第六章 树和二叉树

1、第第6 6章章 树和二叉树树和二叉树树是一类重要的非线性数据结构，是以分支树是一类重要的非线性数据结构，是以分支关系定义的层次结构关系定义的层次结构6.1 树的定义和基本术语树的定义和基本术语一、树的定义一、树的定义 树是有树是有 n (n 0) 个结点的有限集合。如果个结点的有限集合。如果 n=0，称，称为为空树空树；如果；如果 n 0，则：，则：有且仅有一个特定的称之为有且仅有一个特定的称之为根根(Root)的结点，它的结点，它只有直接后继，但没有直接前驱；只有直接后继，但没有直接前驱；当当n 1，除根以外的其它结点划分为，除根以外的其它结点划分为 m (m 0) 个互不相交的有限集个互不

2、相交的有限集 T1, T2 , Tm，其中每个集合，其中每个集合本身又是一棵树，并且称为根的本身又是一棵树，并且称为根的子树子树(SubTree)。例如例如:A只有根结点的树只有根结点的树其中：其中：A是根；其余结点分成三个互不相交的子集，是根；其余结点分成三个互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根都是根A的的子树，且本身也是一棵树子树，且本身也是一棵树有有13个结点的树个结点的树ACGBDEFKLHMIJ子树树结构的四种表示方法：树结构的四种表示方法：2)括号表示法：括号表示法：(A(B(E(K,L),F),C(G),D(

3、H(M),I,J)FKLEBMHIJDGCA3)嵌套集合表示法嵌套集合表示法ABEKLFCGDHMIJ4)凹入表示法凹入表示法ACGBDEFKLHMIJ1)倒立树表示法倒立树表示法二、树的基本术语二、树的基本术语树的结点树的结点:包含一个数据元素及若干指向其子树的分支包含一个数据元素及若干指向其子树的分支孩子结点孩子结点:结点的子树的根称为该结点的孩子结点的子树的根称为该结点的孩子双亲结点双亲结点:B结点是结点是A结点的孩子结点的孩子,则则A结点是结点是B结点的双亲结点的双亲兄弟结点兄弟结点:同一双亲的孩子结点同一双亲的孩子结点堂兄结点堂兄结点:同一层上，不同一双亲的结点同一层上，不同一双亲的

4、结点结点层结点层:根结点的层定义为根结点的层定义为1,根的孩子为第根的孩子为第2层结点层结点树的高度（深度）树的高度（深度）:树中结点的最大层次数树中结点的最大层次数结点的度结点的度:结点的子树个数结点的子树个数树的度树的度: 树中各结点的度的最大值树中各结点的度的最大值叶子结点叶子结点:也叫终端结点，是度为也叫终端结点，是度为0的结点的结点分枝结点分枝结点:度不为度不为0的结点；的结点；森林森林:互不相交的树集合；互不相交的树集合；有序树有序树:子树从左到右有序子树从左到右有序,(即左右子树不能互换即左右子树不能互换)无序树无序树:不考虑子树的左右顺序；不考虑子树的左右顺序；结点结点A的度：

