Tree & Binary Tree

A( B(E, F(K, L)), C(G), D(H, I, J(M)) ) 树根 T2 T3 T1

二叉树的类型定义

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交叉的二叉树组成 A B E C F G D 左子树 H K

二叉树的五种基本形态 空树 只含根结点 左右子树均不为空树 N 右子树为空树 左子树为空树 N N N L R L R

二叉树的分类 完全二叉树 丰满二叉树 排序二叉树 平衡二叉树

满二叉树：指的是深度为k且含有2k-1个结点的二叉树 3 5 4 6 7 完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应 9 10 11 12 13 14 15 8 a b c d e f g h i j

二叉树 的重要特性

性 质 1 　在二叉树的第i(i≥1)层上至多有 2i-1 个结点

用归纳法证明 归纳基础 归纳假设 归纳证明 i = 1 层时，只有一个根结点： 2i-1 = 20 = 1 假设对所有的 j，1≤ j  i， 命题成立 二叉树上每个结点至多有两 棵子树，则第 i 层的结点数 ≤ 2i-2 2 = 2i-1

性 质 2 深度为k（k≥1）的二叉树上至多 含2k-1 个结点

证明 　 基于上一条性质，深度为 k 的二　　　　 　叉树上的结点数至多为 20+21+       +2k-1 = 2k-1

性 质 3 对任何一棵二叉树，若它含有n0 个 叶子结点、n2 个度为2的结点，则必存 在关系式：n0 = n2+1

证明 设二叉树上结点总数 n = n0 + n1 + n2 又二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1

性 质 4 　具有n个结点的完全二叉树的深度 为log2n +1

证明 设完全二叉树的深度为 k 则根据第二条性质得 2k-1≤ n < 2k 即 k-1 ≤ log2 n < k 因为k只能是整数，因此，k=log2n +1

性 质 5 若对含n个结点的完全二叉树从 上到下且从左至右进行1至n的编号， 则对完全二叉树中任意一个编号为i 的结点：

(1)若i=1，则该结点是二叉树的根， 无双亲，否则，编号为i/2 的 结点为其双亲结点 (2)若2i>n，则该结点无左孩子，否 则，编号为2i的结点为其左孩子 结点 (3)若2i+1>n，则该结点无右孩子结 点，否则，编号为2i+1的结点为 其右孩子结点

树的存储结构 一、广义表表示法 二、双亲表示法 三、孩子表示法 四、孩子兄弟表示法

广义表表示法 树的广义表表示 (结点的utype域没有画出)

双亲表示法 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 A D B C E F G data parent 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 A D B C E F G

孩子链表表示法 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 4 A B C D E F G data firstchild 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 4 1 2 3 A 4 5 B C D E F 6 G

孩子兄弟表示法 root A B C E D F G A B C D A B C E D F G E F G

孩子兄弟表示法 data firstChild nextSibling

二叉树的存储结构 一、二叉树的顺 序存储表示 二、二叉树的链 式存储表示

顺序存储表示 完全二叉树的 一般二叉树的 数组表示 数组表示

A 2 1 B D 6 4 E C 13 F 0 1 2 3 4 5 6 7 8 9 10 11 12 13 A B D C E F

由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况

二叉链表 root 结点结构 lchild data rchild A   B D    C E   F

链表表示

三叉链表 结点结构 root parent lchild data rchild  A   B D    C E   F

二叉链表的静态结构

(Binary Tree Traversal) 二叉树遍历 (Binary Tree Traversal)

问题的提出 顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次 “访问”的含义可以很广，如：输出结 点的信息等

“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构，每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题

对“二叉树”而言，可以有三条搜索路径 1．先上后下的按层次遍历 2．先左（子树）后右（子树）的遍历 3．先右（子树）后左（子树）的遍历

设 访问根结点 记作 V 遍历根的左子树 记作 L 遍历根的右子树 记作 R 则可能的遍历次序有 前序 VLR 逆前序 VRL 中序 LVR 逆中序 RVL 后序 LRV 逆后序 RLV 层次遍历

