性质
树的性质
- 树的结点数等于所有结点的度数加1
- 度为m的树第i层上至多有$m^{i-1}$个结点
- 高度为h的m叉树至多有$1 + m + m^2 + … + m^{h-1} = \frac{1 - m^h}{1-m} = \frac{m^h-1}{m-1}$个结点
- 具有n个结点的m叉树最小高度为$\ceil(log_m(n(m-1)+1))$
二叉树的性质
- 非空二叉树的叶子结点数等于度为2的结点数加1
- 非空二叉树上第i层至多有$2^{i-1}$个结点
- 高度为h的二叉树至多有$2^h-1$个结点
完全二叉树的性质
- $i>1$时，结点i的双亲结点编号为$floor(\frac{i}{2})$, 当i为偶数时，它是左孩子，当i为奇数时，它是右孩子。
- $2i\leq n$时，结点i的左孩子编号为2i，否则无左孩子
- $2i+1 \leq n$时， 结点i的右孩子编号为2i+1，否则无右孩子
- 结点i所在的层次（深度）为$ceil(log_2(i+1))$
- 具有n个结点的完全二叉树高度为$ceil(log_2(n+1))$
树的遍历
先序遍历
递归算法
1
2
3
4
5
6
7
8
9
10
| Status PreOrder_Recursion(BiTree &T){
BiTNode *p = T;
if(!p) return 0;
else{
cout << p->data << " ";
PreOrder_Recursion(p->lchild);
PreOrder_Recursion(p->rchild);
}
return OK;
}
|
非递归算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| Status PreOrder_Iteration(BiTree &T){
BiTNode *p = T;
stack<BiTNode*> S;
cout << "The PreOrder_Iteration: ";
while(p||!S.empty()){
while(p){
cout << p->data << " ";
S.push(p);
p = p->lchild;
}
p = S.top();
S.pop();
p = p->rchild;
}
cout << endl;
return OK;
}
|
中序遍历
递归算法
1
2
3
4
5
6
7
8
9
10
| Status InOrder_Recursion(BiTree &T){
BiTNode *p = T;
if(!p) return ERROR;
else{
InOrder_Recursion(p->lchild);
cout << p->data << " ";
InOrder_Recursion(p->rchild);
}
return OK;
}
|
非递归算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| Status InOrder_Iteration(BiTree &T){
BiTNode *p = T;
stack<BiTNode*> S;
cout << "The InOrder_Iteration: ";
while(p||!S.empty()){
while(p){
S.push(p);
p = p->lchild;
}
p = S.top();
S.pop();
cout << p->data << " ";
p = p->rchild;
}
cout << endl;
return OK;
}
|
后序遍历
递归算法
1
2
3
4
5
6
7
8
9
10
| Status PostOrder_Recursion(BiTree &T){
BiTNode *p = T;
if(!p) return ERROR;
else{
PostOrder_Recursion(p->lchild);
PostOrder_Recursion(p->rchild);
cout << p->data << " ";
}
return OK;
}
|
非递归算法
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
| Status PostOrder_Iteration(BiTNode *T){
BiTNode *p = T;
stack<BiTNode*> S;
BiTNode *pCur = T;
BiTNode *pLast = NULL;
while(pCur||!S.empty()){
// 这里的思想和中序遍历线索二叉树很相似
while(pCur){
S.push(pCur);
pCur = pCur->lchild;
}
pCur = S.top();
S.pop();
// 符合访问条件
if(pCur->rchild==NULL||pCur->rchild==pLast){
cout << pCur->data << " ";
pLast = pCur;
// 这个NULL很关键，是退栈的一个条件
// 意思是告诉程序，这个节点已经被打印了，该接着退栈了
pCur = NULL;
}
else{
S.push(pCur);
pCur = pCur->rchild;
}
}
return OK;
}
|
主要是两个思想：
- 栈中的元素全都是访问到了，但是没有资格打印的节点
- 打印资格是什么？
-
- 该结点无右孩子
-
- 右孩子刚被访问过
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
| Status PostOrder_Iteration(BiTree &T){
BiTNode *p = T;
stack<BiTNode*> S;
BiTNode *pCur, *pLast;
pCur = p;
cout << “The PostOrder: “;
while(pCur){
S.push(pCur);
pCur = pCur->lchild;
}
while(!S.empty()){
pCur = S.top();
S.pop();
// 符合访问条件
if(pCur->rchild==NULL||pCur->rchild==pLast){
cout << pCur->data << “ “;
pLast = pCur;
}
else{
S.push(pCur);
pCur = p->rchild;
while(pCur){
S.push(PCur);
pCur = pCur->lchild;
}
}
}
cout << endl;
return OK;
}
|
Note：所有的非递归算法，都借助了NULL元素作为退栈的条件。
while循环，不管什么遍历，他要做的一件事情都是先找到最左下角的元素，在这个过程中，在通过条件判断什么时候打印该结点。
也就是说对树的遍历，路径是一定的，变化的仅仅是打印结点的条件。
层次遍历
求二叉树的宽度：
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
| // 层次遍历, 用NULL来标记一层遍历完毕
int Tranverse(BiTNode *root){
int count = 0， max = 0;
BiTNode *p = root;
queue<BiTNode*> Q;
if(p){
Q.push(p);
Q.push(NULL);
}
else{
return ERROR;
}
while(!Q.empty()){
p = Q.front();
Q.pop();
if(p){
count++;
if(p->lchild) Q.push(p->lchild);
if(p->rchild) Q.push(p->rchild);
}
else{
if(Q.empty()) break;
if(count>max) max = count;
count = 0;
Q.push(NULL);
}
}
return max;
}
|
由遍历序列构造二叉树
先序序列和中序序列
- 先序序列第一个结点一定是根结点
- 中序序列中，根结点一定将中序序列分割成两个子序列
- 先序序列中找到对应的左右子序列，第一个结点分别是左右子树的根结点
- 如此递归
后序序列和中序序列
- 后序序列最后一个结点一定是根结点
- 中序序列中，根结点一定将中序序列分割成两个子序列
- 后序序列中找到对应的左右子序列，最后结点分别是左右子树的根结点
- 如此递归
层次序列和中序序列
- 层次序列第一个结点一定是根结点
- 中序序列中，根结点一定将中序序列分割成两个子序列
- 先序序列中找到对应的左右子序列，第一个结点分别是左右子树的根结点
- 如此递归
线索二叉树
二叉树的线索化，实际上就是遍历一次二叉树，在遍历的过程中检查当前结点左右指针域是否为空，若为空，将它们改为指向前趋结点或后继结点的线索。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void InOrder(ThreadTree &p, ThreadTree &per){
if(p!=NULL){
InOrder(p->lchild, pre);
if(p->lchild==NULL){
p->lchild = pre;
p->ltag = 1;
}
if(pre!=NULL&&pre->rchild==NULL){
pre->rchild = p;
pre->tag = 1;
}
pre = p;
InTread(p->rchild,pre);
}
}
void CreateInThread(ThreadTree &T){
ThreadTree pre = NULL;
if(T!=NULL){
InOrder(T, pre);
pre->rchild = NULL; //处理遍历的最后一个结点
pre->rtag = 1;
}
}
|
中序遍历线索二叉树
1
2
3
4
5
6
7
8
9
10
11
12
| void InOrderThr(BiThrTree &T){
BiThrTree p = T->lchild; //p指向根结点
while(p!=T){
while(p->late==Link) p=p->lchild;
visit(p);
while(p->rtag==Thread&&p->rchild!=t){
p = p->rchild;
visit(p);
}
p = p->rchild;
}
}
|
假设二叉排序树以中序后继线索表作为存储结构，编写按非递减顺序输出该二叉排序树中所有大于a且小于b的关键字的算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| //基于中序遍历线索二叉树的思想写该算法
Void f(BiThrTree &t, int a, int b){
BiThrTree p = t->rchild;
while(p!=t){
while(p->ltag==Link) p = p->lchild;
if(p->data.key>b) break;
if(p->data.key>a){
cout << p->data;
}
while(p->rtag==Thread&&p->data.key<=b&&p->rchild!=t){
if(p->data.key>a){
cout << p->data;
}
p = p->rchild;
}
p = p->child;
}
}
|
后序遍历线索二叉树
后序遍历线索二叉树需要改变数据结构，加入父结点
(尚未验证）(在一棵二叉树上验证通过，尚未在多棵二叉树测试）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void PostOrderThrBiTree(BiTree &T){
BiTree p = T->lchild, pre = T;
while(p!=T){
while(p->ltag==Link&&p->lchild!=T) p = p->lchild;
while(p->rtag==Thread&&p->rchild!=T){
cout << p->data;
pre = p;
p = p->rchild;
}
if(p->rchild==pre){
cout << p->data;
pre = p;
p = p->parent->rchild;
if(p==pre){
cout << p->parent->data;
break;
}
}
else{
p = p->rchild;
}
}
}
|
树和森林的遍历
树，森林和二叉树的相互转换
左边是孩子，右边是兄弟
树的遍历
- 树的先根遍历等同于对转换所得的二叉树进行先序遍历
- 树的后根遍历等同于对转换所得的二叉树进行中序遍历
森林的遍历
- 森林的先序遍历等于对转换所得的二叉树进行先序遍历
- 森林的中序遍历等于对转换所得的二叉树进行中序遍历
哈夫曼树