5、的度：结点结点B的度：的度：结点结点M的度：的度：叶子：叶子：结点结点A的孩子：的孩子：结点结点B的孩子：的孩子：结点结点I的双亲：的双亲：结点结点L的双亲：的双亲：结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：结点结点A的层次：的层次：结点结点M的层次：的层次：树的深度：树的深度：结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先320B,C,DE,F314K，L，F，G，M，I，JDE4ACGBDEFKLHMIJ 1）InitTree(&T); 2）DestroyTree(&T); 3）CreateTree(&T, de

6、finition); 4）ClearTree(&T); 5）TreeEmpty(T); 6）TreeDepth(T); 7） Root(T); 8） Value(T, &cur_e); 9） Assign(T, cur_e, value); 10）Parent(T, cur_e); 11）LeftChild(T, cur_e); 12）RightSibling(T, cur_e); 13）InsertChild(&T, &p, i, c); 14）DeleteChild(&T,&p, i); 15）TraverseTree(T, Visit( )

7、;三、树的基本操作三、树的基本操作62175 438910 11 12五种基本形态：五种基本形态：一棵二叉树是结点的一个有限集合，该集合或者为空，一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成的、互不相交的二叉树组成LLRR6.2 二叉树二叉树一、定义一、定义每个结点至多有二棵子树每个结点至多有二棵子树( (即不存在度大于即不存在度大于2 2的结点的结点) )二叉树的子树有左、右之分，且其次序不能任意颠倒二叉树的子树有左、右之分，且其次序不能任意颠倒特点特点：1、满二叉树、

8、满二叉树 (Full Binary Tree) 一棵深度为一棵深度为k且有且有2k-1个结点的二叉树个结点的二叉树二、两种特殊形态的二叉树二、两种特殊形态的二叉树621754389 10 1113 14 1512满二叉树满二叉树2、完全二叉树、完全二叉树 (Complete Binary Tree) 若设二叉树的高度为若设二叉树的高度为h，则共有，则共有h层，除第层，除第 h 层外，层外，其它各层其它各层 (1 h-1) 的结点数都达到最大个数，第的结点数都达到最大个数，第 h 层从右向左层从右向左连续连续缺若干结点缺若干结点 每个结点都与深度为每个结点都与深度为k的满二叉树中编号从的满二叉树

9、中编号从1到到n结结点一一对应点一一对应621754389 10 11 12完全二叉树完全二叉树215436 7216543非完全二叉树非完全二叉树性质性质1 在二叉树的第在二叉树的第 i 层上至多有层上至多有 2i-1个结点。个结点。(i 1) 证明用归纳法证明用归纳法证明：证明：当当i=1时，只有根结点，时，只有根结点，2i-1=20=1假设对所有假设对所有j，ij 1，命题成立，即第，命题成立，即第j层上至多有层上至多有2j-1 个结点个结点由归纳假设第由归纳假设第i-1 层上至多有层上至多有 2i-2个结点个结点由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2，故在第，故

10、在第i层上的最层上的最大结点数为第大结点数为第i-1层上的最大结点数的层上的最大结点数的2倍，即倍，即2*2i-2= 2i-16.2.2 6.2.2 二叉树的性质二叉树的性质性质性质2 深度为深度为 k 的二叉树至多有的二叉树至多有 2k-1个结点个结点(k 1)kii112 20 + 21 + + 2k-1 = 2k-1kii1(层上的最大结点数）第证明：证明：由性质由性质1可见，深度为可见，深度为k的二叉树的最大结点数的二叉树的最大结点数性质性质3 对任何一棵二叉树对任何一棵二叉树T, 如果其叶子结点数为如果其叶子结点数为n0, 度为度为2的结点数为的结点数为 n2,则则n0n21.证明证

11、明:若度为若度为1的结点有的结点有 n1 个，个，结点个数为，结点个数为 n，则：则：n = n0 + n1 + n2 若总边数为若总边数为 e e，则根据二叉树的定义有：，则根据二叉树的定义有：e = 2n2 + n1 = n - 1因此，有因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1 证明：证明：设完全二叉树的深度为设完全二叉树的深度为 k，则根据性质，则根据性质2和完全和完全二叉树的定义有二叉树的定义有2k-1 - 1 n 2k- 1或或 2k-1 n 2k取对数取对数 k-1 log2n 1，则其双亲是结点，则其双亲是

12、结点 i/2 2)如果如果2in，则结点，则结点i为叶子结点，无左孩子；为叶子结点，无左孩子； 否则，其左孩子是结点否则，其左孩子是结点2i3)如果如果2i1n，则结点，则结点i无右孩子；无右孩子； 否则，其右孩子是结点否则，其右孩子是结点2i162175438910 11 12练习：练习：1、设树、设树T的度为的度为4，其中度为，其中度为1,2,3,4的结点个数分的结点个数分别为别为4,2,1,1。T有多少个叶子叶子结点？有多少个叶子叶子结点？2、设一棵完全二叉树有、设一棵完全二叉树有1000个结点。问该完全二个结点。问该完全二叉树有多少个叶子结点？有多少个度为叉树有多少个叶子结点？有多少个