前序遍历 (Preorder Traversal) 若二叉树为空，则空操作 否则 访问根结点(V) 前序遍历左子树(L) 前序遍历右子树(R) 遍历结果 - + a * b - c d / e f

中序遍历 (Inorder Traversal) 若二叉树为空，则空操作 否则 中序遍历左子树(L) 访问根结点(V) 中序遍历右子树(R) 遍历结果 a + b * c - d - e / f 表达式语法树

后序遍历 (Postorder Traversal) 若二叉树为空，则空操作 否则 后序遍历左子树(L) 后序遍历右子树(R) 访问根结点(V) 遍历结果 a b c d - * + e f / -

层次遍历(Levelorder Traversal) 从上到下，从左到右 遍历结果 - ＋／a* e f b -cd

按给定的表达式建相应二叉树 由前缀表达式建树 例如: -×+abc/de 由中缀表达式建树 例如：(a+b)×c–d/e 由后缀表达式建树

对应前缀表达式 -×+abc/de 的二叉树 - × / + c d e 特点： 操作数为叶子结点 运算符为分支结点 a b

对应中缀表达式 (a+b)×c-d/e 的二叉树 - × / + c d e 特点： 操作数为叶子结点 运算符为分支结点 a b

对应后缀表达式 ab+c×de/- 的二叉树 - × / + c d e 特点： 操作数为叶子结点 运算符为分支结点 a b

+ + + / + 分析表达式和二叉树的关系 a+b (a+b)×c × c a b b a a+b×c (a+b)×c – d/e - ×

二叉树的计数 由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树 由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树 　　由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树 　　由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树 　　由二叉树的前序序列和后序序列不可唯一地确定一棵二叉树

仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树， 由二叉树的先序和中序序列建树 　仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树， 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？ 二叉树的先序序列 根 左子树 右子树 二叉树的中序序列 左子树 根 右子树

a a b c d e f g a b c d e f g c c b d a e g f b d e g f 先序序列中序序列 ^ ^ ^

前序序列{ABHFDECKG} 中序序列{HBDFAEKCG}

　如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树

　　问题是有n个数据值，可能构造多少种不同的二叉树？ 　　我们可以固定前序排列，选择所有可能的中序排列

有 3 个数据 { 1, 2, 3 }，可得5种不同的二叉树。它们的前序排列均为123，中序序列可能是 123，132，213，231，321

　有0个, 1个, 2个, 3个结点的不同二叉树如下

计算具有n个结点的不同二叉树的棵数 Catalan函数 具有4个结点的不同二叉树

树　的　遍　历 深度优先遍历 树的先根次序遍历 树的后根次序遍历 广度优先遍历 树的层次次序遍历

先根遍历 A B C D E F G H I J K A B E F C D G H I J K 后根遍历 E F B C I J K H G D A 层次遍历： A B C D E F G H I J K

森林由三部分构成 B C D 1．森林中第一棵树的根结点 E F G H I J K 2．森林中第一棵树的子树森林 3．森林中其它树构成的森林

森林的先根遍历 若森林F为空, 返回 否则: 访问F的第一棵树的根结点 先根次序遍历第一棵树的子树森林 先根次序遍历其它树组成的森林 森林的二叉树表示

森林的后根遍历 若森林F为空，返回 否则: 后根次序遍历第一棵树的子树森林 后根次序遍历其它树组成的森林 访问F的第一棵树的根结点 森林的二叉树表示

森林的层次遍历 若森林F为空，返回 否则: 依次遍历各棵树的根结点 依次遍历各棵树根结点的所有子女 依次遍历这些子女结点的子女结点 森林的二叉树表示

二叉树的类定义

template <class Type> class BinTreeNode { private: BinTreeNode<Type> *LChild,*RChild; Type data; }; class BinaryTree { BinTreeNode<Type> *root; };

二叉树前序遍历递归算法 template <class Type> void BinaryTree<Type>:: PreOrder(BinTreeNode<Type>*current) { if ( current != NULL ) { cout << current→data; PreOrder ( current→LChild ); PreOrder ( current→RChild ); } }

二叉树中序遍历递归算法 template <class Type> void BinaryTree <Type>:: InOrder(BinTreeNode<Type>*current) { if ( current != NULL ) { InOrder ( current→LChild ); cout << current→data; InOrder ( current→RChild ); } }

