第06章 树和二叉树

1、第六章第六章 树和二叉树树和二叉树n树的概念和基本术语n二叉树 n二叉树遍历n树与森林n霍夫曼树 1、树的定义、树的定义树是由树是由 n (n 0) 个结点的有限集合。如果个结点的有限集合。如果 n = 0，称为空树；如果，称为空树；如果 n 0，则，则 有且仅有一个特定的称之为根有且仅有一个特定的称之为根(Root)的结点，的结点，它只有直接后继，但没有直接前驱；它只有直接后继，但没有直接前驱； 当当n 1，除根以外的其它结点划分为，除根以外的其它结点划分为 m (m 0) 个互不相交的有限集个互不相交的有限集 T1, T2 , Tm，其中，其中每个集合本身又是一棵树，并且称为根的子树每个集

2、合本身又是一棵树，并且称为根的子树(SubTree)ACGBDEFKLHMIJ例如例如A只有根结点的树只有根结点的树有有13个结点的树个结点的树其中：其中：A是根；其余结点分成三个互不相交的子集，是根；其余结点分成三个互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根都是根A的子树，且本身也是一棵树的子树，且本身也是一棵树2、树的基本术语、树的基本术语1层2层4层3层height= 4ACGBDEFKLHMIJ定义定义五种形态五种形态：二叉树是一种特殊类型的树，它是由一个根：二叉树是一种特殊类型的树，它是由一个根结点加上两棵分别称为结点

3、加上两棵分别称为左子树左子树和和右子树右子树的、互的、互不相交的二叉树组成。不相交的二叉树组成。LLRR特点：特点：每个结点至多只有两棵子树（二叉树中每个结点至多只有两棵子树（二叉树中不存在度大于不存在度大于2的结点）的结点）1 1、二叉树的概念与性质、二叉树的概念与性质性质性质1：在二叉树的第在二叉树的第 i 层上至多有层上至多有 2i 1个个结点。结点。(i 1) 证明用归纳法证明用归纳法证明：当证明：当i=1时，只有根结点，时，只有根结点，2 i-1=2 0=1。假设对所有假设对所有j，ij 1，命题成立，即第，命题成立，即第j层层上至多有上至多有2 j-1 个结点。个结点。由归纳假设第

4、由归纳假设第i-1 层上至多有层上至多有 2i 2个结点。个结点。由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2，故在，故在第第i层上的最大结点数为第层上的最大结点数为第i-1层上的最大结层上的最大结点数的点数的2倍，即倍，即2* 2i 2= 2 i-1。性质性质性质性质2 ：深度为深度为 k 的二叉树至多有的二叉树至多有 2 k- -1个个结点结点(k 1)。证明：由性质证明：由性质1可见，深度为可见，深度为k的二叉树的的二叉树的最大结点数为最大结点数为 kii11220 + 21 + + 2 k-1 = 2 k- -1kii1(层上的最大结点数）第性质性质3：对任何一棵二叉

5、树对任何一棵二叉树T, 如果其叶结如果其叶结点数为点数为 n0, 度为度为2的结点数为的结点数为 n2,则则n0n21.证明：若度为证明：若度为1的结点有的结点有 n1 个，总结点个个，总结点个数为数为 n，总边数为，总边数为 e，则根据二叉树的定，则根据二叉树的定义，义， n = n0 + n1 + n2 e = 2n2 + n1 = n - - 1因此，有因此，有 2n2 + n1 = n0 + n1 + n2 - - 1 n2 = n0 - - 1 n0 = n2 + 1 定义定义1 满二叉树满二叉树 (Full Binary Tree) 一棵深度为一棵深度为k且有且有2 k-1个结点的

6、二叉树称为个结点的二叉树称为满二叉树。满二叉树。两种特殊形态的二叉树两种特殊形态的二叉树621754389 10 1113 14 1512满二叉树满二叉树215436 7216543非完全二非完全二叉树叉树定义定义2 完全二叉树完全二叉树 (Complete Binary Tree) 若设二叉树的高度为若设二叉树的高度为h，则共有，则共有h层。除层。除第第 h 层外，其它各层层外，其它各层 (0 h- -1) 的结点数都的结点数都达到最大个数，第达到最大个数，第 h 层层从右向左从右向左连续缺若干连续缺若干结点，这就是完全二叉树。结点，这就是完全二叉树。621754389 10 11 12完全

7、二完全二叉树叉树性质性质4 具有具有 n (n 0) 个结点的完全二叉树个结点的完全二叉树的深度为的深度为 log2(n) 1证明：证明：设完全二叉树的深度为设完全二叉树的深度为 h，则根据性，则根据性质质2和完全二叉树的定义有和完全二叉树的定义有2h1 - - 1 n 2h- - 1或或 2h1 n 2h取对数取对数 h1 0, 则则 i 的双亲为的双亲为 (i - -1)/2 n 若若2*i+1 n, 则则 i 的左子女为的左子女为 2*i+1，若，若2*i+2 lchild ); visit(T-data); InOrderTraverse ( T-rchild ); 中序遍历二叉树的递