13、度为2的结点？的结点？有多少个度为有多少个度为1的结点？若完全二叉树有的结点？若完全二叉树有1001个结个结点，再回答上述问题，并说明理由。点，再回答上述问题，并说明理由。 1、解：各结点射出的分支总数为：、解：各结点射出的分支总数为： 4*1+2*2+1*3+4*1=15即树中总结点为：即树中总结点为：15+1=16由条件可知非叶子结点数为：由条件可知非叶子结点数为：4+2+1+1=8即叶子结点个数为：即叶子结点个数为：16-8=82、解：若完全二叉树中结点总数为偶数，则：、解：若完全二叉树中结点总数为偶数，则：n1=1,n0=n2+1;即此题中：即此题中：n0=500,n1=1,n2=49

14、9若完全二叉树中结点总数为奇数，则：若完全二叉树中结点总数为奇数，则： n1=0,n0=n2+1;即此题中：即此题中：n0=501,n1=0,n2=500完全二叉树完全二叉树 的顺序表示的顺序表示6.2.36.2.3 、二叉树的存储结构、二叉树的存储结构12489 105673一、顺序表示一、顺序表示1 2 3 4 5 6 7 8 9 10第第i个结点的左右孩子一定个结点的左右孩子一定保存在第保存在第2i和和2i+1号单元里号单元里缺点缺点:浪费空间。最坏的情况下，深度为浪费空间。最坏的情况下，深度为k且只有且只有k个个结点的单支树，却需要长度为结点的单支树，却需要长度为2k-1的一维数组的一

15、维数组9123654789 10一般二叉树的顺序表示一般二叉树的顺序表示1090000876504321二、链表表示二、链表表示含两个指针域的结点结含两个指针域的结点结构构lChild data rChild含三个指针域的结点结含三个指针域的结点结构构lChild data parent rChild二叉链表二叉链表 data lChildrChild三叉链表三叉链表parent data lChildrChildlchild data rchild ABCDEFG AB C D E F Gtypedef struct BiTNode TElemType data; struct BiTNod

16、e *lchild , *rchild ; BiTNode , *BiTree ;1、二叉链表的存储表示、二叉链表的存储表示在在n个结点的二叉链表中有个结点的二叉链表中有n+1个空链域个空链域lchild data parent rchild A B C D E F Gtypedef struct BiTNode TElemType data; struct BiTNode *lchild , *rchild, *parent ; BiTNode , *BiTree ;2、三叉链表的存储表示、三叉链表的存储表示ABCDEFG遍历：遍历：按某种搜索路径访问二叉树的每个结点，而且按某种搜索路径访问

17、二叉树的每个结点，而且每个结点仅被访问一次每个结点仅被访问一次访问：访问：含义很广，可以是对结点的各种处理，如修改含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据结点数据、输出结点数据二叉树是非线性结构，每个结点可能有两个后继，如何二叉树是非线性结构，每个结点可能有两个后继，如何访问二叉树的每个结点，而且每个结点仅被访问一次？访问二叉树的每个结点，而且每个结点仅被访问一次？6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树遍历是各种数据结构最基本的操作，许多其他的操作遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现可以在遍历基础上实现对于线性结构由于每个结点只