二叉树后序遍历递归算法 template <class Type> void BinaryTree<Type>:: PostOrder(BinTreeNode<Type>*current) { if ( current != NULL ) { PostOrder ( current→LChild ); PostOrder ( current→RChild ); cout << current→data; } }

二叉树前序遍历 非递归算法

template <class Type> void BinaryTree<Type>:: PreOrder(BinTreeNode<Type> *p ) { do { while ( p != NULL ) { cout << p→data; Push ( s, p ); p = p→LChild; } if ( !Empty ( s ) ) { p = pop ( s ); p = p→RChild; } }while ( ( !Empty ( s ) ) || ( p != NULL ) ) }

二叉树中序遍历 非递归算法

template <class Type> void BinaryTree<Type>:: PreOrder(BinTreeNode<Type> *p ) { do { while ( p != NULL ) { Push ( s, p ); p = p→LChild; } if ( !Empty ( s ) ) { p = pop ( s ); cout << p→data; p = p→RChild; } }while ( ( !Empty ( s ) ) || ( p != NULL ) ) }

应用二叉树遍历的事例

计算二叉树结点个数的一种方法 template <class Type> int BinaryTree<Type>:: Size ( BinTreeNode <Type> *t ) { if ( t == NULL ) return 0; else return 1 + Size ( t→LChild ) + Size ( t→RChild ); }

计算二叉树的高度 template <class Type> int BinaryTree<Type>:: Depth ( BinTreeNode <Type> *t ) { if ( t == NULL ) return 0; else return 1+ Max( Depth( t→LChild ), Depth( t→RChild ) ); }

线索二叉树

遍历二叉树的结果是， 求得结点的一个线性序列 A 先序序列 B A B C D E F G H K E F C 中序序列 B D C A H G K F E G D 后序序列 D C B H K G F E A H K

包含 “线索” 的存储结构，称作 “线索链表” 指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索” A B C D E F G H K 包含 “线索” 的存储结构，称作 “线索链表” ^ B E ^ 与其相应的二叉树， 称作 “线索二叉树” C ^ ^ D ^

对线索链表中结点的约定 在二叉链表的结点中增加两个标志域 LTag和RTag,并作如下规定: 若该结点的左子树不空， 则LChild域的指针指向其左孩子， 且左标志LTag的值为0 否则，LChild域的指针指向其“前驱”， 且左标志LTag的值为1

若该结点的右子树不空， 则RChild域的指针指向其右孩子， 且右标志RTag的值为0 否则，RChild域的指针指向其“后继”， 且右标志RTag的值为1 如此定义的二叉树的存储结构称作“线索链表”

LTag = 0, LChild为指针,指向左孩子 LTag = 1, LChild为线索,指向前驱 RTag = 0, RChild为指针,指向右孩子 RTag = 1, RChild为线索,指向后继

猜一猜,是哪一种线索二叉树

前序序列 A B D C E 后序序列 D B E C A

带表头结点的中序线索二叉树

寻找当前结点 在中序下的后继

if (pRTag==1) if (pRChild!=T.root) 后继为 pRChild else 无后继 else //pRTag==0 后继为当前结点右 子树的中序下的第 一个结点 else 出错情况 A B C D E F G H I J K L

寻找当前结点 在中序下的前趋

if (pLTag==1) if (pLChild!=T.root) 前驱为pLChild else 无前驱 else //pLTag==0 前驱为当前结点左 子树的中序下的最 后一个结点 else 出错情况 A B C D F E H I G K J L

在前序线索化二叉树中寻找当前结点的后继

在前序线索化二叉树中寻找当前结点的前趋

在后序线索化二叉树中寻找当前结点的后继

在后序线索化二叉树中寻找当前结点的前趋

哈 夫 曼 树 (Huffman Tree) 与 哈 夫 曼 编 码

设给出一段报文 CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 } 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36

若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度 A : 0 T : 10 C : 110 S : 111 它的总编码长度为 7*1+5*2+( 2+4 )*3 = 35 比等长编码的情形要短

