•学习要点
–领会树和二叉树的类型定义，理解树和二叉树的结构差别。
–熟记二叉树的主要特性，并掌握它们的证明方法。–熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。
–理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。
–熟练掌握二叉树和树的各种存储结构及其建立的算法。–学会编写实现树的各种操作的算法。
–了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。
树(Tree)的实例
•树的实例1：家族树
设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可用树A表示。BCDEFGHIJKLM树(Tree)的实例
•树的实例2：计算机的文件系统
计算机中树是常用的数据组织形式。不论是DOS文件系统还是windows文件系统，所有的文件都是用树的形式来组织的。
C盘
文件夹1文件夹n文件1文件2
文件夹11文件夹12文件13文件14
树的定义(递归定义)
•树是n(n≥0)个结点的有限集合T。T非空时满足：
–有且仅有一个特殊的称为根的结点。
–除根接点外，其余结点可分为m个互不相交的子集合，而且这些子集合中的每一个本身又是一棵非空树，也称为根的子树(subtree)。
•结点数为0(n=0)的树，称为空树。
•一棵树也可以没有子树(m=0)，此时这棵树只包含一个根结点。
•如有子树，则子树非空(使子树的个数可以定义)。
树的基本术语
B
AC
D
J
根——即根结点(没有前驱)
EFGHI叶子——即终端结点(没有后继)
森林——指m棵不相交的树的集
LF合(例如删除A后的子树个数)K
有序树——结点各子树从左至右有序，不能互换(左为第一)无序树——结点各子树可互换位置。
双亲——即上层的那个结点(直接前驱)
孩子——即下层结点的子树的根(直接后继)
兄弟——同一双亲下的同层结点（孩子之间互称兄弟）堂兄弟——即双亲位于同一层的结点（但并非同一双亲）祖先——即从根到该结点所经分支的所有结点子孙——即该结点下层子树中的任一结点
树的基本术语
B
A
CF
G
HF
DI
J
结点——即树的数据元素结点的度——结点挂接的子树数
（有几个直接后继就是几度，亦称“次数”）
K
E
L
结点的层次——从根到该结点的层数(根结点算第一层)终端结点——即度为0的结点，即叶子
分支结点——即度不为0的结点(也称为内部结点)
树的度——所有结点度中的最大值(Max{各结点的度})
树的深度——指所有结点中最大的层数(Max{各结点的层次})(或高度)
问：右上图中的结点数＝13；树的度＝3；树的深度＝4
树形结构的逻辑特征
•树形结构的逻辑特征可用树中结点之间的父子关系来描述：
–树中任一结点都可以有零个或多个直接后继(即孩子)结点，但至多只能有一个直接前趋(即双亲)结点。
–树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点。
–祖先与子孙的关系是对父子关系的延拓，它定义了树中结点之间的纵向次序。
–有序树中，同一组兄弟结点从左到右有长幼之分。–对这一关系加以延拓，规定若k1和k2是兄弟，且k1在k2的左边，则kl的任一子孙都在k2的任一子孙的左边，那么就定义了树中结点之间的横向次序。
树和线性结构的比较
线性结构树结构存在唯一的没有前驱的首存在唯一的没有前驱的根元素结点存在唯一的没有后继的尾存在多个没有后继的叶子元素可见，由于线性结构是一个序列，元素之间存在的是一对一的关系，其余元素均存在唯一的前而树是一个层次结构，元素之间其余元素均存在唯一的前驱(双亲)结点和多个后继存在的是一对多的关系。驱元素和唯一的后继元素(孩子)结点树的五种表示方法
•••••
图形表示法
嵌套集合表示法嵌套括号表示法凹入表示法二元组表示法
图形表示法
计算机学院根应用系软件系信息系…………教师学生其他人员BACD2002级2003级2004级2005级子树GJEFI叶子HK嵌套集合表示法
嵌套括号表示法
( A( B( E ( K, L ), F ), C( G ), D( H ( M ), I, J ) ) 约定：
根作为由子树森林组成的表的名字写在表的左边
凹入表示法又称目录表示法二元组表示法
树的二元组表示(D，S)
D = { A，B，C，D，E，F，G，H，I，J}S = { R }
R = { •若树中存在一个结点序列k1，k2，…，ki，使得ki是k(1≤i ABCDEFGHIJ树的抽象数据类型 ADT Tree{ 数据对象：D是具有相同特性的数据元素的集合。 数据关系： 若D 为空集，则称为空树； 若D 中仅含一个数据元素，则关系R为空集；否则R={H}， (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 当n>1时，其余数据元素可分为m(m>0) 个互不相交的(非空)有限集T1,T2,…,Tm, 其中每一个子集本身又是一棵符合本定义的树，称为根root 的子树， 每一棵子树的根xi 都是根root 的后继，即 } 树的基本操作 {结构初始化} InitTree(&T); 操作结果：构造空树T。 CreateTree(&T,definition); 初始条件：definition 给出树T的定义。操作结果：按definition构造树T。 {销毁结构} DestroyTree(&T); 初始条件：树T 存在。操作结果：销毁树T。 {引用型操作} TreeEmpty(T); 初始条件：树T存在。 操作结果：若T为空树，则返回TRUE，否则返回FALSE。 树的基本操作 {引用型操作} TreeDepth(T); 初始条件：树T存在。 操作结果：返回T的深度。 Root(T); 初始条件：树T存在。操作结果：返回T的根。 Value(T, cur_e); 初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。 Parent(T, cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e是T的非根结点，则返回它的双亲，否则返回\"空\"。 树的基本操作 {引用型操作} LeftChild(T, cur_e); 初始条件：树T存在，cur_e是T 中某个结点。 操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子， 否则返回\"空\"。RightSibling(T, cur_e); 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回\"空\"。TraverseTree(T, visit()); 初始条件：树T存在，visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。 一旦visit()失败，则操作失败。 树的基本操作 {加工型操作} Assign(T, cur_e, value); 初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。ClearTree(&T); 初始条件：树T存在。 操作结果：将树T清为空树。 InsertChild(&T, &p, i, c); 初始条件：树T 存在，p指向T中某个结点，1≤i≤p所指结点的度＋1， 非空树c与T不相交。 操作结果：插入c为T中p所指结点的第i棵子树。DeleteChild(&T, &p, i); 初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。操作结果：删除T中p所指结点的第i棵子树。 二叉树 •二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。 二叉树的定义 •二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。•二叉树的特点： –一个结点至多有两棵子树，即二叉树每个结点度小于等于2；–子树有左右之分； –左、右子树不能颠倒——有序树； 二叉树的抽象数据类型 ADT BinaryTree{ 数据对象：D是具有相同特性的数据元素的集合。 数据关系： 若D 为空集，则称为空二叉树；否则关系R={H}： (1) 在D 中存在唯一的称为根的数据元素root，它在关系H 下无前驱； (2) D 中其余元素必可分为两个互不相交的子集L 和R，每一个子集都是一棵符合本定义的二叉树，并分别为root 的左子树和右子树。如果左子树L 不空，则必存在一个根结点，它是root 的\"左后继\"( } 二叉树的五种基本形态 •二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。 问：具有3个结点的二叉树可能有几种不同形态？ 有5种 二叉树不是树的特例 •二叉树并非是树的特殊情形，它们是两种不同的树型结构。 –二叉树结点的子树分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。 –如果根结点只有一棵子树，那么对树而言，它就是一个独生子，无次序可分，但对二叉树而言，必须明确区分它是根的左子树还是根的右子树，两者将构成不同的二叉树。 二叉树的性质 •性质1：二叉树第i层上的结点数目最多为2i-1(i≥1)。 证明：用数学归纳法。归纳基础：当i=1时，整个二叉树只有一根结点，此时2i-1=20=1，结论成立。归纳假设：设i=k时结论成立，即第k层k-1上结点总数最多为2个。1个结点？现证明当i=k+1时，结论成立：提问：第i层上至少有因二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即2×2k-1=2(k+1)-1，故结论成立。二叉树的性质 •性质2：深度为k的二叉树至多有2k-1个结点(k≥1)。 证明： 因深度为k的二叉树，其结点总数的最大值是将二叉树中每层结点的最大值相加，所以深度为k的二叉树的结点总数至多为： 第i层上的最大结点个数2i1i1kki121k故结论成立 二叉树的性质 •性质3：对任意一棵二叉树T，若叶结点数为n0，而其度为2的结点数为n2，则n0=n2+1。 物理意义：叶子数＝2度结点数＋1证明： ∵二叉树中全部结点数n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数)又∵二叉树中全部结点数n＝B+1(总分支数＋根结点) （除根结点外，每个结点必有一个直接前趋，即一个分支） 而总分支数B=n1+2n2(1度结点必有1个直接后继，2度结点必有2个)三式联立可得：n0+n1+n2=n1+2n2+1,即n0=n2+1 课堂练习 1. 树Ｔ中各结点的度的最大值称为树Ｔ的D Ａ) 高度 Ｂ) 层次 Ｃ) 深度 。 Ｄ) 度 2.深度为Ｋ的二叉树的结点总数，最多为C个。Ａ)２k-1 Ｂ) log2k Ｃ) ２k－１ Ｄ)２k 3. 深度为9的二叉树中至少有C个结点。 Ａ)２9 Ｂ)２8 Ｃ)９ Ｄ)２9－1 满二叉树(FullBinaryTree) •一棵深度为k且有2k-1个结点的二又树称为满二叉树。 •满二叉树的特点： –每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。 –满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。ABDEFCG完全二叉树(Complete BinaryTree) •若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。•特点： –满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 –在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 –在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。 ABDEFCGDABEC(a) A(b) 满二叉树和完全二叉树有什么区别？(a)满、完全二叉树(b)完全二叉树答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-EGD1层是满的，但最底层却允许在右边缺少连续若干个结点。满(c)不是完全二叉树BC二叉树是完全二叉树的一个特例。(c)二叉树的性质 •性质4：具有n个结点的完全二叉树的深度为log2n1证明： 设n个结点的完全二叉树的深度为k，由性质2可知，k-1层满二叉树的结点总数为：n1=2k-1-1k层满二叉树的结点总数为：n2=2k-1 显然n1 •性质5：对于有n个结点的完全二叉树，按照从上到下、从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有： –如i=1，则序号为i的结点是根结点，无双亲结点；如i>1，则序号为i的结点的双亲结点序号为i/2–如2i>n，则序号为i的结点无左孩子；如2i≤n，则序号为i的结点的左孩子结点的序号为2i。 –如2i＋1>n，则序号为i的结点无右孩子；如2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1。 可根据归纳法证明。 二叉树的抽象数据类型 ADT BinaryTree { 数据对象：D 是具有相同特性的数据元素的集合。 数据关系： 若D 为空集，称BinaryTree 为空二叉树；否则关系R={H}： (1) 在D 中存在唯一的称为根的数据元素root，它在关系 H 下无前驱； (2) D 中其余元素必可分为两个互不相交的子集L 和R，每 一个子集都是一棵符合本定义的二叉树，并分别为root 的左子树和右子树。如果左子树L 不空，则必存在一个根结点，它是root 的\"左后继\"( 二叉树的基本操作 {结构初始化} InitBiTree(&T); 操作结果：构造空二叉树T。 CreateBiTree(&T, definition); 初始条件：definition给出二叉树T的定义。操作结果：按definition构造二叉树T。 {销毁结构} DestroyBiTree(&T); 初始条件：二叉树T存在。操作结果：销毁二叉树T。 {引用型操作} BiTreeEmpty(T); 初始条件：二叉树T存在。 操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE。 二叉树的基本操作 {引用型操作} BiTreeDepth(T); 初始条件：二叉树T存在。操作结果：返回T的深度。 Root(T); 初始条件：二叉树T存在。操作结果：返回T的根。 Value(T, e); 初始条件：二叉树T存在，e 是T中某个结点。操作结果：返回e的值。 Parent(T, e); 初始条件：二叉树T 存在，e是T中某个结点。 操作结果：若e是T的非根结点，则返回它的双亲，否则返回\"空\"。 二叉树的基本操作 {引用型操作} LeftChild(T, e); 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的左孩子。若e无左孩子，则返回\"空\"。RightChild(T, e); 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的右孩子。若e无右孩子，则返回\"空\"。LeftSibling(T, e); 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的左兄弟。若e是其双亲的左孩子或无左兄弟， 则返回\"空\"。RightSibling(T, e); 初始条件：二叉树T存在，e是T的结点。 操作结果：返回e的右兄弟。若e是其双亲的右孩子或无右兄弟， 则返回\"空\"。 二叉树的基本操作 {引用型操作} PreOrderTraverse(T, visit()); 初始条件：二叉树T存在，visit是对结点操作的应用函数。 操作结果：先序遍历T，对每个结点调用函数visit一次且仅一次。 一旦visit()失败，则操作失败。InOrderTraverse(T, vsit()); 初始条件：二叉树T存在，visit是对结点操作的应用函数。 操作结果：中序遍历T，对每个结点调用函数visit一次且仅一次。 一旦visit()失败，则操作失败。PostOrderTraverse(T, visit()); 初始条件：二叉树T存在，visit是对结点操作的应用函数。 操作结果：后序遍历T，对每个结点调用函数visit一次且仅一次。 一旦visit()失败，则操作失败。LevelOrderTraverse(T, visit()); 初始条件：二叉树T存在，visit是对结点操作的应用函数。 操作结果：层序遍历T，对每个结点调用函数visit一次且仅一次。 一旦visit()失败，则操作失败。 二叉树的基本操作 {加工型操作} ClearBiTree(&T); 初始条件：二叉树T存在。 操作结果：将二叉树T清为空树。 Assign(&T, &e, value); 初始条件：二叉树T 存在，e是T中某个结点。操作结果：结点e赋值为value。 InsertChild(&T, p, LR, c); 初始条件：二叉树T存在，p 指向T中某个结点，LR为0或1， 非空二叉树c与T不相交且右子树为空。 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。 p所指结点原有左或右子树成为c 的右子树。DeleteChild(&T, p, LR); 初始条件：二叉树T存在，p指向T中某个结点，LR 为0或1。操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。 用二叉树表示算术表达式 •在计算机中，可以用树结构来表示算术表达式。•用树来表示算术表达式的原则如下： ①表达式中的每一个运算符在树中对应一个结点，称为运算符结点。 ②运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）。③运算对象中的单变量均为叶子结点。 例：用二叉树表示算术表达式A / B * C * D + E ①表达式中的每一个运算符在树中对应一个结点，称为运算符结点。②运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）。 ③运算对象中的单变量均为叶子结点。 /A B +* EDC * 二叉树的存储结构 一、顺序存储结构 AT[0]一般不用[1]按二叉树的结点自上而下、[2]从左至右编号，用一组连续BC[3]的存储单元存储。 DEFG[4][5]HI[6][7][8]特点： [9]1. 结点间关系蕴含在其存储位置中 2. 浪费空间，适于存满二叉树和完全二叉树 ABCDEFGHI 二叉树的存储结构 问：顺序存储后能否复原成唯一对应的二叉树形状？答： 若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5） 例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必是D,右孩子必为E。 非完全二叉树的顺序结构 一律转为完全二叉树！ 方法很简单，将各层空缺处统统补上虚结点，其内容为空。 [1]A A [2]B[3]^B [4]C C [5]^[6]^D [7]^ E [8]D 缺点：①浪费空间；②插入、删除不便[9]^ …… 二叉树的常用存储结构是链表[16]E 二叉树的存储结构 二、链式存储结构 用二叉链表即可方便表示。一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始） 注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。 left_child data right_child dataleft_child right_child 二叉链表类型定义 二叉链表结点数据类型定义： Typedef Struct BitNode{ Elemtype data; struct BitNode *Lchild,*Rchild; //左、右孩子指针} BitNode *BitTree; 二叉链表存储举例 BTABCDA^B^C^D^^E^E优点：①不浪费空间；②插入、删除方便 三叉链表 •三叉链表中每个结点包含四个域： –数据域、双亲指针域、左指针域、右指针域 parent left_child data right_child dataleft_child right_child 三叉链表类型定义 三叉链表结点数据类型定义： Typedef Struct TriNode{ Elemtype data; struct BitNode *Lchild,*Rchild; //左、右孩子指针 struct BitNode *parent; //双亲指针} TriNode *TriTree; 二叉链表和三叉链表示举例 rootrootAABBCDCDEFEF二叉树 二叉链表 rootABCDEF三叉链表 二叉树的遍历 •遍历的定义：按某种顺序访问二叉树的每个结点，而且每个结点仅被访问一次。•访问的含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。•遍历的用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。 •遍历的方法：对每个结点的查看通常都是先左后右。 遍历的规则 二叉树由根、左子树、右子树构成，定义为D、L、RD、L、R的组合定义了六种可能的遍历方案：LDR, LRD, DLR, DRL, RDL, RLD若限定先左后右，则有三种实现方案： DLR LDR LRD先序遍历中序遍历后序遍历注：先、中、后的意思是指访问的结点D是先于子树出现还是后于子树出现。以根结点为参照系先序遍历（DLR）若二叉树非空 （1）访问根结点； （2）先序遍历左子树；（3）先序遍历右子树。 ABDC例：先序遍历右图所示的二叉树（1）访问根结点A （2）先序遍历左子树：即按DLR的顺序遍历左子树（3）先序遍历右子树：即按DLR的顺序遍历右子树先序遍历序列：A B D C 先序遍历: ABCD先序遍历序列：A B D CD L RAD L RD L RBCD L RD中序遍历（LDR）若二叉树非空 （1）中序遍历左子树（2）访问根结点 （3）中序遍历右子树 ABDC例：中序遍历右图所示的二叉树 （1）中序遍历左子树：即按LDR的顺序遍历左子树（2）访问根结点A （3）中序遍历右子树：即按LDR的顺序遍历右子树中序遍历序列：B D A C 中序遍历: AL D RABDCL D RBL D RCL D RD中序遍历序列：B D A C 后序遍历（LRD）若二叉树非空 （1）后序遍历左子树（3）后序遍历右子树（2）访问根结点 ABDC例：后序遍历右图所示的二叉树 （1）后序遍历左子树：即按LRD的顺序遍历左子树（3）后序遍历右子树：即按LRD的顺序遍历右子树（2）访问根结点A 后序遍历序列：D B C A 后序遍历: L R DABCD后序遍历序列：D B C A L R DL R DBCL R DDA例1： A先序遍历的结果是：中序遍历的结果是：ABDECD B E AC BC后序遍历的结果是： D E B C DE口诀： DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根 A 例2：用二叉树表示算术表达式 + *E*D /C A B 先序遍历结果+ * * / A B C D E—前缀表示法中序遍历结果A / B * C * D + E—中缀表示法后序遍历结果A B / C * D * E +—后缀表示法 层次遍历结果+ * E * D / C A B 例3：对下列所示的二叉树，分别写出前序、中序和后序遍历的序列 ABC(一) ABAB CABC(四) ABC(二) (三) C(五) 前序中序后序 (一)ABC(二)ABC(三)ABC(四)ABC(五)ABC CBACBA BCACBA BACBCA ACBCBA ABCCBA 例4：将下面的二叉树以二叉链表形式存入计算机内。输入：二叉树的先序序列输出：二叉树的二叉链表 ABC E D 考虑1：输入结点时怎样表示无孩子？考虑2：以何种遍历方式来输入和建树？字符串输完后应当再加一特殊的结束符号以先序遍历最为合适，用空格字符表示无(让每个结点都能及时如$)，因为无孩子或指针为空法惟一表示结束。被连接到位。FG 将二叉树按先序遍历次序输入：A B CD EGF($) 输入序列：A B CD EGF($) ABC D EF G BTA ^ B^ C ^D^ E^ F ^^ G ^问题：用二叉链表法(l_child, r_child)存储包含n个结点的二叉树，结点的指针区域中会有多少个空指针？ 有n+1个！证明：用二叉链表存储包含n个结点的二叉树，结点 必有2n个链域(见二叉链表数据类型说明)。除根结点外，二叉树中每一个结点有且仅有一个双亲，意即每个结点地址占用了双亲的一个直接后继，n个结点地址共占用了n-1个双亲的指针域。也就是说，只会有n-1个结点的链域存放指针。 所以，空指针数目=2n-(n-1)=n+1个。 输入序列：A B CD EGF($)建树算法： StatusCreateBiTree(BiTree&T){scanf(“%c”,&ch); //构造二叉树T if(ch==‟$‟)exit;//建树完成if(ch==‟‟)T=NULL;//建空树else{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(overflow);T->data=ch; CreateBiTree(T->lchild);}returnOK; //生成根结点 //递归构造(遍历)左子树 CreateBiTree(T->rchild);//递归构造(遍历)右子树 }//CreateBiTree 遍历的递归算法 先序遍历二叉树中序遍历二叉树后序遍历二叉树 若二叉树为空，则若二叉树为空，则若二叉树为空，则空操作；否则：空操作；否则：空操作；否则：(1)访问根结点；(1)中序遍历左子树；(1)后序遍历左子树；(2)先序遍历左子树；(2)访问根结点；(3)后序遍历右子树；(3)先序遍历右子树；(3)中序遍历右子树；(2)访问根结点； 先序遍历算法 DLR(node*root){ if(root!=NULL)//非空二叉树{ printf(“%d”,root->data);//访问DDLR(root->lchild);//递归遍历左子树DLR(root->rchild);//递归遍历右子树} return(0);}//DLR 中序遍历算法 LDR(node*root){ if(root!=NULL){ LDR(root->lchild); printf(“%d”,root->data);LDR(root->rchild);} return(0);}//LDR 后序遍历算法 LRD(node*root){ if(root!=NULL){ LRD(root->lchild);LRD(root->rchild); printf(“%d”,root->data);} return(0);}//LRD 1.从前面的三种遍历算法可以知道：如果将printf语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。 ACB从虚线的出发点到终点的路径上，每个结点经过3次。第1次经过时访问，是先序遍历第2次经过时访问，是中序遍历第3次经过时访问，是后序遍历2.二叉树遍历的时间效率和空间效率时间效率:O(n)//每个结点只访问一次空间效率:O(n)//栈占用的最大辅助空间DEFG精确值：树深为k的递归遍历需要k+1个辅助单元中序遍历二叉树(非递归算法) bcbdaaadea b入栈 b退栈访问 d入栈 ecca退栈 访问 c e入栈 e 退栈c退栈 访问 访问 ad退栈访问 栈空 void InOrder ( BinTree T ) { stack S; InitStack( &S ); //递归工作栈BinTreeNode *p = T;//初始化 while ( p != NULL || !StackEmpty(&S) ) { if( p != NULL ) { Push(&S, p); p = p->leftChild; }else{ Pop(&S, p); //退栈printf( p->data) ; //访问根p = p->rightChild; } //if b} //while return ok;} //InOrderdce二叉树遍历应用举例 •例1：统计二叉树中叶子结点的个数 思路：若左右指针均空，必为叶子。可选用任何一种遍历算法查找叶子，将其统计并打印出来。DLR(node*root) //采用先序遍历的递归算法 {if(root!=NULL)//非空二叉树条件，等效于if(root) {if(!root->lchild&&!root->rchild)//是叶子结点则统计并打印{sum++;printf(\"%d\\n\DLR(root->lchild);}return(0);} //递归遍历左子树，直到叶子处； DLR(root->rchild);}//递归遍历右子树，直到叶子处； 二叉树遍历应用举例 •例2：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请画出这棵二叉树。 思路：①由后序遍历特征，根结点必在后序序列尾部(即A)；②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙(即BDCE)，其右部必全部是右子树的子孙(即FHG)；③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。BDCEA已知中序遍历：B D C E A F H GCBA已知后序遍历：D E C B H G F A AB F CD E （B D C E）（D C E） GH （F H G） 二叉树遍历应用举例 •例3：求二叉树的深度。思路： ①二叉树的深度(高度)为二叉树中结点层次的最大值。 ②设根结点为第1层的结点，所有h层的结点的左右孩子结点在h+1层，则可以通过遍历计算二叉树中每个结点的层次，其中最大值即为二叉树的深度。 int BitTreeDepth(BitTree T, int level, int &depth) { //T指向二叉树的根，level为T所指结点所在层次，//其初值为1，depth为当前求得的最大层次，其初值为0if(T) { if(level>depth) depth=level; //得到深度较大者 BitTreeDepth(T->Lchild, level+1, depth); //求左子树的深度BitTreeDepth(T->Rchild, level+1, depth); //求右子树的深度} else return(0); //如果是空树，则返回0 } 二叉树遍历应用举例 •例4：在二叉树上查询某个结点。思路： ①若二叉树为空树，则二叉树上不存在这个结点，返回FALSE；否则和根结点的元素进行比较，若相等，则找到，即刻返回指向该结点的指针和函数值TRUE，从而查找过程结束。 ②否则在左子树中进行查找，若找到，则返回TRUE。③否则返回在右子树中进行查找的结果。因为右子树上查找的结果即为整个查找过程的结果，即若找到，返回的函数值为TRUE，并且已经得到指向该结点的指针，否则返回的函数值为FALSE。 bool Locate (BiTree T, ElemType x, BiTree &p) { //若二叉树中存在和x 相同的元素，则p指向该结点并返回TRUE，// 否则p = NULL且返回FALSEif (!T){ p = NULL; return FALSE; //空树中不存在这样的结点}else { if (T->data==x){ p = T; return TRUE; //找到所求结点else } if (Preorder(T->Lchild,x,p)) return TRUE;//在左子树中找到所求结点else return(Preorder(T->Rchild,x,p)); //返回在右子树中查找的结果} // else} //Locate 二叉树的线索链表 •对二叉树进行遍历的过程即为沿着某一条搜索路径对二叉树中的结点进行一次且仅仅一次访问，换句话说，就是按一定规则将一个处于层次结构中的结点排列成一个线性序列之后进行依次访问，这个线性序列或是先序序列、或是中序序列或是后序序列，在这些线性序列中每个结点(除第一个和最后一个外)有且仅有一个直接前驱和直接后继(在不致于混淆的情况下，省去直接二字)。 •例如右图所示二叉树中的数据A元素E在先序序列中的前驱是D，后继是G；•而在中序序列中的前驱是G， 后继是H； •在后序序列中的前驱是H，后 继是B。 •显然，这种信息是在遍历的动 态过程中产生的，如果将这些 信息在第一次遍历时就保存起来，则在以后再次需要对二叉树进行遍历时就可以将二叉树视作线性结构进行访问操作了。BCDEFGHIJ 先序序列为：ABDEGHCFIJ中序序列为：DBGEHACIJF后序序列为：DGHEBJIFCA•二叉树的遍历是将二叉树中结点按一定规律线性化的过程。当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到在遍历序列中的前驱和后继信息。 如何得到前驱和后继信息？利用线索二叉树(Threaded Binary Tree) 如何预存这类信息？有两种解决方法：①每个结点增加两个域：fwd和bwd；存放前驱指针存放后继指针fwdlchilddatarchildbwd缺点：空间效率太低！②与原有的左右孩子指针域复用，充分利用那n+1个空链域。 lchilddatarchild规定： 1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继(即线索)。 问题：计算机如何判断是孩子指针还是线索指针？如何区别？为区别两种不同情况，特增加两个标志域： lchildLTagdata各1bitRTagrchild约定:当Tag域为0时,表示正常情况;当Tag域为1时,表示线索情况. 1 左(右)孩子前驱(后继)0 lchild域是指向结点的左孩子的指针lchild域是指向结点的前驱的左线索 0 rchild域是指向结点的右孩子的指针1 rchild域是指向结点的后继的右线索 有关线索二叉树的几个术语 •••••• 线索：指向结点前驱或后继的指针 线索链：用含Tag的结点样式所构成的二叉链表线索二叉树：加了线索的二叉树 前序线索二叉树：按前序遍历得到的二叉树中序线索二叉树：按中序遍历得到的二叉树后序线索二叉树：按后序遍历得到的二叉树 线索二叉树的类型说明 typedef enum PointerTag {link=0,thread=1}; typedef struct BiThrNode{ TElemType data; Struct BiThrNode *lchild, *rchild; //左右指针域PointerTag Ltag, Rtag; //左右标志域} BiThrNode，*BiThrTree； 对线索链表中结点的约定 •若该结点的左子树不空， –则lchild域的指针指向其左子树，且左标志域的值为指针Link； –否则，lchild域的指针指向其前驱，且左标志的值为线索Thread。 •若该结点的右子树不空， –则rchild域的指针指向其右子树，且右标志域的值为指针Link； –否则，rchild域的指针指向其后继，且右标志的值为线索Thread。 例：带了两个标志的某先序遍历结果如下表所示， 请画出对应的二叉树。LtagdataRtag 00AG00 1E0 1I1AGEIDCJHFB1D0 1J1 0H0 1C1 0F1 1B1 Tag=1表示线索Ltag=1表示前驱Rtag=1表示后继 二叉树的中序线索化 •以线索链表作存储结构，即以指向线索链表中头结点的指针表示二叉树。由于在线索链表中已经包含有遍历得到的访问次序序列的信息，则在线索链表中进行遍历可以递推进行。即首先找到遍历中应该访问的第一个结点，而后接着顺每个结点的后继依次进行访问。在此仅以中序线索链表为例进行讨论。 二叉树的线索化 •线索化：对二叉树以某种次序进行遍历并且加上线索的过程。 •按某种次序将二叉树线索化的实质是：按该次序遍历二叉树，在遍历过程中用线索取代空指针。 –将空的lchild改为结点的直接前驱；–将空的rchild改为结点的直接后继。 –非空指针呢？仍然指向孩子结点(称为正常情况) 例：下面(a)图中所示的线索二叉树，其线索链表如图(b)所示中序遍历结果：CBDAFHGIE 图中的实线表示指针，虚线表示线索。 结点C的左线索为空，表示C是中序序列的开始结点，无前驱；结点E的右线索为空，表示E是中序序列的终端结点，无后继； 线索二叉树中，一个结点是叶结点的充要条件为：左、右结点标志均是1。 •线索化过程就是在遍历过程中修改空指针的过程例1：画出以下二叉树对应的中序线索二叉树。 解：对该二叉树中序遍历的结果为:H,D, I, B, E, A, F, C,G所以添加线索应当按如下路径进行： rootA悬空？NULLB悬空？NULLHCDEFGIABDEF为避免悬空态，应增设一个头H结点CG孩子指针前趋指针后继指针线索二叉树悬空？NULL0D10B0中序遍历序列：D,B,H,E,A,F,C,G0A00C00E11F1悬空？NULL1G01H1线索链表图示为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点。约定： 头结点的lchild域：存放线索链表的根结点指针头结点的rchild域：中序序列最后一个结点指针中序序列第一个结点的lchild域指向头结点；中序序列最后一个结点的rchild域指向头结点。 头结点010A00B01D10E10C01F11G11H1头结点010A0②①1D1③0B00E11H10C01F11G1中序遍历序列：D,B,H,E,A,F,C,G 如何在中序线索链表上进行遍历，关键问题有二：一是如何找到访问的第一个结点？ 二是如何找到每个结点在中序序列中的后继？ 头结点010A00B01D10E11H10C01F11G1中序遍历序列：D,B,H,E,A,F,C,G 在中序线索链表中如何找到中序序列中的第一个结点？ ①中序遍历访问的第一个结点必定是其左子树为空的结点； ②若根结点没有左子树，则根结点即为中序遍历访问的第一个结点； ③若根结点的左子树不空，则访问的第一个结点应该是其左子树中最左下结点，即从根结点出发，顺指针lchild找到其左子树直至某个结点的指针lchild为线索止，该结点必为中序序列中的第一个结点。如上图所示的结点D。 头结点010A00B01D10E11H10C01F11G1中序遍历序列：D,B,H,E,A,F,C,G 如何在中序线索链表中找结点的后继？ ①若结点没有右子树，即结点的右指针类型标志Rtag为Thread，则指针rchild所指即为它的后继，如上图所示的结点D、结点G等。 ②若结点有右子树，则它的后继应该是其右子树中访问的第一个结点。和找二叉树的第一个结点一样，就应该从它的右子树根出发，顺指针lchild直至没有左子树的结点为止，该结点即为它的后继。如上图所示的结点B的后继为结点H。 线索二叉树的遍历 •在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历。•基本步骤： –p=Thead->lchild; p指向线索链表的根结点；–若线索链表非空，循环： •循环，顺着p左孩子指针找到最左下结点；访问之 •若p所指结点的右孩子域为线索，p的右孩子结点即为后继结点循环：p=p->rchild；并访问p所指结点；（在此循环中，顺着后继线索访问二叉树中的结点） •一旦线索“中断”，p所指结点的右孩子域为右孩子指针，p=p->rchild，使p指向右孩子结点； –返回OK；结束 void InOrderTraverse_Thr(BiThrTree Thead,void (*Visit)(ElemType e)){ //Thead指向中序线索链表中的头结点，头结点的左指针Lchild//指向二叉树的根结点，头结点的右线索Rchild指向中序遍历//访问的最后一个结点。本算法对此二叉树进行中序遍历，对//树中每个数据元素调用函数Visit进行访问操作p = Thead->lchild;//p指向二叉树的根结点while (p!= Thead) { //空树或遍历结束时，p==Thead while (p->LTag==Link) p = p->lchild;Visit(p->data);//访问其左子树为空的结点while (p->RTag==Thread && p->rchild!=Thread) { p = p->rchild; Visit(p->data);//访问\"右线索\"所指后继结点} // while p = p->rchild; // p 进至其右子树根} // while } // InOrderTraverse_Thr 在中序线索二叉树中找结点的前驱 •根据中序线索二叉树的概念和存储结构可知，对于结点p： –当p->Ltag=1时，p->lchild指向p的前驱。–当p->Ltag=0时，p->lchild指向p的左孩子。 •由中序遍历的规律可知，作为根p的前驱结点，它是中序遍历p的左子树时访问的最后一个结点，即左子树的最右下端结点。 void InPre(Struct BiThrnode *p, Struct BiThrnode &pre){ // 在中序线索二叉树中查找p的前驱, 并用pre指针返回结果if(p->Ltag==1) pre= p->lchild; //直接利用线索else // 在p的左子树中查找“最右下端”结点{ q= p->lchild; while (q->Rtag==0) q=q->rchild; pre=q;}//else} //InPre 在中序线索二叉树中找结点的后继 •对于结点p，要找其后继结点： –当p->Rtag=1时，p->rchild即为p的后继结点；–当p->Rtag=0时，说明p有右子树，此时p的后继结点即为其右子树的最左下端的结点。 void InSucc(Struct BiThrnode *p, Struct BiThrnode & succ) { //在中序线索二叉树中查找p的后继结点，用succ指针返回结果if (p->Rtag==1) succ= p-> rchild; //直接利用线索else//在p的右子树中查找“最左下端”结点{ q= p->rchild; while (q->Ltag==0) q=q->lchild ; succ=q; } //else} //InSucc 结论 •由上述讨论可知：对于非线索二叉树，仅从*p出发无法找到其中序前趋(或中序后继)，而必须从根结点开始中序遍历，才能找到*p的中序前趋(或中序后继)。线索二叉树中的线索使得查找中序前趋和中序后继变得简单有效。 线索链表的生成 •由于线索链表上保存的是遍历过程中得到的前驱和后继的信息，显然，线索链表应该在遍历过程中建立，即在遍历过程中改变二叉链表中结点的空指针以及相应的指针类型标志。若结点没有左子树，则令其左指针指向它的前驱并将左指针类型标志改为Thread，若结点没有右子树，则令它的右指针指向它的后继并将右指针类型标志改为Thread。为了获取前驱的信息，需要在遍历过程中添加一个指向其前驱的指针pre。 由此建立线索链表的过程即为将遍历过程中对结点进行下列访问操作(指针p指向当前访问的结点，pre指向在它之前刚刚访问过的结点)：if (!pre->Rchild) { pre->RTag = Thread;pre->rchild = p;} if (!p->lchild) { p->LTag = Thread;p->lchild = pre;} pre = p; void InThreading(BiThrTree p，BiThrTree& pre) { // 对p 指向根结点的二叉树进行中序遍历，遍历过程中进行\"中序线索// 化\"。若p 所指结点的左指针为空，则将它改为\"左线索\"，若pre// 所指结点的右指针为空，则将它改为\"右线索\"。指针pre 在遍历// 过程中紧随其后，即始终指向p 所指结点在中序序列中的前驱。if (p) { InThreading(p->lchild, pre);// 对左子树进行线索化if (!p->lchild) { p->LTag = Thread; p->lchild = pre; }// 建前驱线索if (!pre->rchild){ pre->RTag = Thread; pre->rchild = p;}// 建后继线索pre = p;// 保持pre 指向p 的前驱InThreading(p->rchild, pre);// 对右子树进行线索化} // if } // InThreading void InOrderThreading(BiThrTree &Thead, BiThrTree BT) { // BT为指向二叉树根结点的指针，由此二叉链表建立二叉树// 的中序线索链表，Thead 指向线索链表中的头结点。BiThrTree pre; if (!(Thead = new BiThrNode)) exit (1); // 存储分配失败Thead->LTag = Link; Thead->RTag =Thread;// 建头结点Thead->Rchild = Thead;// 右指针回指if (!BT) Thead->Lchild = Thead; // 若二叉树空，则左指针回指else { Thead->Lchild = BT; pre = Thead;InThreading(BT, pre); // 中序遍历进行中序线索化pre->Rchild = Thead; pre->RTag = Thead; // 对中序序列中最后一个结点进行线索化 Thead->Rchild = pre; // 建非空树的头结点的\"右线索\"} // else } // InOrderThreading 树和森林 •••• 树的存储结构 树和二叉树的转换森林 树和森林的遍历 树的存储结构 •树的存储结构：在树中，每个结点既可能有孩子也可能有双亲，所以既可以通过保存每个结点的孩子结点位置来表示结点之间的结构关系，也可以通过保存每个结点的双亲结点位置来表示结点之间的结构关系。 •四种常用的表示方法： –––– 双亲表示法孩子表示法 双亲孩子表示法孩子兄弟表示法 双亲表示法 •双亲表示：通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系•以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。 •每个结点有两个域： data域-----存放结点的信息； parent域-----存放该结点双亲结点的位置． Adata 0 1 2 3 4 5 6 BCDABCDEFGparent-10EFG00113特点:(1)便于涉及双亲的操作； (2)求结点的孩子时需要遍历整棵树。 用双亲表示实现的树定义 #define MaxSize//最大结点个数typedef struct //树结点定义{ TElemType data; int parent; //双亲位置域} TreeNode; typedef struct //树结构{ TreeNode Nodes[MaxSize]; int r, n; //根的位置和结点数}PTree 孩子表示法 •孩子表示法：通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。•两种表示方法： –顺序存储–链式存储 孩子表示法(顺序存储) #define MAX_TREE_SIZE 100 //最大结点个数typedef struct PTNode //树结点定义{ TElemType data; int child1; //第1个孩子位置域int child2; //第2个孩子位置域...... int childd; //第d个孩子位置域}PTNode; typedef struct //树结构{ PTNode nodes[MAX_TREE_SIZE];int n; //结点数}PTree; 孩子表示法举例 0R 1 2 3 数组下标:R1A 4 5 0 2B 0 0 0 CAB3C 6 0 0 D 0 0 0 4FDE5E 0 0 0 F 7 8 9 6HGK7G 0 0 0 H 0 0 0 8* 便于涉及孩子的操作；求双亲不方便；* 采用同构的结点，空间浪费。9K 0 0 0 孩子表示法(链式存储) •让每个结点的子树根构成一个线性表，以链表作它的存储结构，令其头指针和结点的数据元素构成一个结点，并将所有这样的结点存放在一个地址连续的存储空间里，所构成的树的存储结构称为树的孩子链表(链式存储)。 •注意，孩子结点中的子树根只存放该结点在一维数组中的下标。由于整个结构无法用一个指针表示，所以对整个树结构还需要给出结点数目和根的位置。 孩子链表类型定义 typedef struct CTNode //孩子结点{ int child; struct CTNode * next;}* ChildPtr;typedef struct{ TElemType data; //结点的数据元素ChildPtr firstchild; //孩子链表头指针}CTBox; typedef struct{ CTBox nodes[MAX_TREE_SIZE]; Int n, r; //结点数和根的位置；}CTree; 孩子链表存储表示举例 T.nodes[ ]; T.n=10; T.r = 0;数组下标:0R 1 2 R1A 4 5 ∧2B ∧ABC3C 6 ∧4D ∧FDE5E ∧6F 7 8 HGK7G ∧8H ∧* 便于涉及孩子的操作；* 求结点的双亲时不方便。9K ∧3∧9∧双亲孩子表示法 •在孩子表示法的头指针向量中，增加一项，用来表示该结点的双亲。 树的双亲孩子表示法类型定义#define MAX 100 struct node //孩子结点{ char child; struct node *NEXT;}; struct CPt_node { char data;int parent; struct node *NEXT; //孩子链表头指针} tree[MAX]; 双亲孩子表示举例 data parentnextR数组下标:0R -1 ADEBCFGHK* 便于涉及孩子的操作；* 求结点的双亲也方便。1234567891 4 6 ∧2 5 ∧3∧A 0 B 0 ∧C 0 D 1 ∧E 1 ∧F 3 G 6 ∧7 8 9∧H 6 ∧K 6 ∧孩子兄弟表示法(二叉链表示法) •用二叉链表作树的存贮结构。每个结点的左链域指向该结点的第一个孩子，右链域指向该结点的下一个兄弟结点。便于求孩子操作。 •这里的第一个和下一个都没有逻辑上的含义，只是在构造存储结构时自然形成的次序。 孩子兄弟表示法类型定义 typedef struct CSNode { ELemType data; struct CSNode *firstchild,*nextsibling;}CSNode, *CSTree; 结点结构 datafirstChildnextSibling孩子兄弟表示法示例 R∧ARADEGBC∧D∧B∧E∧F∧C∧F∧GHK∧H∧K∧ABBEFCGHDEICAFGHD(a)B∧EA∧I(b)CD∧由此可将树与二叉树对应起来∧F∧∧G∧此二叉链表既是树(a)的孩子兄弟表示又是二叉树(b)的二叉链表∧H∧I∧树与二叉树的转换 •二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。 树与二叉树转换方法 树二叉树 根 结点X的第一个孩子结点X紧邻的右兄弟 根结点X的左孩子结点X的右孩子 特点：一棵树转换成二叉树后，根结点没有右孩子。 树根 结点X 的第一个孩子结点X 紧邻的右兄弟 ABCDEFGHI二叉树根 结点X 的左孩子结点X 的右孩子 ABECFGDHI树与二叉树的对应关系 •树与二叉树均可由二叉链表作为存储结构，因此给定一棵树，用二叉链表存储，可唯一对应一棵二叉树，反之亦然。 将一棵树转换为二叉树的方法 •树中所有相邻兄弟之间加一条连线； •对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线； •以树的根结点为轴心，将整棵树顺时针旋转一定的角度。 •特点：根无右子树。 树到二叉树的转换 树ＡＢＣＥＤ二叉树 ＡＢＣＤＥＡＢＣＥＤＡＢＣＥＤＡ树 ＢＡＣＤＥｂＣＤＥ（１）孩子兄弟法（２）顺时针转４５度Ａ∧∧∧∧∧Ａ∧ＢＣＢ∧ＣＥ∧Ｄ∧ Ｄ ∧ ∧ Ｅ ∧ 解释：B是A的第一个孩子，C、E是B的兄弟，D是C的第一个孩子。 解释：Ｂ是Ａ的左孩子，Ｃ是Ｂ的右孩子。 森林 •森林：若干棵树的集合 •森林中树的根看成兄弟，可用树的孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；可用树的遍历方法对森林进行遍历。 AJBEFCGHDIKLNOMP包含两棵树的森林 森林转换为二叉树的方法 •将森林中的每棵树转换成相应的二叉树；•第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。 •树和森林都可以转换为二叉树，不同是： –树转换成的二叉树, 其根结点必无右孩子，而森林转换后的二叉树，其根结点有右孩子。 森林转换为二叉树的过程 T1AT2FIKT3HJBCDGABCDGEFH3棵树的森林EIT1T2T3 KJHFAGBI森林的二叉树表示CKJD各棵树的二叉树表示E转换规则(递归定义) 如果F={T1,T2,…,Tm}是森林,则可按如下规则转换成一棵二叉树B=(root,LB,RB)。 (1)若F为空，即m=0,则B为空树； (2)若F非空，则B的根root即为森林中第一棵树的根ROOT(T1)； B的左子树LB是从T1中根结点的子树森林F1={T11,T12,…,T1m1}转换而成的二叉树;其右子树RB是从森林F2={T2,T3,…,Tm}转换而成的二叉树。 二叉树转换成森林 •将一棵二叉树还原为树或森林，具体方法如下： 1.若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来。 2.删掉原二叉树中所有双亲结点与右孩子结点的连线。 3.整理由1、2两步所得到的树或森林。 ABCDEGFHIK(a)添加连线 JABCDFEGHIKJ(a)添加连线 ABCDFEGHIKJ(b)删除右孩子结点的连线 ABBACDEGFHCDEGFHIK(a)添加连线 IJHIKJKJ(b)删除右孩子结点的连线 ABCDFG(c)整理 E转换规则(递归定义) 如果B=(root,LB,RB)是一棵二叉树,则可按如下规则转换成森林F={T1,T2,…,Tm}：(1)若B为空，则F为空； (2)若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root； T1中的根结点的子树森林F1是由B的左子树LB转换而成的森林; F中除T1之外其余树组成的森林 F„={T2,T3,…，Tm}是由B的右子树RB转换而成的森林。 树和森林的遍历 •和二叉树的遍历类似，树的遍历问题亦为，从根结点出发，对树中各个结点进行一次且仅进行一次访问。 •对树进行遍历可有两条搜索路径：一条是从左到右（这里的左右指的是在存储结构中自然形成的子树之间的次序），另一条是按层次从上到下。•对树进行从左到右遍历，由对根的访问时机不同，有两种方式： –先根遍历–后根遍历 树的先根次序遍历 •当树非空时： –访问根结点；B–依次先根遍历根的各棵子树。 EF树先根遍历：ABEFCDG 对应二叉树前序遍历：ABEFCDG树的先根遍历结果与其对应二叉树 B表示的前序遍历结果相同。 树的先根遍历可以借助对应二叉树E的前序遍历算法实现。 ACGAD•••• CDGF树的后根次序遍历 •当树非空时： –依次后根遍历根的各棵子树；B–访问根结点。 EF树后根遍历：EFBCGDA 对应二叉树中序遍历：EFBCGDA树的后根遍历结果与其对应二叉树 B表示的中序遍历结果相同。 树的后根遍历可以借助对应二叉树E的中序遍历算法实现。 ACGAD•••• CDGF森林的两种遍历方法 一、先序遍历森林：若森林非空，则 （1）访问森林中第一棵树的根结点； （2）先序遍历第一棵树的根结点的子树森林；（3）先序遍历除去第一棵树之后的森林。二、中序遍历森林：若森林非空，则 （1）中序遍历第一棵树的根结点的子树森林；（2）访问森林中第一棵树的根结点； （3）中序遍历除去第一棵树之后的森林。 ABCDGEFHJIKL包含3棵树的森林如图森林的先序遍历序列为：ABCDEFGHIJKL ABCDGEFHJIKL包含3棵树的森林如图森林的中序遍历序列为：BCDAGHFEJLKI 最优树的定义 ••••••例 24 5 6 最优树，又称赫夫曼树(Huffman Tree)是一类带权路径长度最短的树。结点的权：根据应用的需要赋予树中结点的一个有某种意义的值；路径：从一个结点到另一个结点之间的若干个分支序列；路径长度：从一个结点到另一个结点路径上的分支数目；结点的路径长度：从根到该结点的路径长度； 树的路径长度：从树根到每一结点的路径长度之和；一般记为PL。 1 3 7 ⑴-⑵-⑸为结点1到5之间的路径，其路径长度为2， 树的路径长度PL=l12 +l13+l14 +l15+l16 +l17 =1+1+2+2+2+2=10 最优树的定义(续) •在结点数相同的条件下，完全二叉树是路径长度最短的二叉树； •结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积； •树的带权路径长度=树中所有叶子结点的带权路径长 n度之和，通常记作： WPLwilii1其中：n表示叶子结点的数目 Wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。 树的带权路径长度也称为树的代价。 例：下图中的三棵二叉树，都有5个叶子且带相同权值5、6、2、9、7，它们的带权路径长度分别为： 2562579679(a) (b) (a)WPL=7*3+9*3+5*2+6*2+2*2 = 74(b)WPL=2*1+6*3+7*4+9*4+5*2 = 94(c)WPL=6*2+7*2+5*3+2*3+9*2 = 65 67952(c) 赫夫曼树的概念 •赫夫曼树：假设有n个权值(w1, w2, … , wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个wi作为它的权值。则带权路径长度最小(即代价最小)的二叉树称为赫夫曼树，或最优二叉树。 2457WPL = 2*2+ WPL = 2*1+ WPL = 7*1+4*2+5*2+ 4*2+5*3+ 5*2+2*3+7*2 = 36 7*3 = 46 4*3 = 3527455724带权路径 长度达到最小 赫夫曼树的特点 •叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树； •最优二叉树中，权越大的叶子离根越近；•最优二叉树的形态不唯一，WPL最小。 要使二叉树WPL小,就须在构造树时, 将权值大的结点靠近根。 赫夫曼树的构造过程 (1)根据给定的n个权值{w1,w2,…,wn}，构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右子树均为空。(2)在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和。(3)在F中删除这两棵树，同时将新得到的二叉树加入F中。 (4)重复(2)和(3)，直到F只含一棵树为止。这棵树便是赫夫曼树。 举例霍夫曼树的构造过程 F : {7} {5} {2} {4}7524初始 F : {7} {11} 1175624合并{5} {6} F : {7} {5} {6}75624合并{2} {4} 1871156{7} {11}24F : {18} 合并应用举例 •在求某些判定问题时，利用哈夫曼树获得最佳判定算法。•例：编制一个将百分制转换成五分制的程序。 最直观的方法是利用if语句来实现。可用二叉树描述判定过程。a 60不及格及格中等a 70a 80a 90良好优秀考试成绩分布表 [0, 60 ) [60, 70 ) [70, 80 ) [80, 90 ) [90, 100 ) 不及格 0.10 及格 0.15 中 0.25 良 0.35 优 0.15 判定树 <<60?<0.150.250.35WPL = 0.10*1+0.15*2+0.25*3+0.35*4+0.15*4 = 3.15 转换10000个分数所需的总比较次数= 10000 3.15 = 31500 ≥0.10<70?<≥<80?<≥<90?≥0.15最佳判定树 <<80?≥≥<<0.10<60?<70?≥<<90?≥0.250.150.350.15WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2 = 0.3+0.45+0.5+0.7+0.3 = 2.25 转换10000个分数所需的总比较次数= 10000 2.25 = 22500 赫夫曼编码 •问题的提出： –通讯中常需要将文字转换成二进制字符串电文进行传输。文字电文，称为编码。 –反之，收到电文后要将电文转换成原来的文字，电文文字，称为译码。 •哈夫曼编码：电文尽可能短的编码 霍夫曼编码的基本思想是—— 出现概率大的信息用短码，概率小的用长码,最小冗余 例如：需将文字ABACCDA转换成电文。文字中有四种字符，用2位二进制便可分辨。 编码方案1： A B C D00 01 10 11则上述文字的电文为：00010010101100译码时，只需每2位一译即可。 共14位。 特点：等长等频率编码，译码容易，但电文不一定最短. A的编码是B的前缀编码方案2： A B C D0 00 1 01采用不等长编码，让出现次数多的字符用短码。 则上述文字的电文为：000011010共9位。 但无法译码，将产生二义性。它既可译为BBCCACA，也可译为AAAACCDA等。 编码方案3： A B C D0 110 10 111任何字符编码都不是其它字符编码的前缀：前缀编码 使用频率高的字符用短的编码，使用频率低的字符用较长的编码。 采用不等长编码，让出现次数多的字符用短码，且任一编码不能是另一编码的前缀。 则上述文字的电文为：0110010101110所得的译码是唯一的。 共13位。 二叉树与前缀编码 •可以利用二叉树来设计前缀编码，约定叶结点表示字符。从根结点到叶的路径中，左分支表示0，右分支表示1，从根结点到叶结点上的路径分支所组成的字符串作为该叶结点字符的编码。这样的编码一定是前缀编码。 •怎样保证这样的编码树所得到的编码总长度最小？ –Huffman编码树解决了这个问题。 Huffman树与前缀编码 •Huffman编码将代码与字母相联系 –代码长度取决于对应字母的相对使用频率或权；–它是一种不等长编码； –如果预计的字母出现频率与实际资料显示的情况相符，那么所得代码长度将明显小于用固定长度编码获得的长度。 赫夫曼编码的概念 设有n种字符，每种字符出现的次数为Wi,其编码长度为Li (i=1,2,．．．n)，则整个电文总长度为∑ Wi Li， 要得到最短的电文，即使得∑ Wi Li最小。 也就是以字符出现的次数为权值，构造一棵Huffman树，并规定左分支编码位0，右分支编码为1，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。用构造Huffman树编出来的码，称为Huffman编码。 赫夫曼编码为最优前缀码 •每个叶子字符ci的码长恰为从根到该叶子的路径长度li，平均码长(或文件总长)又是二叉树的带权路径长度WPL。而赫夫曼树是WPL最小的二叉树，因此编码的平均码长(或文件总长)亦最小。 •树中没有一片叶子是另一叶子的祖先，每片叶子对应的编码就不可能是其它叶子编码的前缀。即上述编码是二进制的前缀码。 根据最优二叉树构造赫夫曼编码 •具体做法: –用字符ci作为叶子，pi或fi做为叶子ci的权，构造一棵哈夫曼树，并将树中左分支和右分支分别标记为0和1； –将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码（也称赫夫曼编码）。 例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4，怎样编码才能使它们组成的报文在网络中传得最快？构造过程： (1)利用二叉树设计赫夫曼编码； (2)构造以d、i、a、n为叶子结点的二叉树；(3)将该二叉树所有左分枝标记0，所有右分枝标记1；(4)从根到叶子结点路径上的标记作为叶子结点所对应字符的编码。 明确：要实现Huffman编码，就要先构造Huffman树具体操作步骤： step1：对权值进行合并、删除与替换 ——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权 a. 初始 c. 合并{5} {6} b. 合并{2} {4} 圆框表示内结点（合并后的权值）方框表示外结点（叶子，字符）d. 合并{7} {11} step2：按左“0”右“1” 对Huffman树的所有分支编号 ——将Huffman树与Huffman编码挂钩 01d0 1i 01a Huffman编码结果：d=0, i=10, a=110, n=111WPL=1bit×7＋2bit×5+3bit(2+4)=35 n Huffman树和编码的特点 •由于Huffman树的WPL最小，说明编码所需要的比特数最少。 •Huffman树肯定没有度为1的结点； •一棵有n 0个叶子结点的Huffman树，共有2n0-1个结点（因为n=n0+n2=n0+n0-1=2n0-1) (P124 性质3)•Huffman编码时是从叶子走到根；而译码时又要从根走到叶子，因此每个结点需要增开双亲指针分量（连同结点权值共要开4个分量）； •用计算机实现时，顺序和链式两种存储结构都要用到。 Huffman树和编码的存储表示 typedef struct{ unsigned int weight；//权值分量（可放大取整） unsigned int parent，lchild，rchild；//双亲和孩子分量}HTNode，*HuffmanTree；//用动态数组存储Huffman树typedef char**HuffmanCode；//动态数组存储Huffman编码表 如何编程实现Huffman编码？ 参见教材P147先构造Huffman树HT，再求出N个字符的Huffman编码HC。Void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){*w存放n个字符的权值if (n<=1)return; m=2*n-1; //n 0个叶子的HuffmanTree共有2n0-1个结点； HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0单元未用for(p=HT,i=1; i<=n; ++i,++p,++w)*p={*w,0,0,0}; //给前n0个单元 初始化 for(；i<=m; ++i,++p)*p ={0,0,0,0}; //对叶子之后的存储单元清零for(i=n+1;i<=m; ++i){ //建Huffman树(从叶子后开始存内结点) Select(HT, i-1, s1, s2); //在HT[1…i-1]选择parent为0且weight最小的两个结点，其序号分别为S1和s2（教材未给出此函数源码）HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+ HT[s2].weight;} (续前)再求出n个字符的Huffman编码HC HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n个字符 编码的头指针向量（一维数组） cd=(char*) malloc(n*sizeof(char)); //分配求编码的工作空间(n) cd[n-1]=“\\0”; //编码结束符（从cd[0]~cd[n-1]为合法空间）for(i=1;i<=n;++i){ //逐个字符求Huffman编码start=n-1; //编码结束符位置 for(c=i,f=HT[i].parent; f!=0; c=f, f=HT[f].parent)//从叶子到根逆向求编码 if(HT[f].lchild==c) cd[--start]=“0”;else cd[--start]=“1”; HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字 符编码分配空间 strcpy(HC[i],&cd[start]); //从cd复制编码串到HC } free(cd); //释放工作空间}//HuffmanCoding 第4章基本知识结构图 树结点、终端结点(叶子)、非终端结点基本术语孩子、双亲、兄弟、祖先、子孙树的度有序树、无序树森林二叉树的定义二叉树的性质树二叉树二叉树的存储结构遍历二叉树线索二叉树树的存储结构树和森林森林与二叉树的转换树和森林的遍历赫夫曼树赫夫曼树(最优二叉树)赫夫曼编码 因篇幅问题不能全部显示，请点此查看更多更全内容