数据结构课件 第6章 树和二叉树

1、第六章 树和二叉树,6.1 树的类型定义 树（Tree）是n（n0）个结点的有限集。 在任意一棵非空树当中： （1）有且仅有一个特定的结点称为根结点（Root） （2）当n1时，其余结点可分为m（m0）个互不相交的有限集T1T2Tm，其中每一个集合本身又是一棵树，并且称为根的子树（sub tree）,树结构中的基本术语： 结点：包含一个数据元素及若干指向其子树的分支。 结点的度：结点拥有的子树的个数。 终端结点（叶子）：度为0的结点 非终端结点（分支）：度不为0的结点 树的度：树内各结点的度的最大值。 孩子：结点子树的根结点。 双亲：结点本身成为其孩子的双亲（父）结点。 兄弟：同一个双亲结点的

2、孩子之间互称为兄弟。 祖先：是从根到该节点所经分支上的所有结点。 子孙：以某结点为根的子树中的任意结点。,结点的层次：从根开始定义为第1层，根的孩子为第二层 堂兄弟：其双亲在同一层的结点。 树的深度（高度）：树中结点的最大层数。 有序树：树中结点的子树看成从左到右有序的（不能 互换），则称概树为有序树，否则称为无序树。 森林（forest）：是m（m 0）棵互不相交的树的集合。,树的抽象数据类型的定义如下： ADT Tree 数据对象：D是具有相同特性的数据元素的集合。 数据关系： 若 D 为空集，则称为空树； 若 D 中仅含一个数据元素，则关系R为空集； 否则 R=H， (1) 在D中存在唯

3、一的称为根的数据元素 root，它在关系H下无前驱； (2) 当n1时，其余数据元素可分为 m(m0) 个互不相交的(非空)有限集 T1,T2,Tm, 其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树，每一棵子树的根 xi 都是根 root 的后继，即 H,i=1,2,m。,基本操作： 结构初始化 InitTree( 初始条件：树 T 存在。 操作结果：销毁树 T。,引用型操作 TreeEmpty(T); 初始条件：树 T 存在。 操作结果：若 T 为空树，则返回 TRUE， 否则返回 FALSE。 TreeDepth(T); 初始条件：树T存在。 操作结果：返回T的深度。

4、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);

5、初始条件：树 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 存在，p 指向T中某个结点，