18、有一个直接后继，遍历对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事是很容易的事一、二叉树的遍历方法一、二叉树的遍历方法令令:L:遍历左子树遍历左子树 D:访问根结点访问根结点 R:遍历右子树遍历右子树有六种遍历方法有六种遍历方法: DLR，LDR，LRD,DRL，RDL，RLD先左后右先左后右,有三种遍历方法：有三种遍历方法： DLR、LDR、LRD ，分别称为分别称为先序遍历、中序遍历、后序遍历先序遍历、中序遍历、后序遍历二叉树的遍历可以分解为二叉树的遍历可以分解为:访问根，遍历左子树和遍访问根，遍历左子树和遍历右子树历右子树 A A B B D D C C E E F F G

19、G1、先序遍历（、先序遍历（DLR）若二叉树非空若二叉树非空 (1)访问根结点；访问根结点； (2)先序遍历左子树；先序遍历左子树； (3)先序遍历右子树；先序遍历右子树； 先序遍历序列：先序遍历序列：A B D E G C F例例:先序遍历右图所示的二叉树先序遍历右图所示的二叉树 （1）访问根结点）访问根结点A （2）先序遍历左子树）先序遍历左子树 （3）先序遍历右子树）先序遍历右子树 A A B B D D C C E E F F G G2、中序遍历（、中序遍历（LDR）若二叉树非空若二叉树非空(1)中序遍历左子树中序遍历左子树(2)访问根结点访问根结点(3)中序遍历右子树中序遍历右子树

20、中序遍历序列：中序遍历序列： D B G E A C F例例:中序遍历右图所示的二叉树中序遍历右图所示的二叉树 （1）中序遍历左子树）中序遍历左子树 （2）访问根结点）访问根结点A （3）中序遍历右子树）中序遍历右子树 A A B B D D C C E E F F G G3、后序遍历（、后序遍历（LRD）若二叉树非空若二叉树非空(1)后序遍历左子树后序遍历左子树(2)后序遍历右子树后序遍历右子树(3)访问根结点访问根结点 后序遍历序列：后序遍历序列： D G E B F C A例：例：后序遍历右图所示的二叉树后序遍历右图所示的二叉树 （1）后序遍历左子树）后序遍历左子树 （2）后序遍历右子树

21、）后序遍历右子树 （3）访问根结点）访问根结点A A A B B D D C C E E F F G G 先序遍历序列：先序遍历序列：例例:用二叉树表示表达式用二叉树表示表达式 a+b*(c-d)-e/f- + a * b c d / e f 前缀式前缀式(波兰式波兰式)中序遍历序列：中序遍历序列：a + b * c d e / f 中缀式中缀式后序遍历序列：后序遍历序列：a b c d - * + e f / - 后缀式后缀式(逆波兰式逆波兰式) 若二叉树非空若二叉树非空 （1）访问根结点；）访问根结点； （2）先序遍历左子树）先序遍历左子树 （3）先序遍历右子树；）先序遍历右子树；二、遍历

22、的递归算法二、遍历的递归算法 上面介绍了三种遍历方法，显然可以用递归的方式实现上面介绍了三种遍历方法，显然可以用递归的方式实现三种遍历方法，以先序为例：三种遍历方法，以先序为例：先序遍历的定义：先序遍历的定义：先序遍历递归算法先序遍历递归算法void PreOrderTraverse(BiTree T) if (T) printf(T-data)； PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); A A B B D D C C E E F F G G H H I I J J K K L L三、三、 遍历的非递归算法遍历的非递归算法

