数据结构树和二叉树

《数据结构树和二叉树》由会员分享，可在线阅读，更多相关《数据结构树和二叉树（150页珍藏版）》请在金锄头文库上搜索。

1、第六章第六章 树和二叉树树和二叉树树是一种很重要的非线性数据结构。6.1 树的定义和基本术语树的定义和基本术语6.3 树和森林树和森林6.2 二叉树二叉树6.4 赫夫曼树与赫夫曼编码赫夫曼树与赫夫曼编码提要6.1 树的定义和基本术语树的定义和基本术语D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 若若D为空集，则称为空树为空集，则称为空树 。 否则否则: (1) 在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root； (2) 当当n1时，其余元素可分为时，其余元素可分为m (m0)个互个互 不相交的有限集不相交的有限集T1, T2, , Tm，其中每一其中

2、每一 个子集本身又是一棵符合本定义的树，个子集本身又是一棵符合本定义的树， 称为根称为根root的子树。的子树。 数据关系数据关系 R：6.1.1 树树的的定义定义数据对象数据对象 D：ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2树根例如例如: :6.1.2 6.1.2 基本术语基本术语结点结点: :结点的度结点的度: :树的度树的度: :叶子结点叶子结点: :分支结点分支结点: :数据元素+ +若干指向子树的分支。结点的分支的个数。树中所有结点的度的最大值。度为零的结点。度大于零的结点。DHIJM(终端结点)(非终端结点)(

3、从根到结点的)路径：路径：孩子孩子、双亲双亲、兄弟兄弟、祖先祖先、子孙子孙结点的层次结点的层次: :树的深度树的深度(高度)：由从根根到该结点所经分支和结点构成。ABCDEFGHIJMKL根为第一层，根的孩子为第二层，若某结点在第l 层，则其子树的根就在第l+1层。树中结点的最大层次。任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为根结点 F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合。ArootFBCDEFGHIJMKL由此，我们可以定义：查查 找找 类类 插插 入入 类类删删 除除 类类 6.1.3 基本操作基本操作 Root(T) / 求树

4、的根结点求树的根结点 Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树判定树是否为空树 TreeDepth(T) / 求树的深度求树的深度TraverseTree( T, Visit() ) / 遍历遍历查找类查找类：InitTree(&T) / 初始化置空树初始化置空树 Cr

5、eateTree(&T, definition) / 按定义构造树按定义构造树Assign(T, cur_e, value) / 给当前结点赋值给当前结点赋值InsertChild(&T, &p, i, c) / 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树插入类：插入类： ClearTree(&T) / 将树清空将树清空 DestroyTree(&T) / 销毁树的结构销毁树的结构DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树删除类：删除类：() 有确定的根；() 树根和子树根之间为有向关系。有序树：有序树：子树之间存在确

6、定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。(有向有向)树：树：对比对比树型结构树型结构和和线性结构线性结构的的结构特点结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )6.2 二叉树二叉树6.2.1 二叉树的定义二叉树的定义6.2.2 二叉树的存储结

7、构二叉树的存储结构6.2.3 二叉树的遍历二叉树的遍历6.2.4 线索二叉树线索二叉树ABCDEFGHK根结点左子树右子树 二叉树或为空树空树，或是由一个根结点根结点加上两棵两棵分别称为左子树左子树和右子树的、互互不交的不交的二叉树二叉树组成。N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树二叉树的五种基本形态二叉树的五种基本形态：查查 找找 类类插插 入入 类类删删 除除 类类 二叉树的主要基本操作二叉树的主要基本操作： Root(T); Value(T, e); Parent(T, e); LeftChild(

8、T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit(); InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p,

9、LR, c);ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);二叉树的重要特性二叉树的重要特性 性质性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1)用归纳法证明用归纳法证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。性质性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：证明：

10、 基于上一条性质，深度为 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 。满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号为编号为 1 至至 n 的结点的结点一一对

