1.二叉树的先中后序遍历

1.1.先中后序遍历的基本概念

先序遍历：根→左→右：ABDECFG
中序遍历：左→根→右：DBEAFCG
后序遍历：左→右→根：DEBFGCA
可以先按遍历的顺序写出每次递归的子树的根左右结点，然后依次按结点添加下一次递归的根左右结点，直到访问全部结点（逐层展开）

1.先序遍历：根左右→根（根左右）右→ 根（根左右）（根左右）

2.中序遍历：左根右→（左根右）根→（左根右）根（左根右）

3.后序遍历：左右根→（左右根）右根→（左右根）（左右根）根

1.2.先中后序遍历的代码实现

1.2.1.递归

typedef struct BiTNode{
    elemType value;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
 
//先序遍历
void preOrder(BiTree T){
    if(T != NULL){
        visit(T);    //访问根节点
        preOrder(T->lchild);    //递归遍历左子树
        preOrder(T->rchild);    //递归遍历右子树
    }
}
 
//中序遍历
void inOrder(BiTree T){
    if(T != NULL){
        inOrder(T->lchild);    //递归遍历左子树
        visit(T);    //访问根节点
        inOrder(T->rchild);    //递归遍历右子树
    }
}
 
//后序遍历
void postOrder(BiTree T){
    if(T != NULL){
        postOrder(T->lchild);    //递归遍历左子树
        postOrder(T->rchild);    //递归遍历右子树
        visit(T);    //访问根节点
    }
}

#126为第126行代码，#127为第127行代码
preOrder(A)→访问A→preOrder(A)入栈#126，进入preOrder(B)
访问B→preOrder(B)入栈#126，进入preOrder(D)
访问D→左子树为空→preOrder(D)入栈#127，进入preOrder(G)
访问G→左子树空→右子树空→返回preOrder(D)#127→返回preOrder(B)#126→preOrder(B)#127入栈，进入preOrder(E)
访问E→左子树为空→右子树为空→返回preOrder(B)#127→返回preOrder(A)#126→preOrder(A)#127入栈，进入preOrder(C)
访问C→preOrder(C)#126入栈，进入preOrder(F)
访问F→左子树为空→右子树为空→返回preOrder(C)#126→右子树为空→返回preOrder(A)#127→结束遍历

1.2.2.非递归

后序遍历非递归：栈中剩余元素都是栈顶元素的双亲结点，此特性可求根到结点的路径和两个节点的最近公共结点

#define MAXSIZE 100
 
typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
typedef struct Stack{
    BiTNode data[MAXSIZE];
    int top;
}Stack;
 
//先序遍历
void PreOrder(BiTree T){
    Stack S;
    InitStack(S);
    BiTNode *p = T;
    //当p不存在并且栈空时结束循环
    while(p || !(IsEmpty(S)){
        if (p) {
            //先序遍历先访问p再入队
            visit(p);
            push(S, p);
            p = p->lchild;
        }
        else{
            pop(S, p);
            p = p->rchild);
        }
    }//while
}
 
//中序遍历
void InOrder(BiTree T){
    Stack S;
    InitStack(S);
    BiTNode *p = T;
    while(p || !(IsEmpty(S)){
        if (p){
            push(S, p);
            p = p->lchild;
        }
        else{
            //中序遍历出栈后访问p
            pop(S, p);
            visit(p);
            p = p->rchild;
        }
    }//while
}
 
//后序遍历
void PostOrder(BiTree T){
    Stack S;
    InitStack(S);
    BiTNode *p = T, *r = NULL;
    while(p || !(IsEmpty(S)){
        //p存在，则入栈p，进入p的左子树
        if (p){
            push(S, p);
            p = p->lchild;
        }
        //p不存在
        else{
            //查看栈顶元素
            GetTop(S, p);
            //栈顶元素的右孩子未访问过，则将右孩子入栈，并且进入其左子树
            if (p->rchild && p->rchild != r) {
                p = p->rchild;
                push(S, p);
                p = p->lchild;
            }
            //栈顶元素的右孩子访问过，则出栈并访问栈顶元素，并用r进行标记
            //访问后p置空再次进入else循环
            else {
                pop(S, p);
                visit(p);
                r = p;
                p = NULL;
            }
        }//else
    }//while
}

2.二叉树的层次遍历

2.1.算法思想

初始化一个队列
将根节点入队
若队不空，则队头结点出队，访问该节点，并且将其左右孩子入队
重复3直至队列为空

2.2.代码实现

typedef struct BiTNode{
    elemType value;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
 
typedef struct linkNode{
    //存指针
    BiTNode *data;
    struct linkNode *next;
}linkNode;
 
typedeft struct linkQueue{
    linkNode *front, *rear;
}linkQueue;
 
//层次遍历
void levelOrder(BiTree T){
    linkQueue Q;
    initQueue(Q);    //初始化队列
    BiTree p;
    enQueue(Q, T);    //T入队
    while(!isEmpty(Q)){
        deQueue(Q, p);    //p出队
        visit(p);    //访问p
        if (p->lchild) enQueue(Q, p->lchild);    //p的左孩子入队
        if (p->rchild) enQueue(Q, p->rchild);    //p的右孩子入队
    }
}

3.由遍历序列构造二叉树

中序+前序/后序/层序可以确定一个二叉树

3.1.前序+中序确定一个二叉树

前序序列：D A E F B C H G I
中序序列：E A F D H C B G I
前序序列第一个访问的是根节点→D是根节点→左（EAF）根（D）右（HCBGI）
前序序列中EAF第一个访问的是根节点→A是EAF根节点→左（E）根（A）右（F）
前序序列中HCBGI第一个访问的是根节点→B是HCBGI根节点→左（HC）根（B）右（GI）
前序序列中HC第一个访问的是根节点→C是HC的根节点→左（H）根（C）
前序序列中GI第一个访问的是根节点→G是GI的根节点→根（G）右（I）

3.2.后序+中序确定一个二叉树

后序序列：E F A H C I G B D
中序序列：E A F D H C B G I
后序序列中最后访问的是根节点→D是根节点→左（EAF）根（D）右（HCBGI）
后序序列中EAF最后访问的是根节点→A是EAF根节点→左（E）根（A）右（F）
后序序列中HCBGI最后访问的是根节点→B是HCBGI根节点→左（HC）根（B）右（GI）

6.后序序列中HC最后访问的是根节点→C是HC根节点→左（H）根（C）

7.后序序列中GI最后访问的是根节点→G是GI根节点→根（I）右（G）

3.3.层序+中序确定一个二叉树

层次序列：D A B E F C G H I
中序序列：E A F D H C B G I
层次序列中第一个访问的是根节点→D是根节点→左（EAF）根（D）右（HCBGI）
层次序列中EAF第一个访问的是根节点→A是EAF根节点→左（E）根（A）右（F）
层次序列中HCBGI第一个访问的是根节点→B是HCBGI根节点→左（HC）根（B）右（GI）
层次序列中HC第一个访问的是根节点→C是HC的根节点→左（H）根（C）
层次序列中GI第一个访问的是根节点→G是GI的根节点→根（G）右（I）

4.线索二叉树

4.1.线索二叉树的概念

二叉树使用链式存储时会有n + 1个空指针未使用，可以将其指向该结点的前驱和后继，使得二叉树具有线性特性，从而方便遍历

规定线索二叉树中，相比传统二叉树，多两个标志位——ltag和rtag。tag用来标记指针指向的是左右孩子还是前驱后继

typedef struct threadNode{
    elemType data;
    struct threadNode *lchild, *rchild;
    int ltag, rtag;
}threadNode, *threarTree;

4.2.中序线索化

typedef struct threadNode{
    elemType data;
    struct threadNode *lchild, *rchild;
    int ltag, rtag;
}threadNode, *threadTree;
 
//全局变量pre，指向当前当前结点的前驱结点
threadNode *pre = NULL;
 
void inThread(threadTree &T){
    if (T){
        inThread(T->lchild);
        visit(T);
        inThread(T->rchild);
    }
}
 
void visit(threadNode *q){
    //如果p节点左孩子不存在，则左孩子指向该节点的前驱结点
    if (!q->lchild) {
        q->lchild = pre;
        q->ltag = 1;
    }
    //如果pre结点存在并且它的右子树为空
    if (pre && !pre.rchild){
        pre->rchild = q;
        pre->rtag = 1;
    }
    pre = q;
}
 
void createInThread(threadTree T){
    pre = NULL;
    if(T) {
        inThread(T);
        //如果最后一个结点的右孩子为空，则改标记位
        if (pre->rchild == NULL) pre->rtag = 1;
    }
}

4.3.先序线索化

需要注意，如果不对ltag进行判断，则会进入死循环

typedef struct threadNode{
    struct threadNode *lchild, *rchild;
    elemType data;
    int ltag, rtag;
}threadNode, *threadTree;
 
threadNode pre = NULL;
 
void preThread(threadTree T){
    visit(T);
    //防止进入死循环
    if (ltag == 0) preThread(T->lchild);
    preThread(T->rchild);
}
 
void visit(threadTree *p){
    if (p->lchild == NULL) {
        p->lchild = pre;
        p->ltag = 1;
    }
    if (pre && pre->rchild == NULL) {
        pre->rchild = p;
        pre->rtag = 1;
    }
    pre = p;
}
 
void createPreThread(threadTree T){
    pre = NULL;
    if (T){
        preThread(T);
        if (pre->rchild  == NULL) pre->rtag = 1;
    }
}

4.4.后序线索化

typedef struct threadNode{
    struct threadNode *lchild, *rchild;
    elemType data;
    int ltag, rtag;
}threadNode, *threadTree;
 
threadNode *pre = NULL;
 
void postThread(threadTree T){
    postThread(T->lchild);
    postThread(T->rchild);
    visit(T);
}
 
void visit(threadNode *p){
    if (p->lchild == NULL){
        p->lchild = pre;
        p->ltag = 1;
    }
    if (pre && pre->rchild == NULL){
        pre->rchild = p;
        pre->rtag = 1;
    }
    pre = p;
}
 
void createPostThread(threadTree T){
    pre = NULL;
    if (T) {
        postThread(T);
        if (pre->rchild == NULL) pre->rtag = 1;
    }
}

4.5.找前驱/后继

4.5.1.中序线索树找后继

p->rtag = 1，next = p->rchild
p->rtag = 0，next = 右子树的最左节点

//找到中序遍历的第一个节点
threadNode *firstNode(threadNode *p){
    //找到最左下的结点，并非一定是叶子结点
    //有可能是左空右不空
    while(p->ltag == 0) p = p->lchild;
    return p;
}
 
//找当前节点的后继结点
threadNode *nextNode(threadNode *p){
    //rtag = 0说明有右子树，继续寻找右子树中的最左节点
    if (p->rtag == 0) return firstNode(p->rchild);
    //rtag = 1说明右子树为指向的是后继结点
    else return p->rchild;
}
 
//中序遍历
void InOrder(ThreadNode *T){
    for (threadNode *p = firstNode(T); p != NULL; p = nextNode(p)) visit(p);
}

4.5.2.中序线索树找前驱

p->ltag = 1，pre = p->lchild
p->ltag = 0，pre = 左子树的最右结点

//找到最后一个结点
ThreadNode *LastNode(ThreadNode *p){
    while(p->rtag == 0) p = p->rchild;
    return p;
}
 
//找前驱结点
ThreadNode *PreNode(ThreadNode *p){
    if (p->rtag == 0) return LastNode(p->lchild);
    else return p->rchild;
}
 
//中序遍历
void InOrder(ThreadTree T){
    for (ThreadNode *p = LastNode(T); p != NULL; p = preNode(p)) visit(p);
}

4.5.3.先序搜索树找后继

p->ltag = 1，next = p->rchild
p->ltag = 0

1. 左子树不空，next = 左孩子
2. 左子树空，右子树不空，next = 右孩子

4.5.4.先序搜索树找前驱

p->ltag = 1，pre = p->lchild
p->ltag = 0

1. 如果没有parent指针，则无法找到前驱
2. 有parent指针：

1.p是左孩子：pre = p->parent

2.p是右孩子，但左兄弟为空：pre = p->parent

3.p是右孩子，且有左兄弟：pre = 左兄弟子树的最后一个遍历的结点

4.p是根节点：pre = NULL

4.5.5.后序搜索树找后继

p->rtag = 1，next = p->rchild
p->rtag = 0

1. 如果没有parent指针，则无法找到后继
2. 有parent指针：

1.p是右孩子：next = p->parent

2.p是左孩子，且没有右兄弟：next = p->parent

3.p是左孩子，且有右兄弟：next = 右兄弟子树中第一个被后序遍历的结点

4.p是根节点，p没有后继

4.5.6.后序搜索树找前驱

p->ltag = 1，pre = p->lchild
p->ltag = 0，p必有左子树

1. p有右子树，pre = p->rchild
2. p没有右子树，pre = p->lchild

408数据结构学习笔记——二叉树的遍历和线索二叉树(上）