二儿子管理三儿子
（三儿子变成二儿子的右孩子） ....
A / | \\ B C D / \\ / \\ E F G H / \\ I J 树T
A / B - C - D / / E -F G - H / I - J
A
/ B / \\ E C \\ \\ F D / / I G \\ \\ J H
涉及题目：
06年 一(7，12)，三(21) 05年 一(6)
七、树遍历：对树中每个结点访问一次，且仅访问一次。
1、 树(二叉树)遍历：
前根（先根，先序，前序）: ABEFIJDGH 中根（中序）：EBIFJAGDH 后根（后序）：EIJFBGDHA 层次：A B D E F G H I J A / \\ B D / \\ / \\ E F G H / \\ I J
2、性质
由一棵二叉树的前序和____中序___可唯一确定这棵二叉树的结构。
由一棵二叉树的后序和____中序____可唯一确定这棵二叉树的结构。
由一棵二叉树的前序和____后序____不能唯一确定这棵二叉树的结构。
只有一个序不行
有三个序肯定可以
涉及题目： 08年 22
05年 三(3)、
已知一棵二叉树的
中序序列 BDCE A FHG 后序序列 DECB HGF A， 请画出该二叉树。再求出前序。
A / \\ 中序序列 BDCE FHG 后序序列 DECB HGF
A / \\ B F \\ \\ 中序序列 DCE HG 后序序列 DEC HG
A / \\ B F \\ \\ C G / \\ / D E H
中序：BDCEAFHG 后序：DECBHGFA，
层次：A B F C G D E H 前序：A B C D E F G H
八、二叉树以二叉链表为存储结构，类型 声明如下，写出二叉树中遍历递归算法。
typedef struct node{
datatype data； //element struct node *Lchild；//left struct node *Rchild；//right }BinaTree；
[ Lchild | data | Rchild ]
1、前序
void PreOrder(BinaTree *t){ //t是指向根的指针变量
//函数定义：前序遍历t为根的二叉树 if(t==NULL)return;//处理边界情况 访问t指向的结点;//打印该结点的元素 PreOrder(t->Lchild); PreOrder(t->Rchild); } 2、中序
void InOrder(BinaTree *t){ if(t==NULL)return; InOrder(t->Lchild);
访问t指向的结点;//打印该结点的元素 InOrder(t->Rchild); } 3、后序
void PostOrder(BinaTree *t){ if(t==NULL)return; PostOrder(t->Lchild); PostOrder(t->Rchild);
访问t指向的结点;//打印该结点的元素 }
4、计算结点个数
int f(BinaTree *t){ //t是指向根的指针变量
//函数定义：计算t为根的二叉树结点数 if(t==NULL)return 0;
//边界情况：如果是空树，结点数为0
return f(t->Lchild)+f(t->Rchild)+1; //自圆其说：左子树结点数+右子树结点数+根数1 }
5、计算叶子结点个数 int g(BinaTree *t){ //t是指向根的指针变量
//函数定义：计算t为根的二叉树叶子结点数 if(t==NULL)return 0;
//边界情况：如果是空树，结点数为0
if(t->Lchild==NULL&&t->Rchild==NULL)return 1; //边界情况：如果只有根，叶子结点数为1 return g(t->Lchild)+g(t->Rchild);
//自圆其说：叶子结点数=左子树叶子结点数+右子树结点数 }
6、计算高度
int h(BinaTree *t){ //t是指向根的指针变量
//函数定义：计算t为根的二叉树高度
if(t==NULL)return 0;//边界情况：如果是空树，高度0 return max{h(t->Lchild),h(t->Rchild)}+1; //自圆其说：max{左子树高度,右子树高度}+1 }
7、 遍历非递归算法：不要求 void PreOrder(BinaTree *t){ int n=0;
if(t==NULL)return; 栈Ｓ＝空； 将ｔ进栈；
while(Ｓ!=空){
将S顶出栈，记作ｘ；n++; if(x->Rchild!=NULL) 将x->Rchild进栈 if(x->Lchild!=NULL) 将x->Lchild进栈 } }
S的元素、t、x类型相同！！ BinaTree *S[100]; BinaTree *x;
8、层次遍历算法（不要求）
//错误的递归算法
void LevelOrder(BinaTree *t){ //t是指向根的指针变量
//函数定义：层次遍历t为根的二叉树 if(t==NULL)return;//处理边界情况 访问t指向的结点;//打印该结点的元素
LevelOrder(t->Lchild); LevelOrder(t->Rchild); }
正确的非递归算法
void LevelOrder(BinaTree *t){ //t是指向根的指针变量
//函数定义：层次遍历t为根的二叉树 int n=0;
if(t==NULL)return; 队列Ｑ＝空； 将ｔ进队； while(Q!=空){
将Ｑ队头出队，记作ｘ；n++; if(x->Lchild!=NULL) 将x->Lchild进队 if(x->Rchild!=NULL) 将x->Rchild进队 }//while
printf(\ }
Q元素,x,t类型一样，BinaTree *．
涉及题目： 08年 10,25
07年 9,10,14,17,18,24,27 06年 四(25),二(13)
05年 四(1), 二(4)、三(3)、
九、书本第10章p175 二叉搜索树：
把关键字储存在二叉树的结点上，左子树的关 键字比根小，右子树的关键字比根大， 中序遍历得到关键字的递增序列
15 / \\ 14 16 / \\ / \\ 13 14.5 15.5 18
新插入的结点一定是叶子 删除结点比较麻烦
涉及题目： 08年 11 06年 三(23) 05年 一(7)
七、Huffman树(第11章): 不唯一，编码不唯一
a 000 b 001 c 010 d 011 e100 f101 n个 log n位
000001011100101001000011100101000001010 频率高用短编码，频率低用长编码 缩短整篇文章的编码长度
100 a:0 /0 \\1 b:100 a (55) c:101 (45) /0 \\1 d:110 / (30) e:1110 / /0 \\1 f:1111 (25) d (14) /0 \\1 (16) /0 \\1 b c e f (13) (12) (9) (5)
010001010111000011110111 a ba c
f5 e9 a45 b13 c12 d16
100 /0 \\1
55 a45 a:1 /0 \\1 b:010 30 \\ c:011 /0 \\1 \\ d:000
d16 14 25 e:0011 /0 \\1 /0 \\1 f:0010 f5 e9 b13 c12
特点：没有度为1的结点，
叶子数=内结点数+1
总结点数
=叶子数+内结点数 =2*叶子数-1 =2*内结点数+1
29=2*叶子数-1
涉及题目：
08年 14 07年 18 06年 二(17)
============================================= 八、p199堆：排序，在数组中进行。 把数组中的数字看成完全二叉树。 存储方法按照p134图7.15
穷堆：左子树的关键字和右子树的 关键字都比根大
左子树的关键字和右子树的 关键字大小关系无所谓
对于任意结点，它比左右孩子穷-小
（不用） 富堆：左子树的关键字和右子树的关键字都 比根小
堆排序：O(n*log n)
反复地 建堆（n-1次）、取根, 直到堆中只剩下一个元素为止。 每次建堆，元素减少一个， 平均时间O(log n)。
根取走后放在原来数组的后面，交换。
步骤1：建堆
1、从最后一个有孩子的结点开始,从后向前建 2、让该结点和它的孩子中最穷的当父亲 3、不合格的父亲不断一直下沉 4、堆建完后，树根肯定最小（穷）。 5 3 4 6 8 1 2 9 9 / \\ (8) (6) / \\ / \\ (5) (4) (3) (2) / (1)
步骤2：排序：取根
1、将根取走，放在原来数组的最后 （与数组最后元素交换， 原来的最后元素作为根）
之后最小数不再参加排序。数组缩短 2、堆被破坏，重新建堆（将根下沉即可）。
涉及题目： 06年 一(8)