结点间路径长度(Path Length) 连接两结点的路径上的分支数 结点的路径长度 从根结点到该结点的路径上分 支的数目

树的路径长度 树中每个结点的路径长度之和 树的带权路径长度 (Weighted Path Length,WPL) 树的各叶结点所带的权值与该 结点到根的路径长度的乘积的 和

在所有含n个叶子结点、并带相同 权值的m叉树中，必存在一棵其带权路 径长度取最小值的树，称为“最优树”, 或“哈夫曼树” (Huffman Tree)

具有不同带权路径长度的二叉树 哈夫曼树中，权值大的结点离根最近

WPL(T)= 72+52+23+43+92 =60 WPL(T)= 74+94+53+42+21 =89 2 4 7 7 9 WPL(T)= 72+52+23+43+92 =60 WPL(T)= 74+94+53+42+21 =89

构造哈夫曼树 (以二叉树为例)

根据给定的 n 个权值 {w1, w2, …, wn}，造 n 棵二叉树的集合 F = {T1, T2, … , Tn}， 其中每棵二叉树中均只含一个带权 值为 wi 的根结点，其左、右子树为 空树； (1)

在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、 右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和； (2)

从F中删去这两棵树，同时加入 刚生成的新树 (3) 重复 (2) 和 (3) 两步，直至 F 中只 含一棵树为止 (4)

已知权值 W={ 5, 6, 2, 9, 7 } 5 6 2 9 7 6 9 7 7 5 2 9 7 13 5 2 7 6

9 7 13 5 2 7 6 29 1 13 16 1 1 7 9 6 7 1 00 01 10 5 2 110 111

哈夫曼树的构造过程

哈夫曼树的构造过程

前缀编码 任何一个字符的编码都不是同一 字符集中另一个字符的编码的前缀 利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短

设给出一段报文 CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 } 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36

以各字符出现概率{2,7,4,5}为各叶结点权值，建立哈夫曼树，得哈夫曼编码(不等长编码) A:0 T:10 C:110 S:111 总编码长度为 7*1+5*2+(2+4)*3=35 总编码长度正好等 于哈夫曼树的带 权路径长度WPL

在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。 哈夫曼树的应用 判定树 在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。 例1 将学生百分成绩按分数段分级的程序。 若学生成绩分布是均匀的，可用图（a)二叉树结构来实现。 a<60 a<70 a<80 a<90 不及格 中等 良好 优秀 及格 Y N (a) 输入10000个数据，则需进行31500次比较。

10000个学生成绩转换成五分制的判定 500*1+1500*2+4000*3+3000*4+1000*4 =31500 分数 0-59 60-69 70-79 80-89 90-100 比例数 0.05 0.15 0.40 0.30 0.10 A<60 500*1+1500*2+4000*3+3000*4+1000*4 =31500 Y N A<70 不及格 Y N 及格 A<80 N Y 中等 A<90 Y N 良好 优秀

学生成绩分布不是均匀的情况： Y N Y N (c) (b) 分数 0—59 60—69 70—79 80—89 90—99 比例 0.05 0.15 0.4 0.3 0.10 70≤a< 80 a<60 及格 中等 良好 80≤a<90 60≤a<70 不及格 优秀 Y N 以比例数为权构造一棵哈夫曼树，如（b)判断树所示。 输入10000个数据，仅需进行22000次比较。 再将每一比较框的两次比较改为一次，可得到（c)判定树。 不及格 Y a<90 a<80 a<70 a<60 优秀 中等 及格 良好 N (c) (b)

用此形式比较次数为： 500*3+1500*3+4000*2+3000*2+1000*2=22000 A<80 Y N A<70 中等 良好 优秀 Y N 不及格 及格 用此形式比较次数为： 500*3+1500*3+4000*2+3000*2+1000*2=22000

　1. 熟练掌握二叉树的结构特性，了解相应的证明方法。 　2. 熟悉二叉树的各种存储结构的特点及适用范围。 　3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。

　　4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。

　5. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握 1 至 2 种建立二叉树和树的存储结构的方法。 　6. 学会编写实现树的各种操作的算法。　　 7. 了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。