6、1ip 所指结点的度1，空树 c 与 T 不相交。 操作结果：插入 c 为 T 中 p 所指结点的第 i 棵子树。,DeleteChild( 初始条件：树 T 存在，p 指向 T 中某个结点， 1ip 指结点的度。 操作结果：删除 T 中 p 所指结点的第 i 棵子树。 ADT Tree,可从另一个角度来定义树。 定义森林为 m(m0) 棵互不相交的树的集合。 则可定义树是一个二元组 Tree = ( root,F ) 其中，root 是数据元素，称作树的根， F 是子树森林，记作 F=( T1,T2,Tm ), 其中 Ti=(ri,Fi) 为根 root 的第 i 棵(符合本定义的)子树，

7、当 m0 是，在树根和其子树森林之间存在下列关系： RF=|i=1,2,m, m0,树和线性结构作如下对照：,6.2 二叉树类型,6.2.1 二叉树的类型定义,二叉树的抽象数据类型定义如下: ADT BinaryTree 数据对象：D 是具有相同特性的数据元素的集合。 数据关系： 若 D 为空集，称 BinaryTree 为空二叉树； 否则 关系 R=H： (1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； (2) D 中其余元素必可分为两个互不相交的子集 L 和 R，每一个子集都是一棵符合本定义的二叉树，并分别为 root 的左子树和右子树。如果左子树 L 不空

8、，则必存在一个根结点XL，它是 root 的“左后继”(H)如果右子树 R 不空，则必存在一个根结点XR，为 root 的右后继(H)。,基本操作： 结构初始化 InitBiTree( 初始条件：二叉树 T 存在。 操作结果：销毁二叉树 T。,引用型操作 BiTreeEmpty(T); 初始条件：二叉树 T 存在。 操作结果：若T为空二叉树，则返回 TRUE， 否则返回 FALSE。 BiTreeDepth(T); 初始条件：二叉树 T 存在。 操作结果：返回 T 的深度。 Root(T); 初始条件：二叉树 T 存在。 操作结果：返回 T 的根。,Value(T, e); 初始条件：二叉树

9、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 中某

10、个结点。 操作结果：返回 e 的左兄弟。若 e 是其双亲的左 孩子或无左兄弟，则返回“空”。 RightSibling(T, e); 初始条件：二叉树 T 存在，e 是 T 的结点。 操作结果：返回 e 的右兄弟。若 e 是其双亲的右 孩子或无右兄弟，则返回空。,PreOrderTraverse(T, visit(); 初始条件：二叉树 T 存在，visit 是对结点操作的 应用函数。 操作结果：先序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。 InOrderTraverse(T, vsit(); 初始条件：二叉树 T 存在，visit 是对

11、结点操作的 应用函数。 操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit() 失败，则操作失败。,PostOrderTraverse(T, visit(); 初始条件：二叉树T存在，visit 是对结点操作的应用函数。 操作结果：后序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。 LevelOrderTraverse(T, visit(); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：层序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操

12、作失败。,加工型操作 ClearBiTree( 初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1，非空二叉树 c 与 T 不相交且右子树为空。 操作结果：根据 LR 为 0 或 1，插入 c 为 T 中 p 所指结点的左或右子树。p 所指结点原有左或右子树成为 c 的右子树。,DeleteChild( 初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1。 操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。 ADT BinaryTree,6.2.2 二叉树的几个特性,一、在二叉树的第 i 层上至多有 2i-1 个结点(

13、i1)。 利用归纳法容易证得此结论。 证明： 归 纳 基：i=1 时，只有一个根结点。 显然 2i-1=20=1 是对的。 归纳假设：设对所有的j(1ji)，命题成立， 即第j层上至多有 2j-1 个结点。 归纳证明： 由归纳假设“第 i-1 层上至多有 2i-2 个结点”， 又二叉树的每个结点的度至多为2， 则第 i 层上的最大结点数为第 i-1 层上最大结点数的2倍，即 22i-2=2i-1。 证毕。,二、深度为k的二叉树中至多含有 2k-1 个结点，(k1)。 证明： 由特性一可推出，深度为k的二叉树上最大结点数为,三、对任何一棵二叉树 T，如果其终端结点数为n0，度为2的结点数为n2，

14、 则 n0 =n2 + 1 证明： 由于二叉树中只有三种结点，假设n1为二叉树 T 中度为1的结点数，则二叉树中结点总数为 n= n0 + n1 + n2 再看二叉树中的分支数目。除了根结点外，其余结点都有一个分支进入，假设 B 为分支数，则 n=B+1。从另一角度看，这些分支是由度为1或2的结点射出的， 所以又有 B =n1 + 2 n2 即 n = n1 + 2 n2 + 1 综合以上和两个等式便可得到 n0=n2 + 1,有两种特殊形态的二叉树,满二叉树:若二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。 对满二叉树从上到下从左到右进行从1开始的编

15、号（如图所示），则任意一棵二叉树都可以和同深度的满二叉树相对比。,完全二叉树 :假如一棵包含 n 个结点的二叉树中每个结点都可以和满二叉树中编号为1至 n 的结点一、一对应，则称这类二叉树为完全二叉树。,显然一棵深度为h的完全二叉树中，前h-1层中的结点都是满的，且第 h 层的结点都集中在左边。显然，满二叉树本身也是完全二叉树。,四、具有n个结点的完全二叉树的深度为 log2n +1。 假设该完全二叉树的深度为 k，则根据特性二和完全二叉树的定义 2k-1 -1 n 2k -1 或 2k-1 n n，则编号为 i 的结点无左孩子（编号为 i 的结点为叶子结点）；否则其左孩子结点 lChild(

16、i) 的编号是 2i 。 (3) 如果 2i+1n，则编号为 i 的结点无右孩子；否则其右孩子结点 rChild(i) 的编号是结点 2i+1。,6.3 二叉树的存储表示,用一组地址连续的存储单元存储二叉树中的数据元素。,二叉树的顺序存储结构的定义如下： const MAXSIZE = 100; / 定二叉树中结点数的max为100 typedef struct ElemType dataMAXSIZE; / 存储空间基址(初始化时分配空间) int nodeNum; / 二叉树中结点数 SqBiTree; / 二叉树的顺序存储结构,6.3.1 顺序存储结构,对于完全二叉树，只要从根起按层序存

17、储即可。,根据二叉树的特性五，可推出顺序存储结构中“双亲”和“孩子”的关系： 假设 bt.datai 是完全二叉树上的一个结点， 若 2i+1Rchild, visit); / 先序遍历右子树 / if / Preorder,根据遍历递归算法递归工作栈的状态变化状况可以直接写出相应的非递归算法,算法6.2 void InorderTraverse (BiTree T，void(*visit)( BiTree ) / 采用二叉链表存储结构，visit是对数据元素操作的 /应用函数。中序遍历二叉树T的非递归算法，对每一 /个数据元素调用 visit InitStack(S);Push(S,T)；

18、while(!StackEmpty(S) while(GetTop(s,p) /空指针退栈 if (!StackEmpty(S),Pop(s,p); if(!visit(p-lchild) ) Return ERROR; Push(S,P-rchild); /if /while Return ok; /InorderTraverse,层次遍历右图的遍历序列为：ABCDTFGHIJ,6.4.2广度优先遍历二叉树（按层次遍历二叉树）,过程：先访问第1层，然后从左到右依次访问第2层两个节点，依此类推，当第i层访问完以后，在从左到右访问第i+1层的各个节点。,这里需要使用一个队列作为辅助的存储结构,在

19、遍历开始时，首先把根节点放入队列；然后每次从队列中取出队头元素进行处理，每处理一个结点时，按从左到右的顺序把它的所有子结点放入队列。这样，上层结点总是排在下一层结点的前面，从而实现了二叉树的广度优先遍历。,二叉树的广度优先遍历算法，同学们自己练习写下,6.5 线索二叉树,6.5.1 二叉树的线索链表,先序序列为： ABDEGHCFIJ 中序序列为： DBGEHACIJF 后序序列为： DGHEBJIFCA,如何保存在遍历过程中得到的前驱和后继信息？ 方法一：最简单的办法是在结点中增加两个指针域分别指向该结点的前驱和后继，但如此做将使存储结构的存储密度大大降低。 方法二：一个含 n 个结点的二叉

20、链表中有 n+1 个链域的值为NULL，可以利用这些空的指针域存放指向前驱和后继的信息，由此得到的二叉树的存储结构称作线索链表，其中指向前驱或后继的指针称作线索。,线索链表的结构定义如下： 二叉树的二叉线索链表存储表示 typedef enum PointerType Link=0, Thread=1 ; / 定义指针类型，以 Link 表示指针，Thread 表示线索 typedef struct BiThrNode ElemType data; struct BiThrNode *Lchild, *Rchild; / 左右指针 PointerType LTag, RTag; / 左右指针类

21、型标志 *BiThrTree;,若结点的左指针类型标志为“Link”， 则 Lchild 指向它的左子树根结点， 否则指向它的“前驱”； 若结点的右指针类型标志为“Link”， 则 Rchild 指向它的右子树根结点， 否则指向它的后继。,图二叉树的中序线索链表如下所示 （图中所有实线表示指针，虚线表示线索）,从图中可见，在线索链表中添加了一个头结点，头结点的左指针指向二叉树的根结点，其右线索指向中序序列中的最后一个结点，中序序列中的第一个结点的左线索和中序序列中的最后一个结点的右线索均指向头结点。这就好比将二叉树中所有结点置于一个双向循环链表之中，即可以从头结点出发，依照中序遍历的规则对二叉

22、树中的结点依次进行顺序（和中序序列相同的次序）访问，或逆序（和中序序列相反的次序）访问。,6.5.2 以中序线索链表为存储结构的中序遍历,如何在中序线索链表上进行遍历，关键问题有二： 一是如何找到访问的第一个结点？ 二是如何找到每个结点在中序序列中的后继？,由于线索链表上保存的是“遍历”过程中得到的前驱和后继的信息，显然，线索链表应该在遍历过程中建立，即在遍历过程中改变二叉链表中结点的“空指针”以及相应的“指针类型标志”。,6.5.2 以中序线索链表为存储结构的中序遍历,若结点没有左子树， 则令其左指针指向它的“前驱”并将左指针类型标志改为“Thread”， 若结点没有右子树， 则令它右指针指

23、向它的“后继”并将右指针类型标志改为“Thread”。 为了获取前驱的信息，需要在遍历过程中添加一个指向其前驱的指针 pre。,由此建立线索链表的过程即为将遍历过程中对结点进行下列“访问”操作( 指针 p 指向当前访问的结点，pre 指向在它之前“刚刚”访问过的结点)： if (!pre-Rchild) pre-RTag = Thread; pre-Rchild = p; if (!p-Lchild) p-LTag = Thread; p-Lchild = pre; pre = p;,6.5.3 线索链表的生成,算法6.10 void InThreading(BiThrTree p，BiThr

24、Tree / 对右子树进行线索化 / if / InThreading,算法6.11 void InOrderThreading(BiThrTree / 建非空树的头结点的右线索 / else / InOrderThreading 参看flash6-5-2,6.6 树和森林的存储表示,6.6.1 树的双亲表示法,结点中只设一个指向双亲的指针，并对无序树不需要设子树位置的标志。所有结点存储在一个地址连续的存储空间中。 例如，下图所示树的双亲链表如下所示 r=0 n=11,树的双亲链表存储表示 const MAX_TREE_SIZE = 100; typedef struct / 结点结构 Ele

25、mType data; int parent; / 双亲位置域 PTNode; typedef struct / 树结构 PTNode nodesMAX_TREE_SIZE; int r, n; / 根的位置和结点数 PTree;,6.6.2 树的孩子表示法,让每个结点的子树根构成一个线性表，以链表作它的存储结构，令其头指针和结点的数据元素构成一个结点，并将所有这样的结点存放在一个地址连续的存储空间里，所构成的树的存储结构称为树的孩子链表。,如：下列图示树的孩子链表如下图所示,树的孩子链表存储表示 typedef struct CTNode / 孩子结点 int child; struct C

26、TNode *next; *ChildPtr; typedef struct ElemType data; / 结点的数据元素 ChildPtr firstchild; / 孩子链表头指针 CTBox; typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;,6.6.3 树和森林的孩子兄弟表示法,树中每个结点都设有两个指针， firstchild 指向该结点的“第一个”子树根结点， nextsibling 指向它的“下一个”兄弟结点。 森林可认为各棵树的根结点之间是一个 “兄弟”关系 因此无论树和森林都可以用

27、这样的“二叉链表”表示。 由于结点中的两个指针指示的分别为 孩子和兄弟的关系，故称为孩子-兄弟链表 。,6.6.4 森林和二叉树的转换,假设森林 F = T1,T2, ,Tn ， 其中第一棵树T1由根结点 ROOT(T1) 和子树森林 T11 , T12 , , T1m 构成。 可按如下规则转换成一棵二叉树 B =( LBT, Node(root), RBT )： 若森林 F 为空集，则二叉树 B 为空树； 否则， 由森林中第一棵树的根结点 ROOT(T1 ) 复制得二叉树的根 Node(root)，由森林中第一棵树的子树森林 T11 , T12 , , T1m 转换得到二叉树中的左子树LBT

28、，由森林中删去第一棵树之后由其余树构成的森林 T2,T3, ,Tn 转换得到二叉树中的右子树RBT。,反之，对于任意一棵二叉树 B =( LBT, Node(root), RBT )， 可按如下规则转换得到由n 棵树构成的森林 F = T1,T2 , , Tn 若二叉树 B 为空树, 则与其对应的森林 F 为空集； 否则，由二叉树的根结点 Node(root) 复制得森林中第一棵树的根结点 ROOT( )，由二叉树中的左子树 LBT 转换构造森林中第一棵树的子树森林T11 , T12 , , T1m ，由二叉树中的右子树 RBT 转换构造森林中其余树构成的森林 T2,T3, ,Tn 。,由此，

29、对树和森林进行的各种操作均可通过对二叉树进行相应的操作来完成，但同时也必须注意，此时的二叉树，其左、右子树和根结点之间的关系不再是它的左、右孩子，而是左子树是根的孩子们，右子树是根的兄弟们。,6.7 树和森林的遍历,6.7.1 树的遍历,对树进行遍历可有两条搜索路径： 1.是从左到右 2.是按层次从上到下。 树的按层次遍历类似于二叉树的按层次遍历，例如下图树按层次遍历所得访问的次序的为：ABCDEFGHIJK。,类似于二叉树，在这条搜索路径上途径根结点两次，由对根的访问时机不同可得下列两个算法： 一、先根(次序)遍历树 若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树； 二、后根

30、(次序)遍历树 若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点；,树进行从左到右遍历的搜索路径如下图所示。,进行先根遍历所得结点的访问序列为：ABEHIJCDFGK 进行后根遍历所得结点的访问序列为：HIJEBCFKGDA,如图所示,6.7.2 森林的遍历,一、先序遍历森林 若森林不空，则可依下列次序进行遍历 (1) 访问森林中第一棵树的根结点； (2) 先序遍历第一棵树中的子树森林； (3) 先序遍历除去第一棵树之后剩余的树构成的森林。 二、中序遍历森林 若森林不空，则可依下列次序进行遍历： (1) 中序遍历第一棵树中的子树森林； (2) 访问森林中第一棵树的根结点； (3)

31、 中序遍历除去第一棵树之后剩余的树构成的森林。,森林中的 二叉树中的 （第一棵树的根） - （二叉树的根） （第一棵树的子树森林）- （二叉树的左子树） （其余树构成的森林） - （二叉树的右子树）,容易看出： 若以孩子-兄弟链表作树（或森林）的存储结构， 则树的先根遍历（或森林的先序遍历）算法 类似于二叉树的先序遍历算法 树的后根遍历(或森林的中序遍历）的算法 类似于二叉树的中序遍历算法,6.8 最优树和赫夫曼编码,6.8.1 最优树的定义 最优树：又称赫夫曼树（Huffman Tree）是一类带权路径长度最短的树，本节仅限于讨论最优二叉树。 介绍一下概念： 路径：由从树的根结点到其余结点的分支构成一条路径 路径长度：路径上的分支数目。 树