23、(以中序遍历为例以中序遍历为例)中序遍历序列：中序遍历序列： H D K I L B E J A F C G A A B B D D C C E E F F G G H H I I J J K K L Lvoid InOrderTraverse(BiTree T) InitStack(S); t=T; while (t) Push(S,t); t=t-lchild; if (!StackEmpty(S) Pop(S,t); printf(t-data); t=t-rchild; while(t | !StackEmpty(S) A A B B D D C C E E F F G G H H I

24、 I J J K K L Lvoid InOrderTraverse(BiTree T) InitStack(S); p=T; while(p|!StackEmpty(S) if(p) Push(S,p); p=p-lchild; else Pop(S,p);printf(p-data); p=p-rchild; A A B B D D C C E E F F G G H H I I J J K K L Lvoid InOrderTraverse(BiTree T) InitStack(S); Push(S,T); while(!StackEmpty(S) while(GetTop(S,p)&

25、amp;p) Push(S,p-lchild); Pop(S,p); if(!StackEmpty(S) Pop(S,p); printf(p-data); Push(S,p-rchild); A A B B D D C C E E F F G G H H I I J J K K L L四、二叉树的建立四、二叉树的建立基本思想：基本思想：输入输入在空子树处添加在空子树处添加*的二叉树的的二叉树的先序序列先序序列设每个元素是一个字符，按先序遍历的顺序，建立二叉设每个元素是一个字符，按先序遍历的顺序，建立二叉链表的所有结点，并完成相应结点的链接。链表的所有结点，并完成相应结点的链接。 D D A

26、A BB C C EE FFT T* * * * * * * *(在空子树处添加在空子树处添加*的二叉树的的二叉树的)先序序列：先序序列：A B D * F * * * C E * * * A A B B D D C C E E F F先序序列：先序序列：A B D F C E A A B B D D C C E E F FStatus CreateBiTree(BiTree &T) scanf (&ch); if (ch= = * ) T=NULL; else if (! (T=(BiTNode * )malloc(sizeof(BiTNode) exit(OVERFLOW)

27、; T-date = ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK; D D A A BB C C EE FFT T输入：输入：A B D * F * * * C E * * *五、利用中序、先序法或中序、后序法求二叉树五、利用中序、先序法或中序、后序法求二叉树1、利用中序、先序法求二叉树、利用中序、先序法求二叉树步骤步骤: (1)利用先序顺序可知：第一个是根利用先序顺序可知：第一个是根(2)利用中序顺序，配合步骤利用中序顺序，配合步骤(1)所找到的根作对所找到的根作对应，可分成左右两子树应，可分成左右两子树(3)再

28、分别按再分别按(1)(2)步骤处理左、右子树，找到其步骤处理左、右子树，找到其他的根和终端结点他的根和终端结点例例:中序序列中序序列: D C E F B H G A K J L I M 先序序列先序序列: A B C D E F G H I J K L M2、利用中序、后序法求二叉树、利用中序、后序法求二叉树步骤步骤: (1)利用后序顺序可知：最后一个一定是根利用后序顺序可知：最后一个一定是根(2)利用中序顺序，配合步骤利用中序顺序，配合步骤(1)所找到的根作对所找到的根作对应，可分成左右两子树应，可分成左右两子树(3)再分别按再分别按(1)(2)步骤来处理左、右子树步骤来处理左、右子树例例

29、:中序序列中序序列: D C E F B H G A K J L I M 后序序列后序序列: D F E C H G B K L J M I A练习：练习：1、已知中序序列、已知中序序列:DCEBAKJF 后序序列后序序列:DECBKJFA2、已知中序序列、已知中序序列:A-B*C+D/E*F 先序序列先序序列:/+-A*BCD*EF3、已知中序序列、已知中序序列:CBEDFAHJKIG 后序序列后序序列:CEFDBKJIHGAJ计算二叉树的结点个数计算二叉树的结点个数J求二叉树中叶子结点的个数求二叉树中叶子结点的个数J求二叉树的高度求二叉树的高度J按层次遍历二叉树按层次遍历二叉树六、线索二叉

30、树六、线索二叉树 (Threaded Binary Tree)1 1、基本概念、基本概念前驱与后继：在二叉树的先序、中序或后序遍历前驱与后继：在二叉树的先序、中序或后序遍历序列中，两个相邻的结点互称为序列中，两个相邻的结点互称为前驱与后继。前驱与后继。线索：指向前驱或后继结点的指针。线索：指向前驱或后继结点的指针。线索二叉树：加上线索的二叉链表表示的二叉树。线索二叉树：加上线索的二叉链表表示的二叉树。即加上结点前趋、后继信息的二叉树。即加上结点前趋、后继信息的二叉树。线索化：对二叉树按某种遍历次序使其变为线索线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程。二叉树的过程。有有n个结点的二

31、叉链表，有个结点的二叉链表，有n+1个空指针域，故可个空指针域，故可利用这些的空指针域存放结点的前趋和后继指针，利用这些的空指针域存放结点的前趋和后继指针，以这种结点构成的二叉链表称为以这种结点构成的二叉链表称为线索链表。线索链表。在线索二叉树的结点中增加两个标志域在线索二叉树的结点中增加两个标志域：Ltag=0, lchild指向其左孩子指向其左孩子1, lchild指向其前驱指向其前驱Rtag= 0, rchild指向其右孩子指向其右孩子1, rchild指向其后继指向其后继2、实现、实现结点结构结点结构LtagRtag线索链表的类型说明线索链表的类型说明typedef enum link

32、 , thread PointerTag; typedef struct BiThrNode TElemType data; Struct BiThrNode *lchild, *rchild; PointerTag Ltag, Rtag; BiThrNode，*BiThrTreeABCDE A B D C ET先序序列：ABCDE0000111111LtagRtag1）先序线索二叉树先序线索二叉树 A B D C ET中序序列：BCAED0000111111ABCDE2）中）中序线索二叉树序线索二叉树 A B D C ET后序序列：CBEDA0000111111ABCDE3）后）后序线索二叉

33、树序线索二叉树1、双亲表示：、双亲表示：通过保存每个结点的双亲结点的位置，通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系表示树中结点之间的结构关系6.4 树和森林树和森林一、树的存储结构一、树的存储结构typedef struct PTNode TElemType data; int parent; PTNode;parentdata存储实现时，以一组连续空间存储树的结点，同时在结存储实现时，以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。点中附设一个指针，存放双亲结点在链表中的位置。用双亲表示实现的树定义用双亲表示实现的树定义#define M

34、AX_TREE_SIZE 100typedef struct PTNode nodesMAX_TREE_SIZE; int r,n;/根位置，结点数根位置，结点数PTree; 如何找孩子结点如何找孩子结点?特点：特点：找结点的双亲容易，找结点的孩子难找结点的双亲容易，找结点的孩子难7 70 0T.nT.rABCDEFG3G1F1E0D0C0B-1Adata parent01234562、孩子表示法、孩子表示法通过保存每个结点的孩子结点的位置通过保存每个结点的孩子结点的位置,表示树中结点之间表示树中结点之间的结构关系的结构关系与双亲表示法相反与双亲表示法相反,孩子表示法适合实现涉及孩子的操作孩子

35、表示法适合实现涉及孩子的操作方法一方法一 ：多重链表（类似二叉链表）：多重链表（类似二叉链表）两种方式：定长结点两种方式：定长结点 不定长结点不定长结点1、定长结点定长结点等数量的链域等数量的链域 data child1child2child3childdABCDEFGABCDEFG 空链域空链域n(k-1)+1个个 data degree child1child2childd2、不定长结点不定长结点IACBDHGFE方法二：孩子链表方法二：孩子链表对树的每个结点用线性链表存贮它的孩子结点对树的每个结点用线性链表存贮它的孩子结点 1 3 2 8 7 6 4 5 IHGFE DC B A 0 1

36、 2 3 4 5 6 7 8 9 90 0T.nT.r树的孩子链表类型定义树的孩子链表类型定义typedef struct CTNode int child; struct CTNode * next; * ChildPtr; typedef struct TElemType data; ChildPtr firstchild; CTBox; typedef struct CTBox nodesMAX_TREE_SIZE; int n, r;CTree;0 1 2 3 4 5 6 7 8 9 90 0T.nodesT.nT.rIHGF E DC B A 1 3 2 8 7 6 4 5 特点：特

37、点：找结点的孩子容易，找结点的双亲难找结点的孩子容易，找结点的双亲难方法三：带双亲的孩子链表方法三：带双亲的孩子链表将双亲表示和孩子表示联合起来。将双亲表示和孩子表示联合起来。0 1 2 3 4 5 6 7 833211000-1 IHGF E DC B A 1 3 2 8 7 6 4 5 IACBDHGFE特点：特点：找结点的双亲和孩子都容易。找结点的双亲和孩子都容易。ABRECDFGHKP137图图6.14(b)方法四：孩子兄弟表示法方法四：孩子兄弟表示法用二叉链链表作为树的存贮结构用二叉链链表作为树的存贮结构结点结构：结点结构： datafirstchildnextsiblingtype

38、def struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;结构定义：结构定义：ABCDEFG空链域空链域n+1个个A BE F G D C 特点：特点：操作容易操作容易破坏了树的层次破坏了树的层次例如：例如：二叉树与树都可用二叉链表存贮，以二叉链表作中介，二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换可导出树与二叉树之间的转换树树根根结点结点X的第一个孩子的第一个孩子结点结点X紧邻的右兄弟紧邻的右兄弟二叉树二叉树 根根 结点结点X的左孩子的左孩子

39、 结点结点X的右孩子的右孩子二、树与二叉树的转换二、树与二叉树的转换I IA AC CD DH HG GF FE E树树B B二叉树二叉树F FI IA AB BH HG GE EC CD DA BE CG D H I F 树与二叉树的转换树与二叉树的转换I IA AC CD DH HG GF FE E树树B B二叉树二叉树F FI IA AB BH HG GE EC CD D树转换成的二叉树其右子树一定为空树转换成的二叉树其右子树一定为空森林：树的集合森林：树的集合 将森林中树的根看成兄弟，可用树的孩子兄弟表示将森林中树的根看成兄弟，可用树的孩子兄弟表示法来存储森林；用树与二叉树的转换方法，

40、进行森林与法来存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；可用树的遍历方法对森林进行遍历二叉树转换；可用树的遍历方法对森林进行遍历包含两棵树的森林包含两棵树的森林I IA AC CD DH HG GF FE EB B J J K K M M N N L L O O P PT1 T2 T3FGAB C DEHIJKABCEDHIKJFG森林的二叉树表示森林的二叉树表示森林与二叉树的转换森林与二叉树的转换ABCDEFGHIKJ树根相连树根相连三、树的遍历三、树的遍历先根次序遍历先根次序遍历后根次序遍历后根次序遍历对应二叉树先序遍历对应二叉树先序遍历 ABEFCGDHI树的先根遍历结果与

41、其对应二叉树树的先根遍历结果与其对应二叉树表示的先序遍历结果相同表示的先序遍历结果相同1、树的先根次序遍历、树的先根次序遍历I IA AC CB BD DH HG GF FE E当树非空时当树非空时 访问根结点访问根结点 依次先根遍历根的各棵子树依次先根遍历根的各棵子树树先根遍历树先根遍历 ABEFCGDHIF FI IA AB BD DH HG GC CE E二叉树二叉树2、树的后根次序遍历、树的后根次序遍历:对应二叉树中序遍历对应二叉树中序遍历 EFBGCHIDA树的后根遍历结果与其对应二叉树树的后根遍历结果与其对应二叉树表示的中序遍历结果相同表示的中序遍历结果相同当树非空时当树非空时依次

42、后根遍历根的各棵子树依次后根遍历根的各棵子树访问根结点访问根结点I IA AC CB BD DH HG GF FE E树后根遍历树后根遍历 EFBGCHIDAF FI IA AB BD DH HG GC CE E二叉树二叉树四、森林的遍历四、森林的遍历先序遍历先序遍历中序遍历中序遍历对应二叉树先序遍历对应二叉树先序遍历 ABCDEFGHIKJ1、森林的先序遍历、森林的先序遍历当森林非空时当森林非空时 访问森林中第一棵树的根结点访问森林中第一棵树的根结点 先序遍历第一棵树中根结点的子树森林先序遍历第一棵树中根结点的子树森林先序遍历除第一棵树外剩余的树构成的森林先序遍历除第一棵树外剩余的树构成的森

43、林T1 T2 T3FGAB C DEHIJKABCEDHIKJFG森林先序遍历森林先序遍历 ABCDEFGHIKJ对应二叉树中序遍历对应二叉树中序遍历 BCEDAGFKIJH2、森林的中序遍历、森林的中序遍历当森林非空时当森林非空时中序遍历森林中第一棵树的根结点的子树森林中序遍历森林中第一棵树的根结点的子树森林访问森林中第一棵树的根结点访问森林中第一棵树的根结点中序遍历除第一棵树外剩余的树构成的森林中序遍历除第一棵树外剩余的树构成的森林T1 T2 T3FGAB C DEHIJKABCEDHIKJFG森林中序遍历森林中序遍历BCEDAGFKIJH练习：练习：1、对以下两棵二叉树分别画出它们的顺序

44、存储结构、对以下两棵二叉树分别画出它们的顺序存储结构ABDEFCGIJKABDEFCIJABDEFCGH2、对右边的树，分别画出、对右边的树，分别画出孩子链表和孩子兄弟链表孩子链表和孩子兄弟链表存储结构存储结构3、分别画出下列树对应的二叉树、分别画出下列树对应的二叉树ABCABCABDEFCGHIJK4、将下列森林转化为相应的二叉树、将下列森林转化为相应的二叉树121415139101113245867ABD5、画出下列二叉树对应的森林、画出下列二叉树对应的森林ABDEFCGHIJKMJ路径路径:树中一个结点到另一结点间的分支树中一个结点到另一结点间的分支J路径长度路径长度(Path Leng

45、th):路径上的分支数路径上的分支数J树的外部路径长度树的外部路径长度:各叶结点各叶结点(外结点外结点)到根结点的路到根结点的路 径长度之和径长度之和 (EPL)J树的内部路径长度树的内部路径长度:各非叶结点各非叶结点(内结点内结点)到根结点的到根结点的 路径长度之和路径长度之和 (IPL)J树的路径长度树的路径长度:从根到每个叶子结点的路径长度之和从根到每个叶子结点的路径长度之和 PL = EPL + IPL6.5 哈夫曼树哈夫曼树及其应用及其应用一、最优二叉树一、最优二叉树(哈夫曼树哈夫曼树)12345678234567813*1+2*3 = 91*1+2*1+3*1+4*1 = 10EP

46、L =EPL =J树的带权路径长度树的带权路径长度 (Weighted Path Length) 树的各叶子结点所带的权值与该结点到根的路径长度树的各叶子结点所带的权值与该结点到根的路径长度的乘积的和的乘积的和10niiilwWPLJ结点的权结点的权:结点上被赋予的一定意义的实数结点上被赋予的一定意义的实数7*2+5*2+2*2+4*2=36带权路径长度带权路径长度达到最小达到最小abcd7524abcd4275abcd75244*1+2*2+7*3+5*3=447*1+5*2+2*3+4*3=35WPL=WPL=WPL=权值大的结点离根最近权值大的结点离根最近F : 7 5 2 4J哈夫曼树哈夫曼树(最优二叉树最优二叉树):带权路径长度带权路径长度WPL最小的二最小的二叉树叉树abcd7524二、哈夫曼树的建立二、哈夫曼树的建立1、编制一个将百分制转换成五级分制的程序、编制一个将百分制转换成五级分制的程序60?70?80?90?0.050.150.400.300.10NNNNYYYY80以上的数据需要以上的数据需要3次或次或3次以上比较才能