8、归算法中序遍历二叉树的递归算法演示演示前序遍历二叉树算法的定义：前序遍历二叉树算法的定义：若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则访问根结点访问根结点 (V)；前序遍历左子树前序遍历左子树 (L)；前序遍历右子树前序遍历右子树 (R)。遍历结果遍历结果 - - + a * b - - c d / e fn 先序遍历先序遍历 (Preorder Traversal)前序遍历二叉树的递归算法前序遍历二叉树的递归算法演示演示void PreOrderTraverss ( BiTree T, int(*visit )(ElemType data) if ( T ) visit( T-d

9、ata); PreOrderTraverss ( T-lchild ); PreOrderTraverss ( T-rchild ); 后序遍历二叉树算法的定义：后序遍历二叉树算法的定义：若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则后序遍历左子树后序遍历左子树 (L)；后序遍历右子树后序遍历右子树 (R)；访问根结点访问根结点 (V)。遍历结果遍历结果 a b c d - * + e f / -n后序遍历后序遍历 (Postorder Traversal)后序遍历二叉树的递归算法后序遍历二叉树的递归算法 演示演示void PostOrderTraverss ( BiTree T,

10、int (*visit)(ElemType data) ) if ( T ) PostOrderTraverss ( T-lchild ); PostOrderTraverss ( T-rchild ); visit( T-data); 4 4、二叉树主要操作、二叉树主要操作void CreateBiTree(BiTRee &T) scan(&ch); if(ch=“”) T=null; else if(!(T=(BiTree)malloc(sizeof(BiTNode) exit (overflow); T-data=ch; CreateBiTree(T-lchild); C

11、reateBiTree(T-rchild); return;u按前序建立二叉树按前序建立二叉树演示演示int CountBiTNods ( BinTreeNode *T ) if ( !T ) return 0; else return 1 + CountBiTNods ( T-lchild ) + CountBiTNods ( T-rchild );u计算二叉树结点个数计算二叉树结点个数(递归算法递归算法)int CountLeafs (Bitree T) /求二叉树中叶子结点的数目求二叉树中叶子结点的数目 if(!T) return 0; /空树没有叶子空树没有叶子 else if(!T-

12、lchild&!T-rchild) return 1; /叶子结点叶子结点 else return CountLeafs (T-lchild) +CountLeafs(T-rchild); /左子树的叶子数加上右子树的叶子数左子树的叶子数加上右子树的叶子数/Leaf_Countu求二叉树中叶子结点的个数求二叉树中叶子结点的个数int CountHeight ( BiTree T ) if ( !T) return 0 0; else int m =CountHeight ( T-lchild ); int n =CountHeight ( T-rchild ) ); return (m

13、 n) ? m+1 : n+1; u求二叉树高度求二叉树高度(递归算法递归算法)u中序遍历二叉树中序遍历二叉树(非递归算法非递归算法)用栈实现用栈实现baabcdeadaaa b入栈入栈b退栈退栈访问访问d入栈入栈d退栈退栈访问访问e 退栈退栈 访问访问ecc栈空栈空 a退栈退栈访问访问c e 入栈入栈c 退栈退栈 访问访问 void InOrderTraverss ( BiTree T ) stack S; InitStack( &S ); /递归工作栈递归工作栈 Push(S,T); /初始化初始化 while ( !StackEmpty(S) ) while(GetTop(S,p

14、)&p) Push(S,p-lchild); Pop(S,p); if ( !StackEmpty(S) ) /栈非空栈非空 Pop(S, p); /退栈退栈 if(!visit(p-data) return error; Push(S, p-rchild); /if /while return ; 演示演示abcdeu前序遍历二叉树前序遍历二叉树(非递归算法非递归算法)用栈实现用栈实现acabcdedcc访问访问a进栈进栈c左进左进b访问访问b进栈进栈d左进左进空空退栈退栈d访问访问d左进左进空空退栈退栈c访问访问c左进左进e访问访问e左进左进空空退栈退栈 结束结束void PreO

15、rderTraverss( BiTree T ) stack S; InitStack(S); /递归工作栈递归工作栈 BiTree p = T; Push (S, NULL); while ( p ) visit( p-data); if ( p-rchild ) Push ( S, p-rchild ); if ( p-lchild ) p = p-lchild;/进左子树进左子树 else Pop( S, p ); abcdeLTag=0, Lchild为为左孩子左孩子LTag=1, Lchild为为前驱线索前驱线索RTag=0, Rchild为为右右孩子孩子RTag=1, Rchild

16、为为后继指针后继指针LTagRTag5 5、线索二叉树、线索二叉树 (Threaded Binary Tree)(Threaded Binary Tree)n结点结构结点结构-+a*b-c/def中序线索二叉树thrttypedef enum PointerTagLink=0,Thread=1/Link=0：指针，：指针，Thread=1：线索：线索;typedef struct BiThrNode ElemType data; struct BithrNode *lchild,*rchild; PointerTag LTag,RTag; /左右标志左右标志BiThrNode,*BiThrTr

17、ee;n线索二叉树存储结构u中序遍历二叉线索树中序遍历二叉线索树void InOrderTraverss_Thr(BiThrTree T, int(*visit)(ElemType data) BiThrTree p=T-child; /P指向根结点指向根结点 whild(p!=T) /空树或遍历结束时，空树或遍历结束时，p=T while(p-LTag=Link)p=p-child; visit(p-data); while(p-RTag=Thread&p-rchild!=T) p=p-rchild;visit(p-data); /访问后继结点访问后继结点 p=p-rchild; r

18、eturn; 演示演示n线索二叉树的部分操作u中序遍历二叉树，并将其线索化中序遍历二叉树，并将其线索化 演示演示void InOrderThreading(BiThrTree &Thrt, BiThrTree T) if(!(Thrt=(BiThrTree)malloc(sizeof( BiThrNode) exit(overflow); Thrt-LTag=Link;Thrt-RTag=Thread;/建头结点建头结点 Thrt-rchild=Thrt; /右指针回指右指针回指 if(!T)Thrt-rchild=Thrt; /若二叉树空，左指针回指若二叉树空，左指针回指 else

19、Thrt-lchild=T;pre=Thrt; InThreading(T); /中序遍历进行中序线索化中序遍历进行中序线索化 pre-rchild=Thrt;pre-RTag=Thread; /最后一个结点线索最后一个结点线索化化 Thrt-rchild=pre; return;void InThreading(BiThrTree p) if(p) InThreading(p-lchild); /左子树线索化左子树线索化 if(!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if(!pre-rchild) /后继线索后继线索 pre-RTa

20、g=Thread; pre-rchild=p; pre=p; /保持保持pre 指向指向p的前驱的前驱 InThreading(p-rchild); /右子树线索化右子树线索化 return;1 1、树的存储结构、树的存储结构双亲表示双亲表示：以一组连续空间存储树的结点，：以一组连续空间存储树的结点，同时在同时在结点中附设一个指针，存放双亲结点结点中附设一个指针，存放双亲结点在链表中的位置。在链表中的位置。ABCDEFGdataparentA B C D E F G- -1 0 0 0 1 1 30 1 2 3 4 5 6用双亲表示实现的树定义用双亲表示实现的树定义#define MaxSiz

21、e /最大结点个数最大结点个数typedef struct /树结点定义树结点定义 ElemType data; int parent; PTNode;typedef struct PTNode nodesMaxSize; /树树 int r,n;PTree;ABCDEFG孩子链表表示法孩子链表表示法第一种解决方案第一种解决方案 等长的链域等长的链域 data child1child2childd1变长的链域变长的链域 data child1child2childd2空链域n(k-1)+1第二种解决方案第二种解决方案 0A1B2C 3D4E 5F 6G 1ABCDEFG23 45 6 CTNo

22、deCTBoxCTree孩子链表表示法存储结构孩子链表表示法存储结构typedef struct CTNode int child; struct CTNode *next; *ChildPtr;typedef struct char data; ChildPtr firstchild;CTBox;typedef struct CTBox nodesMAX_TREE_SIZE; int r,n;CTree;结点结构结点结构 datafirstChildnextSiblingABCDEFG空链域n+1个n树的孩子树的孩子- -兄弟表示兄弟表示（二叉链表表示二叉链表表示）BCDGFE A type

23、def char ElemType;typedef struct ElemType data; struct node *firstChild, *nextSibling;CSNode,*CSTree;n用左子女用左子女- -右兄弟表示实现的树定义右兄弟表示实现的树定义T1 T2 T3T1 T2 T3AFHB C DGIJEKAFBCDEGHIKJABCEDHIKJFG3 棵树的森林各棵树的二叉树表示森林的二叉树表示2、森林与二叉树的转换、森林与二叉树的转换树的二叉树表示树的二叉树表示:3、树的遍、树的遍历历n深度优先遍历深度优先遍历u 先序遍历先序遍历u 后序遍历后序遍历ABCDE FGAB

24、CEDGF左孩子右兄弟深度优先遍历深度优先遍历n当树非空时当树非空时u 访问根结点访问根结点u 依次先根遍历根的各棵子树依次先根遍历根的各棵子树n树先根遍历树先根遍历 ABEFCDGn对应二叉树前序遍历对应二叉树前序遍历 ABEFCDGn树的先根遍历结果与其对应二叉树树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同表示的前序遍历结果相同n树的先根遍历可以借助对应二叉树的前序遍历树的先根遍历可以借助对应二叉树的前序遍历算法实现算法实现ABCEDGF树的树的先序先序遍遍历历树的树的后序后序遍历遍历:n当树非空时当树非空时u依次后根遍历根的各棵子树依次后根遍历根的各棵子树u访问根结点访问根结点

25、n树后根遍历树后根遍历 EFBCGDAn对应二叉树中序遍历对应二叉树中序遍历 EFBCGDAn树的后根遍历结果与其对应二叉树树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同表示的中序遍历结果相同n树的后根遍历可以借助对应二叉树的中序遍历算树的后根遍历可以借助对应二叉树的中序遍历算法实现法实现ABCEDGF路径长度路径长度 (Path Length) 从树中一个结点到另一个结点之间的从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。分支构成这两个结点之间的路径。 树的外部路径长度是各叶结点树的外部路径长度是各叶结点(外结点外结点)到根结点的路径长度之和到根结点的路径长度之和 E

26、PL。 树的内部路径长度是各非叶结点树的内部路径长度是各非叶结点(内结点内结点)到根结点的路径长度之和到根结点的路径长度之和 IPL。 树的路径长度树的路径长度 PL = EPL + IPL1 1、基本概念、基本概念123456782345678树的外部路径长度树的外部路径长度EPL = 3*1+2*3 = 9树的外部路径长度树的外部路径长度EPL = 1*1+2*1+3*1+4*1 = 101带权路径长度带权路径长度 (Weighted Path Length, WPL)树的的带权树的的带权 路径长度路径长度是树的各叶结点所是树的各叶结点所带的权值带的权值 wi 与该结点到根的路径长度与该结

27、点到根的路径长度 li 的乘的乘积之和。积之和。10niiilwWPLWPL = 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 = 35 222444555777带权路径带权路径长度达到最小长度达到最小2 2、霍夫曼树、霍夫曼树n带权路径长度达到最小的二叉树即为霍夫带权路径长度达到最小的二叉树即为霍夫曼树。曼树。n在霍夫曼树中，权值大的结点离根最近在霍夫曼树中，权值大的结点离根最近。(1) 由给定的由给定的 n 个权值个权值 w0, w1, w2, , wn-1，构造具有构造具有 n 棵二

28、叉树的集合棵二叉树的集合 F = T0, T1, T2, , Tn-1 ，其中每棵二叉树，其中每棵二叉树 Ti 只有一只有一 个带权个带权 wi 的的根结点根结点, 其左、右子树均为空。其左、右子树均为空。 3 3、如何构造霍夫曼树、如何构造霍夫曼树- -霍夫曼霍夫曼算法算法(2) 重复以下步骤重复以下步骤, 直到直到 F 中仅剩下一棵中仅剩下一棵树为止：树为止： 在在 F 中选取两棵根结点的权值最小的中选取两棵根结点的权值最小的二叉树二叉树, 做为左、右子树构造一棵新的二做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权

29、值之和。左、右子树上根结点的权值之和。 在在 F 中删去这两棵二叉树。中删去这两棵二叉树。 把新的二叉树加入把新的二叉树加入 F。F : 7 5 2 4F : 7 5 6F : 7 11 7524初始合并2 475246F : 18 1175246合并5 65合并7 11 27461118举例：霍夫曼树的构造过程举例：霍夫曼树的构造过程5274Weight parent leftChild rightChild7 -1 -1 -15 -1 -1 -12 -1 -1 -14 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -10123456上例存储结构上例存储结构初初 态态52

30、746Weight parent leftChild rightChild 7 -1 -1 -1 5 -1 -1 -1 2 -1 -1 -1 4 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -10123456p1p24423i过过 程程5274611Weight parent leftChild rightChild 7 -1 -1 -1 5 -1 -1 -1 2 4 -1 -1 4 4 -1 -1 6 -1 2 311 -1 -1 -1 -1 -1 -10123456p1p25514i5274611Weight parent leftChild rightChild

31、 7 -1 -1 -1 5 5 -1 -1 2 4 -1 -1 4 4 -1 -1 6 5 2 311 -1 1 418 -1 -1 -10123456p1p26605i18终终 态态3、霍夫曼编码、霍夫曼编码主要用途是实现数据压缩。主要用途是实现数据压缩。 设给出一段报文：设给出一段报文： CAST CAST SAT AT A TASA 字符集合是字符集合是 C, A, S, T ，各个字符出现，各个字符出现的频度的频度(次数次数)是是 W 2, 7, 4, 5 。 若给每个字符以等长编码若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11则总编码长度为则总编码长度

32、为 ( 2+7+4+5 ) * 2 = 36. 若按各个字符出现的概率不同而给予不等若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。长编码，可望减少总编码长度。 各字符出现概率为各字符出现概率为 2/18, 7/18, 4/18, 5/18 ,化整为化整为 2, 7, 4, 5 。以它们为各叶结点上的。以它们为各叶结点上的权值权值, 建立霍夫曼树。建立霍夫曼树。左分支赋左分支赋 0，右分支赋，右分支赋 1，得霍夫曼编码，得霍夫曼编码(变长编码变长编码)。7254010011A : 0 T : 10 C : 110 S : 111它的总它的总编码长度：编码长度：7*1+5*2+(

33、 2+4 )*3 = 35。比等长编码的情形要短。比等长编码的情形要短。 总编码长度总编码长度正好正好等于霍夫等于霍夫曼树的带权路径长度曼树的带权路径长度WPL。 霍夫曼编码是一种霍夫曼编码是一种前缀前缀编码，即任何一个字符的编码，即任何一个字符的编码都不是另一个字符的编码都不是另一个字符的编码的前缀编码的前缀。解码时不会混淆。解码时不会混淆。霍夫曼编码树霍夫曼编码树0001112457解码方向解码方向编码方向编码方向const int n = 20;/叶结点数叶结点数const int m = 2*n - -1;/结点数结点数 typedef struct unsigned int weight; int parent, lchild, rchild; HTNode; *HuffmanTree;/动态分配数组存储动态分配数组存储霍夫曼树霍夫曼树typedef char *HuffmanCode;/动态分配数组存储动态分配数组存储霍夫曼霍夫曼编码表编码表4、霍夫曼树和霍夫曼编码的存储表示、霍夫曼树和霍夫曼编码的存储表示5、求霍夫曼编码的算法、求霍夫曼编码的算法演示演示void HuffmanCode ( HuffmanTree &HT, HuffmanCode &HC,int *w,int n ) /w存放存放n个字符的权值，构造霍夫曼树个字符的权值，构造霍夫曼