二叉树

在《二叉树的定义和性质》中我们已经认识了二叉树这种数据结构。我们知道链表的每个节点可以有一个后继，而二叉树（Binary Tree）的每个节点可以有两个后继。比如这样定义二叉树的节点：

typedef struct node *link;

struct node {

unsigned char item;

link l, r;

};

这样的节点可以组织成下图所示的形态。

二叉树可以这样递归地定义：
1. 就像链表有头指针一样，每个二叉树都有一个根指针（上图中的root指针）指向它。根指针可以是NULL，表示空二叉树，或者
2. 根指针可以指向一个节点，这个节点除了有数据成员之外还有两个指针域，这两个指针域又分别是另外两个二叉树（左子树和右子树）的根指针。

链表的遍历方法是显而易见的：从前到后遍历即可。二叉树是一种树状结构，如何做到把所有节点都走一遍不重不漏呢？有以下几种方法，如下图（来自《linux c 编程一站式学习》）所示：

前序（Pre-order Traversal）（深度优先搜索）、中序（In-order Traversal）、后序遍历（Post-order Traversal）、层序遍历（Level-order Traversal）（广度优先搜索）。如何分辨三种次序的遍历方法呢？《data structrue and algorithm analysis in c》中有一句:We can evaluate an expression tree, T, by applying the operator at the root to the values obtained by recursively evaluating the left and right subtrees.

个人总结就是：前序（root->left->right) ; 中序(left->root->right); 后序（left->right->root)

举例上图来说，前序遍历，首先root是4，接着要Left，就是指左边子树，在左边子树中又先是root即2，然后是left的1，接着说right的3，现在左边子树递归完毕了，接着右边子树，同样先root即5，没有left，最后是right的6，所以最后排列是421356。

注意：已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

但已知前序和后序遍历序列，是不能确定一棵二叉树的。

如果我们要在内存中建立一个如图6-9-1左图这样的树，为了能让每个结点确认是否有左右孩子，可以对它进行扩展，如右图那样，也就是将二叉树的每个结点的空指针引出一个虚结点，其值为一特定值，比如'#'。我们称这种处理后的二叉树为扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。比如图6-9-1的前序遍历序列就为AB#D##C##。

示例程序如下：（改变自《大话数据结构》）

 C++ Code 

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

#include<iostream>
using namespace std;

#define MAXSIZE 50

typedef char ElemType;
typedef char String[MAXSIZE + 1]; //以'’结尾
String str; /* 用于构造二叉树*/
ElemType NoChar = ' '; /* 字符型以空格符为空 */

/* 结点结构 */
typedef struct BTNode
{
    ElemType data;/* 结点数据 */
    struct BTNode *LChild;/* 左右孩子指针 */
    struct BTNode *RChild;
} BTNode, *BTNodePtr;

/* 构造一个字符串 */
bool StrAssign(String Dest, char *ptr)
{
    cout << "Assign Str ..." << endl;
    int i;
    for (i = 0; ptr[i] != '' && i < MAXSIZE; i++)
        Dest[i] = ptr[i];
    Dest[i] = '';
    return true;
}
/* 构造空二叉树 */
bool InitBTree(BTNodePtr *Tpp)
{
    *Tpp = NULL;
    return true;
}
/* 销毁二叉树 */
void DestroyBTree(BTNodePtr *Tpp)
{
    if (*Tpp)
    {
        if ((*Tpp)->LChild)/* 有左孩子 */
            DestroyBTree(&(*Tpp)->LChild);/* 销毁左孩子子树 */
        if ((*Tpp)->RChild)/* 有右孩子 */
            DestroyBTree(&(*Tpp)->RChild); /* 销毁右孩子子树 */
        free(*Tpp);/* 释放根结点 */
        *Tpp = NULL;/* 空指针赋0 */
    }
}
/* 按前序输入二叉树中结点的值（一个字符） */
/* #表示空树，构造二叉链表表示二叉树。 */
void CreateBTree(BTNodePtr *Tpp)
{
    ElemType ch;
    static int i = 0;
    if (str[i] != '')
        ch = str[i++];
    if (ch == '#')
        *Tpp = NULL;
    else
    {
        *Tpp = (BTNodePtr)malloc(sizeof(BTNode));
        if (!*Tpp)
            exit(1);
        (*Tpp)->data = ch;/* 生成根结点 */
        CreateBTree(&(*Tpp)->LChild);/* 构造左子树 */
        CreateBTree(&(*Tpp)->RChild);/* 构造右子树 */
    }
}

bool BTreeEmpty(BTNodePtr Tp)
{
    if (Tp)
        return false;
    else
        return true;
}
/*返回二叉树的深度 */
int BTreeDepth(BTNodePtr Tp)
{
    int i, j;
    if (!Tp)
        return 0;
    if (Tp->LChild)
        i = BTreeDepth(Tp->LChild);
    else
        i = 0;
    if (Tp->RChild)
        j = BTreeDepth(Tp->RChild);
    else
        j = 0;
    return i > j ? i + 1 : j + 1;
}
/* 返回根节点的数值 */
ElemType Root(BTNodePtr Tp)
{
    if (BTreeEmpty(Tp))
        return NoChar;
    else
        return Tp->data;
}
/* 前序递归遍历*/
void PreOrderTraverse(BTNodePtr Tp)
{
    if (Tp == NULL)
        return;
    cout << Tp->data << ' ';
    PreOrderTraverse(Tp->LChild);
    PreOrderTraverse(Tp->RChild);
}
/* 中序递归遍历*/
void InOrderTraverse(BTNodePtr Tp)
{
    if (Tp == NULL)
        return;
    InOrderTraverse(Tp->LChild);
    cout << Tp->data << ' ';
    InOrderTraverse(Tp->RChild);

}
/* 后序递归遍历*/
void PostOrderTraverse(BTNodePtr Tp)
{
    if (Tp == NULL)
        return;
    PostOrderTraverse(Tp->LChild);
    PostOrderTraverse(Tp->RChild);
    cout << Tp->data << ' ';
}

int main(void)
{
    BTNodePtr Tp;
    InitBTree(&Tp);
    StrAssign(str, "ABDH#K###E##CFI###G#J##");
    cout << "输入字符序列（前序遍历）为：" << endl;
    cout << str << endl;
    CreateBTree(&Tp);

    cout << "前序遍历二叉树：" << endl;
    PreOrderTraverse(Tp);
    cout << endl;
    cout << "中序遍历二叉树：" << endl;
    InOrderTraverse(Tp);
    cout << endl;
    cout << "后序遍历二叉树：" << endl;
    PostOrderTraverse(Tp);
    cout << endl;

    cout << "二叉树的根节点为：" << Root(Tp) << endl;
    cout << "二叉树的深度为：" << BTreeDepth(Tp) << endl;

    cout << "销毁二叉树 ..." << endl;
    DestroyBTree(&Tp);
    if (BTreeEmpty(Tp))
        cout << "二叉树现已为空..." << endl << endl;

    return 0;
}

输出为：