[数据结构与算法]数据结构基础知识——树与二叉树（一）

第五章 数和二叉树

本部分为数据结构中较为重要部分，因此优先完成，预计分为几个部分单独完成，为常见考点+常见算法+相关算法题总结

考点： 二叉树的存储结构

• 顺序存储
• 链式存储

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

// 以下为常见写法，包含线索标志，适用定义线索二叉树
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode* lchild, * rchild;
    int ltag, rtag;
}ThreadNode, * ThreadTree;

考点：已知中序+前序/后序序列，还原二叉树

考点：二叉树的遍历🔺

递归写法（前序、中序、后序）

• 前序遍历

void PreOrderTraverse(BiTree T){
    if(T != NULL){
        visit(T);
        PreOrderTraverse(T->lchild)
        PreOrderTraverse(T->rchild)
    }
}

非递归写法

• 前序遍历(DLR/根-左-右)

void PreOrderTraverse(BiTree T){
	Stack S; InitStack(S);	BiTNode *p;
    if(T != NULL) Push(S, T);
    while(!IsEmpty(S)){
        Pop(S, p);
        visit(p);
        if(p->rchild != NULL){
            Push(p->rchild)// 优先将右孩子压栈，因为右孩子最后遍历
        }
        if(p->lchild != NULL){
            Push(p->lchild)
        }
    }
    DestroyStack(S);
}

• 中序遍历(LDR/左-根-右)

void InOrderTraverse(BiTree T){
	Stack S; InitStack(S);	BiTNode *p = T;
	while(p != NULL || !IsEmpty(S)){
        if(p != NULL){
            Push(S, p);// 节点非空则入栈
            p = p->lchild;
        }else{
            Pop(S, p);
            visit(p);
            if(p->rchild != NULL)
                p = p->rchild;
            else
                p = NULL;
        }
    }
    DestroyStack(S);
}

• 后序遍历(LRD/左-右-根)

void PostOrderTraverse(BiTree T){
	Stack S; InitStack(S);	BiTNode *p = T, *r = NULL;
	while(p != NULL || !IsEmpty(S)){
        if(p != NULL){
            Push(S, p);// 节点存在则一直入栈，将左子树链路全部压入栈中
            p = p->lchild;
        }else{
            GteTop(S, p);//获取栈顶元素
			if(p->rchild != NULL && p->rchild != r){// 因为后序遍历，若有右子树还要先遍历右子树
                // 栈顶元素有右子树且未访问
                p = p->rchild;
                Push(S, p);
                p = p->lchild;
            }else{
                // 无右子树或已经访问
                Pop(S, p);
                visit(p);
                r = p;
                p = NULL;
            }// else
        }
    }// while
    DestroyStack(S);
}

• 层次遍历

void LevelOrder(BiTree T){
    Queue Q;	InitQueue(Q);
    BiTNode *p;
    EnQueue(Q,T);
    while(!IsEmpty(Q)){
        DeQueue(Q, p);
        visit(p);
        if(p->lchild != NULL)
            Enqueue(Q, p->lchild);
        if(p->rchild != NULL)
            Enqueue(Q, p->rchild);
    }// while
}

考点：线索二叉树（理解）

考点：树的存储结构

// 双亲表示法
typedef struct PTNode{
    ElementType data;
    int parent;
}PTNode;

typedef struct{
    PTNode nodes[MaxSize];
    int r, n; // 根的位置和总的节点个数
}PTree;

// 孩子表示法
typedef struct CTNode{
    int child;
    struct CTNode *next;
}*ChildPtr;

typedef struct{
    ElementType data;
    ChildPtr firstchild;
}CTBox;

typedef struct{
    CTBox nodes[MaxSize];
    int n, r; // 节点数和根的位置
}CTree;

//孩子兄弟表示法 二叉链
typedef struct CSNode{
    ElementType data;
    struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;