11、应。ABCDEFGHIJKLMNOabcdefghij两类两类特殊特殊的二叉树：的二叉树：12345678910111213 1415对满二叉树可以按顺序编号证明：证明：设设完全二叉树的深度为 k ，则根据第二条性质得 2k-1 n 2k ， 即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子右孩子结点。二、二叉树的链式二、二叉树的链式 存储表示存储表示一、一、 二叉树的顺序二叉树的顺序 存储表示存储表示6.2.2 二叉树的存储结构二叉树的存储结构#define

12、 MAX_TREE_SIZE 100 / 二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点SqBiTree bt;一、一、 二叉树的顺序存储表示二叉树的顺序存储表示 A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131ABCDEF251437例如例如:按照完全二叉树的编号顺序，依次将编号为i的元素存放在下标为i-1的位置中。1. 1. 二叉链表二叉链表2三叉链表三叉链表二、二叉树的链式存储表示二、二叉树的链式存储表示ADEBCF rootlchild data rchild结点结构结点

13、结构:1. 1. 二叉链表二叉链表ABCDEFtypedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;在这种二叉链表上找结点的左右孩子结点很方便；在这种二叉链表上找结点的左右孩子结点很方便；但要找双亲就必须从头指针开始遍历该二叉树。但要找双亲就必须从头指针开始遍历该二叉树。C 语言的类型描述如下语言的类型描述如下: :rootADEBCF parent lchild data rchild结点结构结点结构:2三叉链表三叉链表ABCDE

14、F typedef struct TriTNode / 结点结构结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;parent lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :6.2.3 二叉树的遍历二叉树的遍历一、一、问题的提出问题的提出二、二、先左后右的遍历先左后右的遍历三、遍历三、遍历的递归的递归算法算法四、四、中序遍历的非递归中序遍历的非递归算法算法五五、遍历

15、算法的应用举例遍历算法的应用举例 顺着某一条搜索路径巡访巡访二叉树中的结点，使得每个结点均被访问一次均被访问一次，而且仅被访仅被访问一次问一次。 “访问访问”的含义可以很广，如：输出结点的信息等。一、问题的提出一、问题的提出 “遍历遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点可以有两个每个结点可以有两个后继后继，则存在如何遍历存在如何遍历即按什么样的搜索路搜索路径径遍历的问题。就是要寻找一种规律，使二叉树上的结点能按照这种规律线性排列。对对“二叉树二叉树”而言，可以有三条搜索路径：而言，可以有三条搜

16、索路径：1先上后下先上后下的按层次遍历；2先左先左（子树）后右后右（子树）的遍历；3先右先右（子树）后左后左（子树）的遍历。先先(根次)序的遍历算法中中(根次)序的遍历算法后后(根次)序的遍历算法二、先左后右的遍历二、先左后右的遍历例如:先序先序遍历的次序:A中序中序遍历的次序:D后序后序遍历的次序:DABDCFHEGIBDCEGFHIBAEGCHFIBGEHI FCA 若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根次）序的遍历算法先（根次）序的遍历算法： 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍

