数据结构(C语言版)严蔚敏-＞二叉树（链式存储结构）的构造及其几种遍历方式(先序、中序、后序、层次)和线索二叉树_构造先(根)序线索二叉树构造中(根)序线索二叉树构造后(根)序线索二叉树

二叉树每个节点至多只有两棵子树（即二叉树中不存在度大于2的节点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

1. 二叉树

二叉树一般采用链式存储结构，用链表节点来存储二叉树中每个节点。在二叉树中，节点结构通常包括若干数据域和若干指针域，二叉链表至少含有三个域：数据域data、左指针域lchild，右指针域rchild。

typedef char ElemType;

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
1
2
3
4
5
6

含有n个节点的二叉链表中，含有n个空指针（空链域）

初始化二叉树参考代码如下：

void InitBiTree(BiTree &T){
    T = NULL;
}
1
2
3

构造二叉树参考代码如下：

// 用先序次序构造二叉树
void CreateBiTree(BiTree &T){
    ElemType ch;
    ch = getchar();
    if(ch =='#')
        T = NULL;
    else{
        if(!(T=(BiTree)malloc(sizeof(BiTNode))))
            exit(-1);
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.1. 二叉树的先序遍历

先序遍历（PreOrder）的操作过程如下：
若二叉树为空，则什么也不做；否则，
1）访问根节点；
2）先序遍历左子树；
3）先序遍历右子树。
对应的递归算法如下：

void PreOrderTraverse(BiTree T){
    if(T!=NULL){
        printf("%c",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}
1
2
3
4
5
6
7

非递归实现如下：

void PreOrderTraverse1(BiTree T){
    BiTree Ts[100];
    int i = 0;
    while((T!=NULL)||(i>0)){
        while(T!=NULL){
            printf("%c",T->data);
            Ts[i++] = T;
            T=T->lchild;
        }
        T = Ts[--i];
        T = T->rchild;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.2. 二叉树的中序遍历

中序遍历（InOrder）的操作过程如下：
若二叉树的为空，则什么也不做；否则
1）中序遍历左子树；
2）访问根节点；
3）中序遍历右子树
递归算法如下：

void InOrderTraverse(BiTree T){
    if(T!=NULL){
        InOrderTraverse(T->lchild);
        printf("%c",T->data);
        InOrderTraverse(T->rchild);
    }
}
1
2
3
4
5
6
7

1.3. 二叉树的后续遍历

后序遍历（PostOrder）的操作过程如下：
若二叉树的为空，则什么也不做；否则
1）后序遍历左子树；
2）后序遍历右子树
3）访问根节点；
递归算法如下：

void PostOrderTraverse(BiTree T){
    if(T!=NULL){
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c",T->data);
    }
}
1
2
3
4
5
6
7

1.4. 二叉树的层次遍历

要进行层次遍历，需要借助一个队列。
参考代码如下：

void LevelOrderTraverse(BiTree T){
    BiTree Ts[100],p;
    int f,r;
    Ts[0] = T;
    f = 0;
    r = 1;
    while(f<r){
        p = Ts[f++];
        // 出队
        printf("%c",p->data);
        if(p->lchild!=NULL)  // 入队
            Ts[r++] = p->lchild;
        if(p->rchild!=NULL)  // 入队
            Ts[r++] = p->rchild;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.5 测试

#include <stdio.h>
#include "bitree.h"

int main(){

    BiTree T;
    InitBiTree(T);
    CreateBiTree(T);
    printf("先序遍历\n");
    PreOrderTraverse(T);
    printf("\n非递归先序遍历\n");
    PreOrderTraverse1(T);
    printf("\n中序遍历\n");
    InOrderTraverse(T);
    printf("\n后序遍历\n");
    PostOrderTraverse(T);
    printf("\n层次遍历\n");
    LevelOrderTraverse(T);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

运行结果：

构造的二叉树如下：

2.线索二叉树

遍历二叉树是以一定的规则将二叉树中的节点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个节点（除第一个和最后一个节点）都有一个直接前驱和直接后继。
通常情况下的二叉链表存储仅能体现一种父子关系，不能直接得到节点的直接前驱和直接后继。上述提到，在含有n个节点的二叉树中，有n+1个空指针。利用这些空指针来存放指向其前驱或后继，这样就可以像遍历单链表那样方便地遍历二叉树。构建线索二叉树正是为了加快查找节点前驱或后继的速度。

规定：若节点没有左子树，令lchild指向其前驱节点；若节点没有右子树，令rchild指向其后继节点。线索二叉树的结构在二叉树的结构基础上，还需要增加两个标志域标识指针域是指向左（右）孩子还是指向前驱（后继）。

标志域含义如下：

• ltag=0，lchild指向节点的左孩子；
• ltag=1，lchild指向节点的前驱节点；
• rtag=0，rchild指向节点的右孩子；
• rtag=1，rchild指向节点的后继节点。

线索二叉树的存储结构如下：

typedef struct ThreadNode{
    char data; // 数据元素
    struct ThreadNode *lchild,*rchild;  // 左、右孩子指针
    int ltag,rtag;  // 左、右线索标志
}ThreadNode,*ThreadTree;
1
2
3
4
5

2.1 中序线索二叉树的构造

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索（线索：指向节点前驱和后继的指针）。假设指针pre指向刚刚访问过的节点，指针p指向正在访问的节点，即pre指向p的前驱。在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre；检查pre的右指针是否为空，若为空就将它指向p。

参考代码如下：

// 通过中序遍历对二叉树线索化
void InThread(ThreadTree p,ThreadTree &pre){
    if(p!=NULL){
        InThread(p->lchild,pre);
        // 递归，线索化左子树
        if(p->lchild == NULL){
            p->lchild = pre;
            p->ltag = 1;
        }
        // 左子树为空，建立前驱线索

        if(pre!=NULL && pre->rchild==NULL){
            pre->rchild = p;
            pre->rtag = 1;
        }
        // 建立前驱节点的后继节点
        pre = p;
        InThread(p->rchild,pre);
        // 递归，线索化右子树
    }
}

void CreateInThread(ThreadTree T){
    ThreadTree pre = NULL;
    if(T!=NULL){
        InThread(T,pre);
        pre->rchild = NULL;
        pre->rtag = 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2.2 中序线索二叉树的遍历

中序线索二叉树的节点中隐含了线索二叉树的前驱和后继信息。在对其进行遍历时，只要先找到序列的第一个节点，然后依次找到节点的后继，直至其后继为空。

ThreadNode* Firstnode(ThreadNode *p){
    while(p->ltag==0)
        p = p->lchild;
    return p;
}

ThreadNode* Nextnode(ThreadNode *p){
    if(p->rtag==0)
        return Firstnode(p->rchild);
    else
        return p->rchild;
}

void Inorder(ThreadNode *T){
    for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
        printf("%c",p->data);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

运行结果：

可以发现中序线索二叉树的遍历结果和二叉树的中序遍历一样。

2.3 先序线索二叉树的构造

先序线索二叉树的构造和中序线索化的构造基本一样，唯一需要注意就是防止出现转圈问题。

// 通过先序遍历对二叉树线索化
void PreThread(ThreadTree p,ThreadTree &pre){
    if(p!=NULL){
        if(p->lchild==NULL){
            p->lchild = pre;
            p->ltag = 1;
        }

        if(pre!=NULL && pre->rchild==NULL){
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        if(p->ltag == 0)  // 防止转圈问题
            PreThread(p->lchild,pre);

        PreThread(p->rchild,pre);
    }
}

void CreatePreThread(ThreadTree T){
    ThreadTree pre = NULL;
    if(T!=NULL){
        PreThread(T,pre);
        if(pre->rchild==NULL){
            pre->rtag = 1;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

2.4 后序线索二叉树的构造

参考代码如下：

// 通过后序遍历对二叉树线索化
void PostThread(ThreadTree p,ThreadTree &pre){
    if(p!=NULL){
        PostThread(p->lchild,pre);
        PostThread(p->rchild,pre);

        if(p->lchild == NULL){
            p->lchild = pre;
            p->ltag = 1;
        }

        if(pre!=NULL && pre->rchild==NULL){
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
    }
}

void CreatePostThread(ThreadTree T){
    ThreadTree pre = NULL;
    if(T!=NULL){
        PostThread(T,pre);
        if(pre->rchild==NULL){
            pre->rtag = 1;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29