17、历右子树。中（根次）序的遍历算法中（根次）序的遍历算法： 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根次）序的遍历算法后（根次）序的遍历算法：三、算法的递归算法三、算法的递归算法 基于上述二叉树的先序、中序、后序遍历算法的文字描述，可以得到遍历的递归算法。以二叉链表为存储结构。先序遍历的递归算法：void Preorder (BiTree T, void( *visit)(TElemType& e) / 先序遍历二叉树 if (T) visit(T-data); / 访问结点 Preorder(T-lchild, visit); / 遍历

18、左子树 Preorder(T-rchild, visit);/ 遍历右子树 void Inorder (BiTree T, void( *visit)(TElemType& e) / 中序遍历二叉树 if (T) Inorder(T-lchild, visit); / 遍历左子树 visit(T-data); / 访问结点 Inorder(T-rchild, visit);/ 遍历右子树 中序遍历的递归算法：void Postorder (BiTree T, void( *visit)(TElemType& e) / 后序遍历二叉树 if (T) Postorder(T-lchild, vis

19、it); / 遍历左子树 Postorder(T-rchild, visit);/ 遍历右子树 visit(T-data); / 访问结点 后序遍历的递归算法： 由二叉树遍历的定义可知，三种遍历算法的不同之处仅在于访问根结点和遍历左、右子树的先后关系。如果在算法中暂时抹去和递归无关的visit( )函数，则三个遍历算法完全相同。 由此，从递归执行过程的角度来看，先序、中序、后序遍历是完全相同的。算法的时间复杂度分析： 由于遍历的实质是沿着结点的左、右孩子指针周游，所以，遍历二叉树算法的时间复杂度为O(n)。算法的空间复杂度分析：上述三个算法都是递归算法，所用辅助空间量为栈的容量，恰为树的深度，

20、则至多为O(n)，至少为O(log2n)。四、中序遍历算法的非递归描述四、中序遍历算法的非递归描述 利用栈，我们可以将递归算法改写为非递归算法。BiTNode *GoFarLeft(BiTree T, Stack *S)/从T出发，顺着左孩子链找到左孩子为空的结点，/以该结点的指针返回，并将路径上的所有结点的指针入栈。 if (!T ) return NULL; while (T-lchild ) Push(S, T); T = T-lchild; return T; void InorderTraverse(BiTree T, void (*visit) (TelemType& e) Ini

21、tStack(S); t = GoFarLeft(T, S); / 找到最左下的结点 while(t) visit(t-data); if (t-rchild) t = GoFarLeft(t-rchild, S); else if ( !StackEmpty(S ) / 栈不空时退栈 t = Pop(S); else t = NULL; / 栈空表明遍历结束 / while/ InorderTraverseABDCFHEGI 栈sAB遍历序列：D B ACE GFC H FIttttttttt 非递归算法的时间复杂度和空间复杂度与递归算法相同。 如果我们采用三叉链表存储结构（增加一个双亲指针

22、域），就不再需要栈空间了。1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数 (先序遍历先序遍历)2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)3、复制二叉树、复制二叉树(后序遍历后序遍历)4 4、建立二叉树的存储结构、建立二叉树的存储结构五五、遍历算法的应用举例遍历算法的应用举例算法基本思想算法基本思想: : 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的的参数，参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增若是叶子，则计数器增1 1。1、统计二叉树中叶子结点的个数、统计二叉树中

23、叶子结点的个数void CountLeaf (BiTree T, int& count) /count的初值为0 if ( T ) if (!T-lchild)& (!T-rchild) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf也可以写成如下算法：int CountLeaf (BiTree T)/ 返回二叉树的叶子结点个数 if ( !T ) return 0; if (!T-lchild)& (!T-rchild) return 1; return

24、CountLeaf(T-lchild)+CountLeaf(T-rchild); / CountLeaf算法基本思想算法基本思想: : 从二叉树深度的定义可知，二叉树的深度二叉树的深度应为其左、右子树深度的最大值加应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度求得左、右子树深度的最大值，然后加的最大值，然后加 1 1 。 首先分析二叉树的深度二叉树的深度和它的左左、右子树深右子树深度度之间的关系。2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)int Depth (BiTree T )

25、 / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;其基本操作为：生成一个结点。其基本操作为：生成一个结点。根元素根元素T左子树左子树右子树右子树根元素根元素NEWT左子树左子树右子树右子树左子树左子树右子树右子树3、复制二叉树、复制二叉树(后序遍历后序遍历)BiTNode *GetT

26、reeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(Overflow); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; 生成一个二叉树的结点生成一个二叉树的结点(其数据域为其数据域为item,左指针域为左指针域为lptr,右指针域为右指针域为rptr)BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; if (T

27、-lchild ) newlptr = CopyTree(T-lchild);/复制左子树 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/复制右子树 else newrptr = NULL; newT = GetTreeNode(T-data, newlptr, newrptr); return newT; / CopyTreeG E AABCDEFGHK D C B H K F 例如：下列二叉树的例如：下列二叉树的复制过程如下：复制过程如下：newT4 4、建立二叉树的存储结构、建立二叉树的存储结构不同的定

28、义方法相应有不同的存储不同的定义方法相应有不同的存储结构的建立算法结构的建立算法例如:ABCD以空白字符“ ”表示AB C D 空树空树只含一个根结点的只含一个根结点的二叉树二叉树A以字符串“A ”表示以下列字符串表示以字符串的形式以字符串的形式 根根 左子树左子树 右子右子树树（先序）定义一棵二叉树（先序）定义一棵二叉树Status CreateBiTree(BiTree &T) /按先序输入二叉树中结点的值（字符），空格字符表示空树 scanf(&ch); if (ch= ) T = NULL; else if (!(T = (BiTNode *)malloc(sizeof(BiTNode

29、) exit(OVERFLOW); T-data = ch; / 生成根结点 CreateBiTree(T-lchild); / 构造左子树 CreateBiTree(T-rchild); / 构造右子树 return OK; / CreateBiTreeA B C D A BCD上页算法执行过程举例如下：ATBCD 仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树， 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？ 二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树右子树右子树右子树右子树根根根根由二叉树的先序和中序序列可唯一确定一由二叉树的先序和中序序列可唯一

30、确定一棵二叉棵二叉树树a b c d e f gc b d a e g faab bccddeeffggabcdefg先序序列中序序列例如例如: :6.2.4 线索二叉树线索二叉树何谓线索二叉树？何谓线索二叉树？线索链表的遍历算法线索链表的遍历算法如何建立线索链表？如何建立线索链表？遍历二叉树的结果是， 求得结点的一个线性序列。例如:先序先序序列: A B C D E F G H K中序中序序列: B D C A H G K F E后序后序序列: D C B H K G F E A一、一、何谓线索二叉树？何谓线索二叉树？ABCDEFGHK 这实质上是对一个非线性结构进行线性化，使每个结点在这些

31、线性序列中有且仅有一个直接前驱和一个直接后继。 但在前面的二叉链表存储结构中，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。 另外，在有n个结点的二叉链表中，必定存在n+1个空指针域，由此，设想能否利用这些空指针域来存放结点的前驱和后继信息？ D与其相应的二叉树，称作 “线索二叉树线索二叉树”包含 “线索” 的存储结构，称作 “线索链表线索链表”B D C A H G K F E B C D 指向该线性序列中的“前驱”和 “后继” 的指针指针，称作“线索线索”中序中序序列: 在二叉链表的结点中增加两个标志域增加两个标志域，

32、并作如下规定：若该结点的左子树不空，若该结点的左子树不空，则lchild域的指针指向其左子树， 且左标志域的值为“指针 Link”； 否则，lchild域的指针指向其“前驱”， 且左标志的值为“线索 Thread” 。对对线索链表线索链表中结点的约定：中结点的约定：若该结点的右子树不空，若该结点的右子树不空，则rchild域的指针指向其右子树， 且右标志域的值为 “指针 Link”；否则，rchild域的指针指向其“后继”， 且右标志的值为“线索 Thread”。 如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线索链表线索链表”。typedef struct BiThrNod

33、TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerThr ltag, rtag; / 左右标志 BiThrNode, *BiThrTree;typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索线索链表的类型描述：lchild ltag data rtagrchildltag =0 lchild指向结点的左孩子1 lchild指向结点的前驱rtag =0 rchild指向结点的右孩子1 rchild指向结点的后继tag =0 正常指针1 线索中序线

34、索二叉树：ABCDEFGHKNULLNULLT头结点中序序列：BDCAHGKFE for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。二、线索链表的遍历算法二、线索链表的遍历算法 中序遍历的第一个结点中序遍历的第一个结点 ？ 在中序线索化链表中结点的后继在中序线索化链表中结点的后继 ？左子树上处于“最左下最左下”（没有左子树）的结点。若若无右子树，则为则为后继线索后继线索所指结点；否则为否则为对其右子树右子树进行中序遍历遍历时访问的第一个结点。第一个结点。例如例如

35、: 对中序线索化链表的遍历算法对中序线索化链表的遍历算法求中序线索二叉树中结点的中序后继算法:BiThrTree insuc(BiThrTree p)/返回p所指结点的中序后继 q = p-rchild; /若p-rtag为1，则q所指即为p的后继 if (p-rtag = = 0) /否则，p的后继是从q出发最左下的结点 while (q-ltag = = 0) q = q-lchild; return q;void InOrder_Thr(BiThrTree T, void (*Visit)(TElemType e) /T指向头结点，头结点的lchild指向根结点。 /中序遍历中序线索二叉

36、树的非递归算法 p = T-lchild; / p指向根结点 if (p != T) / 若p不是空树 while (p-ltag=0) p = p-lchild; /找中序访问的第一个结点 while (p!=T) / 依次访问各结点 Visit(p-data); p = insuc(p); / InOrder_Thr 在中序遍历过程中修改结点的左、右在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的指针域，以保存当前访问结点的“前驱前驱”和和“后继后继”信息。遍历过程中，附设指针信息。遍历过程中，附设指针pre, 并始终保持指针并始终保持指针pre指向当前访问的、指向当前访问的、

37、指针指针p所指结点的前驱。所指结点的前驱。三、如何建立线索链表？三、如何建立线索链表？void InThreading(BiThrTree p) if (p) / 对以p为根的非空二叉树进行中序线索化 InThreading(p-lchild); / 左子树线索化 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); /

38、 右子树线索化 / if / InThreadingStatus InOrderThreading(BiThrTree &Thrt,BiThrTree T) / 构建中序线索链表 if (!(Thrt = (BiThrTree)malloc(sizeof( BiThrNode) exit (OVERFLOW); Thrt-ltag = Link; Thrt-rtag =Thread; Thrt-rchild = Thrt; / 添加头结点 return OK; / InOrderThreading if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T

39、; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 处理最后一个结点 pre-rtag = Thread; Thrt-rchild = pre; 6.3 树和森林树和森林6.3.1 树和森林的表示方法树和森林的表示方法6.3.2 森林与二叉树的相互转换森林与二叉树的相互转换6.3.3 树和森林的遍历树和森林的遍历6.3.1 6.3.1 树和森林的表示方法树和森林的表示方法一、一、双亲表示法双亲表示法二、二、孩子表示法孩子表示法三、三、孩子孩子- -兄弟兄弟( (二叉树二叉树) )表示法表示法树的三种存储结构树的三种存储结构一、双亲表示法一、双亲

40、表示法:用一组连续空间存储树的结点，同时，在每个结点中附设一指示器，指示其双亲结点的位置（下标）。 typedef struct PTNode ElemType data; int parent; / 双亲位置域 PTNode; data parent#define MAX_TREE_SIZE 100结点结构结点结构:C语言的类型描述语言的类型描述: :typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;树结构树结构:ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G

41、5r=0(根结点的位置)n=7(总结点数)data parent例如： 这种结构利用了每个结点（除根结点外）只有唯一的双亲的性质。 在其中求结点的双亲，以及找树的根十分方便，但是，当求结点的孩子时需遍历整个表。二、孩子表示法二、孩子表示法:有三种具体的表示方法：有三种具体的表示方法：1. 固定的多重链表 datachild1 child2 childk每个结点有多个指针域，其中每个指针指向一棵子树的根结点。链表的结点结构为：childk为树的度引理：如果T是一棵有n个结点、度为k的树，每个结点表示为如上的固定大小，那么，在nk个链域中有n(k-1)+1个域为空。证：因为有n个结点的树，其非空链

42、域有n-1个，而总的链域是nk个，所以，空链域个数= nk-(n-1) = n(k-1)+1由此可知，固定的多重链表固定的多重链表指针空间浪费太大。2. 可变的多重链表 datadegree child1child2 childd链表的结点结构为：这里，childddegree这样的结点不同构，其大小与具体结点的度有关。虽然节省了存储空间，但操作不便。(结点有几棵子树，就设几个child域)typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子结点结构孩子结点结构: child next3.孩子链表表示法 C语言的类

43、型描述语言的类型描述: :将孩子结点连成一条单链表 typedef struct Elem data; ChildPtr firstchild; / 孩子链的头指针 CTBox; data firstchild双亲结点结构：双亲结点结构：C语言的类型描述语言的类型描述: :typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;树结构树结构:C语言的类型描述语言的类型描述: :0 A 1 B 2 C 3 D 4 E 5 F 6 Gr=0n=7 data firstchildABCDEFG64 5 1 2 3-1

44、000224例如：parent双亲结点结构：双亲结点结构：Data parent firstchild三、孩子三、孩子-兄弟兄弟(二叉树、二叉链表二叉树、二叉链表 ) 表示法表示法 为了用两个指针表示结点之间的关系，得到二叉链表的表示法，需要找出一个最多能用两个量来描述的结点关系。一个这样的关系是“最左孩子，最近兄弟”关系，即每个结点最多有一个最左的孩子、一个靠近的右兄弟。typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;C语言的类型描述语言的类型描述: :结点结构

45、结点结构: firstchild data nextsiblingABCDEFGroot AB C E D F G 例如：ABCDEFG类似地，森林也可以用二叉树表示。例如： A D EJI HG F C B A B C D E FG HIJ森林：二叉树：设设森林森林 F = ( T1, T2, , Tn ); T1 = (root，t11, t12, , t1m);二叉树二叉树 B =( LBT, Node(root), RBT );6.3.2 森林与二叉树的相互转换森林与二叉树的相互转换 由于二叉树和森林由于二叉树和森林(树树)都可以用二叉链表作为存储都可以用二叉链表作为存储结构，则以二叉

46、链表作为媒介可以导出森林结构，则以二叉链表作为媒介可以导出森林(树树)与二叉与二叉树之间的对应关系。也就是说，给定一个森林，可以找树之间的对应关系。也就是说，给定一个森林，可以找到唯一的一棵二叉树与之对应，从物理结构来看，它们到唯一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。的二叉链表是相同的，只是解释不同而已。若 F = ，则 B = ；否则， 由 ROOT( T1 ) 对应得到 Node(root)； 由 (t11, t12, , t1m ) 对应得到 LBT； 由 (T2, T3, Tn ) 对应得到 RBT。1. 由森林转换成二叉树由森林转换成二叉树

47、转换规则为:若 B = ， 则 F = ；否则，由 Node(root) 对应得到 ROOT( T1 )；由LBT 对应得到 ( t11, t12, ，t1m)；由RBT 对应得到 (T2, T3, , Tn)。2. 由二叉树转换为森林由二叉树转换为森林转换规则为：例如：ABCED FGH I JK LMABCDEFGH I JKLM 应当注意的是，应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为： 左是孩子，右是兄弟。左是孩子，右是兄弟。 由此，树的各种操作均可对应二叉树的操作来完成。一、树的遍历一、树的遍历二、森林的遍历二、森林的遍历6.3.3 树和森林的遍历树和森林的遍历按层次

48、遍历按层次遍历:先根先根(次序次序)遍历遍历:后根后根(次序次序)遍历遍历: 若树不空，则先访问根结点，然后依次若树不空，则先访问根结点，然后依次先根遍历各棵子树。先根遍历各棵子树。 若树不空，则先依次后根遍历各棵子树，若树不空，则先依次后根遍历各棵子树，然后访问根结点。然后访问根结点。 若树不空，则自上而下、自左至右访若树不空，则自上而下、自左至右访问树中每个结点。问树中每个结点。树的遍历可有三条搜索路径树的遍历可有三条搜索路径:先根遍历时顶点的访问次序：先根遍历时顶点的访问次序：A B E F C D G H I J K后根遍历时顶点的访问次序：后根遍历时顶点的访问次序：E F B C I

49、 J K H G D A层次遍历时顶点的访问次序：层次遍历时顶点的访问次序：A B C D E F G H I J K例如：ABCDEFGH I JKABCEFDGH I JK转换成二叉树：对应于相应二叉树的对应于相应二叉树的先序遍历先序遍历，可借助二叉树的先序遍历算法可借助二叉树的先序遍历算法来实现。来实现。对应于相应二叉树的对应于相应二叉树的中序遍历中序遍历，可借助二叉树的中序遍历算法可借助二叉树的中序遍历算法来实现。来实现。 B C DE F G H I J K1森林中第一棵树的根结点；2森林中第一棵树的子树森林；3森林中其它树构成的森林。森林由三部分构成：1. 先序遍历先序遍历 若森林

50、不空，则访问访问森林中第一棵树的根结点；先序遍历先序遍历森林中第一棵树的子树森林；先序遍历先序遍历森林中(除第一棵树之外)其 余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行先先根遍历根遍历。森林的遍历森林的遍历 若森林不空，则中序遍历中序遍历森林中第一棵树的子树森林；访问访问森林中第一棵树的根结点；中序遍历中序遍历森林中(除第一棵树之外)其 余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行后根后根遍历遍历。中序遍历中序遍历例如：先序遍历时顶点的访问先序遍历时顶点的访问次序：次序：BEFCDGHIJK中序遍历时顶点的访问次中序遍历时顶点的访问次序：序：E

51、FBCIJKHGDBCDEFGH JK IBCEFDGH I JK转换成二叉树：对应于相应二叉树的对应于相应二叉树的先序遍历先序遍历，可借助二叉树的先序遍历算法可借助二叉树的先序遍历算法来实现。来实现。对应于相应二叉树的对应于相应二叉树的中序遍历中序遍历，可借助二叉树的中序遍历算法可借助二叉树的中序遍历算法来实现。来实现。先根遍历先根遍历后根遍历后根遍历树树二叉树二叉树森林森林先序遍历先序遍历先序遍历先序遍历中序遍历中序遍历中序遍历中序遍历树、森林的遍历和二叉树遍历的对应关系树、森林的遍历和二叉树遍历的对应关系6.4 赫夫曼树与赫夫曼编码赫夫曼树与赫夫曼编码 最优二叉树（赫夫曼树）最优二叉树（

52、赫夫曼树）如何构造最优二叉树如何构造最优二叉树赫夫曼编码赫夫曼编码( Huffman )树的路径长度树的路径长度定义为： 树中每个结点的路径长度之和。 结点的路径长度结点的路径长度定义为： 从根结点到该结点的路径上分支的数目。 一、最优二叉树（赫夫曼树）一、最优二叉树（赫夫曼树）ABCDEFGEGFDCBA1+2+1+2+3+3=121+2+2+1+2+2=10例如：可见,如果结点数目相同,则具有最小路径长度的二叉树是完全二叉树。 在实际应用中，如情报检索、信息编码等，往往将真正的信息存入叶子结点中，而分枝结点仅仅用于检索判断；而且不同的信息具有不同的检索频率，我们应区别对待。也就是说，对于不

53、同的叶子结点需给予不同的权值。 这就要引入带权路径长度的概念。 从该结点到树的根结点的路径长度与结点上权的乘积。结点的带权路径长度结点的带权路径长度定义为： 树中所有叶子结点的带权路径长度结点的带权路径长度之和。树的带权路径长度树的带权路径长度定义为：WPL(T) =其中，n为叶子结点的个数； wk为叶子结点k的权； lk为从根结点到叶子结点k的路径长度。27549WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 7 9 254例如：最优最优二叉树的概念二叉树的概念 设有n个结点，它们分别具有不同的权值wk，将这n个结点作为叶子结点可以构

54、造出m种不同的二叉树，这些二叉树具有不同的带权路径长度，则其中带权路径长度最小的二叉树称为最优二叉树最优二叉树(或赫夫曼树或赫夫曼树)。例如:abcd7524abcd7524abcd7524(A)(B)(C)WPL(A)= (7+5+2+4)2=36WPL(B)= (7+5)3+21+42=46WPL(C)= 71+52+(2+4)3=35请注意观察a7c2WPL(B)=71+42+(2+5)3=36分析上例，我们可以得出以下结论：(1) 当叶子结点的权值不相同时，完全二叉树并不一定是最优二叉树；(2) 为了构造最优二叉树，必须将权值大的结点尽量靠近根结点；(3) 在这种二叉树中，不应有度为1

55、的结点。根据给定的 n 个权值 w1, w2, , wn，构造 n 棵二叉树的集合F = T1, T2, , Tn，其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树;(1)赫夫曼算法：赫夫曼算法：二、如何构造最优二叉树二、如何构造最优二叉树在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；(2)从F中删去这两棵树，同时加入刚生成的新树；重复 (2) 和 (3) 两步，直至 F 中只含一棵树为止。(3)(4)9562752769767139527例如: 已知权值 W= 5, 6

56、, 2, 9, 7 671395271667139527162995271667132900001111000110110111三、赫夫曼编码（前缀编码）三、赫夫曼编码（前缀编码） 为了高速地传递信息，需要高效的编码和译码技术。现在我们讨论如何用前面所学的知识来完成这一任务。 假定有四个字母：A，B，C，D需进行编码，我们可以用两位二进制代码来表示：则信息“ABACCDA”的编码位：00010010101100（14位）A：00 B：01 C：10 D：11 我们总是希望找到长度最小的信息编码。 进一步研究上面例子，可以发现，在信息“ABACCDA”中，字母B和D只出现一次，A则出现过3次，如

57、果我们能选择一种编码，使A的位数比B和D的位数少，那么，整个信息编码的长度就可以减少。例如，把编码设计为：A：0 B：110 C：10 D：111则“ABACCDA”的编码为：0110010101110（13位）这是一种不等长编码不等长编码，当信息很长时，这种方法是很有效的。 但需要注意的是：选择这样一个高效的编码方法时，一个符号的编码不能是另一个符号编码的前缀。即：任何一个字符的编码都不是任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀同一字符集中另一个字符的编码的前缀。 上述问题的实质就是在某一信息集中，在每个符号出现的频率给定的情况下，去寻找一种最佳的编码方法。叫做叫做前缀编码

58、前缀编码 利用赫夫曼树可以构造一种不等长的二进制利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的编码，并且构造所得的赫夫曼编码赫夫曼编码是一种是一种最优最优前缀编码前缀编码，即，即:使所传使所传电文的总长度最短电文的总长度最短。可利用二叉树来设计二进制的前缀编码。ADBC3211左分枝左分枝表示字符表示字符0000右分枝右分枝表示字符表示字符1111从根到叶子的路径上分枝字符组成的字符串即为该叶子结点字符的编码。那么，如何得到最短的二进制前缀编码呢？赫夫曼树及其编码： 设字符ci出现的次数为wi，则以ci为叶子结点， wi为权值，构造赫夫曼树，然后在该赫夫曼树上进行编码。例如：某系统

59、在通讯联络中，只可能出现八个字符，其频率分别为：0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，设计赫夫曼编码。取w=(5，29，7，8，14，23，3，11)5297814 23311297814 23 11358根据赫夫曼算法构造赫夫曼树:29 14 23 1135878151135829 14 2378151914781529 231135819292311358192914781529422914781529231135819425810029147815295823113581942赫夫曼编码：10029147815295823113581942000

60、0000111111111：010 5：011029：10 7：1110 8：111114：11023：00 3：01111. 熟练掌握二叉树的结构特性二叉树的结构特性，了解相应的证明方法。2. 熟悉二叉树的各种存储结构存储结构的特点及适用范围。3. 遍历二叉树遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法递归算法，灵活运用遍历算灵活运用遍历算法法实现二叉树的其它操作。层次遍历层次遍历是按另一种搜索策略进行的遍历。本章学习要点4. 理解二叉树线索化的实质线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树

61、的线索化过程线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程线索化过程是基于基于对二叉树进行遍历遍历，而线索二叉树上的线索又为相应线索又为相应的遍历提供的遍历提供了方便方便。5. 熟悉树的树的各种存储结构存储结构及其特点，掌握树和森林与二叉树的转换树和森林与二叉树的转换方法。6. 学会编写实现树的各种操作实现树的各种操作的算法。7. 了解最优树的特性最优树的特性，掌握建立最优树和建立最优树和哈夫曼编码哈夫曼编码的方法。本章第一次作业：6.16.26.36.46.5本章第二次作业：6.136.146.436.47本章第三次作业：6.196.206.216.226.236.28本章第四次作业：6.266.296.60