《树和二叉树 》PPT课件.ppt

《《树和二叉树 》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《树和二叉树 》PPT课件.ppt（113页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、曾祖父曾祖父 爷爷爷爷 二爷二爷 三爷三爷 父亲父亲 二叔二叔独生子独生子族谱族谱树是以分支关系定义的层次结构。树是以分支关系定义的层次结构。第十章第十章树树树型结构是一类重要的树型结构是一类重要的非线性非线性结构。结构。学习重点学习重点:树的基本概念树的基本概念 二叉树的基本概念、相关操作二叉树的基本概念、相关操作 树和森林与二叉树之间的相互转换树和森林与二叉树之间的相互转换 二叉树的应用二叉树的应用第十章第十章树树树的定义和基本术语树的定义和基本术语树树(Tree):是具有层次结构的是具有层次结构的 n(n0)个结点的有限集。个结点的有限集。ABCDEFGHIJKLM一般树一般树第第十十章

2、章树树只有根结点的树只有根结点的树A树树(Tree):是是 n(n0)个结点的有限集。个结点的有限集。n0，有且仅有一个称为，有且仅有一个称为根根的结点。的结点。n1，除根结点外，其余结点可分为，除根结点外，其余结点可分为 m(m0)个互个互不相交的有限子集不相交的有限子集 T1,T2,Tm，其中每个子集都，其中每个子集都称为称为根结点的子树根结点的子树。A.T1T2Tmn1第十章第十章树和二叉树树和二叉树基本术语基本术语结点结点(node)表示树中的元素，包括数据项及若干表示树中的元素，包括数据项及若干指向其子树的分支指向其子树的分支结点的度结点的度(degree)结点拥有的子树数结点拥有的

3、子树数叶子叶子(leaf)度为度为0的结点的结点孩子孩子(child)结点子树的根称为该结点的孩子结点子树的根称为该结点的孩子双亲双亲(parents)孩子结点的上层结点叫该结点的孩子结点的上层结点叫该结点的兄弟兄弟(sibling)同一双亲的孩子同一双亲的孩子树的度树的度一棵树中最大的结点度数一棵树中最大的结点度数深度深度(depth)树中结点的最大层次数树中结点的最大层次数第十章第十章树和二叉树树和二叉树ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0叶子：叶子：K，L，F，G，M，I，J结点结点A的孩子：的孩子：B，C，D结点结点B的孩子

4、：的孩子：E，F结点结点I的双亲：的双亲：D结点结点L的双亲：的双亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：3结点结点A的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先第十章第十章树和二叉树树和二叉树树的其它表示方法树的其它表示方法 a.嵌套集合嵌套集合大集合表示树，小集合表示子树，相互嵌套。大集合表示树，小集合表示子树，相互嵌套。ABDCEFK LGHJIM第六章第六章树树b.层次表示法层次表示法类似书的编目类似书的编目ABCDEFGHIJKLM第六章第六章树树二叉树

5、二叉树二叉树的定义二叉树的定义二叉树二叉树是是 n(n0)个结点的有限集，它或者是个结点的有限集，它或者是空集空集，或者是由，或者是由一个一个根根和称为和称为左、右子树左、右子树的两个互不相交的的两个互不相交的二叉树二叉树组成组成。二叉树是一个二叉树是一个递归定义递归定义。树的子树次序不作规定，二叉树的两个子树有树的子树次序不作规定，二叉树的两个子树有左、右之分左、右之分。树中结点的度没有限制，二叉树中结点的度只能取树中结点的度没有限制，二叉树中结点的度只能取 0、1、2。空二叉树空二叉树ABCDEF一般二一般二叉树叉树根根左子树左子树右子右子树树第十章第十章树和二叉树树和二叉树根据定义，二叉

6、树通常具有根据定义，二叉树通常具有 5 种基本形态种基本形态:空二叉树空二叉树A仅有根结点的二叉树仅有根结点的二叉树A右子树为空的二叉树右子树为空的二叉树A左、右子树均非空左、右子树均非空的二叉树的二叉树A左子树为空的二叉树左子树为空的二叉树关于树的基本术语也都适用于二叉树。关于树的基本术语也都适用于二叉树。二叉二叉树与与树的区的区别树：1、树最少有一个根最少有一个根结点（点（n0）2、树的度的度 03、树不要求子不要求子树顺序序二叉二叉树：1、二叉、二叉树可以可以为空空(n0)2、二叉、二叉树的度的度23、二叉、二叉树是有序是有序树，有左、右子，有左、右子树之分。之分。例例10-1：试写出具

7、有写出具有3个个结点的所有不同形点的所有不同形态的的树和二叉和二叉树。二叉树的性质二叉树的性质性质性质1:在二叉树的第在二叉树的第 i 层上至多有层上至多有 2i-1 个结点个结点(i1)。归纳法证明归纳法证明:(1)i=1，只有一个根结点，只有一个根结点，2i-1=20=1，正确；，正确；(2)假设假设 i-1-1 成立，即第成立，即第 i-1-1 层上至多有层上至多有 2i-2 个结点；个结点；(3)由于二叉树的结点的度至多为由于二叉树的结点的度至多为 2，故在第，故在第 i 层上层上的最大结点数为第的最大结点数为第 i-1-1 层上的最大结点数的层上的最大结点数的 2 倍，即倍，即2 2

8、i-2=2i-1。性质性质2:深度为深度为 k 的二叉树至多有的二叉树至多有 2k 11 个结点个结点(k1)。i=1k(第第 i 层上的最大结点数层上的最大结点数)i=1k2i-1 2k 11练习练习:归纳法证明。归纳法证明。引论引论:一棵树有一棵树有 n 个结点，则必有个结点，则必有 n 1 条分支。条分支。证明证明:除根结点外，其它结点都有一个分支进入，除根结点外，其它结点都有一个分支进入，设设 B 为分支总数，故为分支总数，故 n=B+1，故故 B=n-1得证。得证。ABCDEF性质性质3:对任何一棵二叉树对任何一棵二叉树 T，如果其终端结点数为，如果其终端结点数为 n0，度为度为 2

9、 的结点数为的结点数为 n2，则，则 n0=n2+1。证明证明:(1)已知，终端结点数为已知，终端结点数为 n0，度为，度为 2 的结点数为的结点数为 n2，设度为设度为 1 的结点数为的结点数为 n1，由于二叉树中的所有结点的度只能为由于二叉树中的所有结点的度只能为 0、1、2，故二叉树的结点总数为故二叉树的结点总数为 n=n0+n1+n2；(2)除根结点外，其它结点都有一个分支进入，除根结点外，其它结点都有一个分支进入，设设 B 为分支总数，故为分支总数，故 n=B+1，由于这些分支均是由度为由于这些分支均是由度为 1 或或 2 的结点引出的，的结点引出的，所以有所以有 B=n1+2n2，

10、故，故 n=n1+2n2+1，由由(1)和和(2)，可得，可得 n0+n1+n2=n1+2n2+1，故有故有 n0=n2+1。两种特殊形态二叉树两种特殊形态二叉树:满二叉树满二叉树、完全二叉树完全二叉树。一棵深度为一棵深度为 k 且有且有 2k-1 个结点的二叉树称为个结点的二叉树称为满二叉树满二叉树。特点特点:1 24 5满二叉树满二叉树3 67(1)每一层的结点数都达到每一层的结点数都达到最大结点数最大结点数。(2)叶子结点在叶子结点在最大层最大层。(3)任一结点，其左、右分支下的子孙的任一结点，其左、右分支下的子孙的最大层次相等最大层次相等。对满二叉树的结点进行连续编号，从根结点起，自上

11、而下，对满二叉树的结点进行连续编号，从根结点起，自上而下，自左至右，自左至右，1、2、3、2k-1。深度为深度为 k 的，有的，有 n 个结点的二叉树，个结点的二叉树，当且仅当当且仅当其每一个结其每一个结点都与深度为点都与深度为 k 的满二叉树中编号从的满二叉树中编号从 1 至至 n 的结点一一对的结点一一对应时，称为应时，称为完全二叉树完全二叉树。1 24 53 6 1 23 4 5非完全二叉树非完全二叉树 1 24 53完全二叉树完全二叉树(1)特点特点:(1)叶子结点只可能在层次最大的两层上出现。叶子结点只可能在层次最大的两层上出现。(2)对任一结点，若其右分支的子孙的最大层次为对任一结

12、点，若其右分支的子孙的最大层次为 l，则，则其左分支下的子孙的最大层次必为其左分支下的子孙的最大层次必为 l 或或 l+1。完全二叉树完全二叉树(2)1 24 53 67满二叉二叉树和完全二叉和完全二叉树的区的区别：1、满二叉二叉树一定是完全二叉一定是完全二叉树，它是完全二叉，它是完全二叉树的特例。的特例。2、完全二叉、完全二叉树不一定是不一定是满二叉二叉树。3、满二叉二叉树中中n1=0，完全二叉，完全二叉树中中n1=0或或1.性质性质4:具有具有 n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n+1。证明证明:设设 n 结点完全二叉树的深度为结点完全二叉树的深度为 k，k

13、 层满二叉层满二叉树结点数树结点数k 层完全二层完全二叉树结点数叉树结点数k-1 层满二层满二叉树结点数叉树结点数因为，因为，故故 2k-1-1-1 n 2k-1 有有 2k-1-1 n 2k又又 k-1 log2n k因为因为 k 是整数，所以是整数，所以 k=log2n+1。性质性质5:如果对一棵有如果对一棵有n个结点的完全二叉树的结点按层序个结点的完全二叉树的结点按层序编号编号(从第从第 1 层到第层到第 log2n+1 层，每层从层，每层从左左到到右右)，则，则对任一结点对任一结点 i(1in)，有，有(1)如果如果 i=1，则结点，则结点 i 为根，无父亲；如果为根，无父亲；如果 i

14、 1，则结点，则结点 i 的父结点的父结点 parent(i)是结点是结点 i/2。/求父亲求父亲(2)如果如果 2i n，则结点，则结点 i 的左儿子的左儿子 LChild(i)是结点是结点 2i；否则无；否则无左儿子。左儿子。/求左儿子求左儿子(3)如果如果 2i+1 n，则结点，则结点 i 的右儿子的右儿子 RChild(i)是结点是结点 2i+1；否；否则无右儿子。则无右儿子。/求右儿子求右儿子证明证明(1):如果如果(2)、(3)成立，则成立，则(1)成立。成立。证明证明(2)和和(3):归纳法归纳法若有左儿子，应为若有左儿子，应为 2i=2；i=1:根结点根结点 1 23若有右儿子

15、，应为若有右儿子，应为 2i+1=3；设对结点设对结点 i 成立，即结点成立，即结点 i 的左儿子为结点的左儿子为结点 2i，右儿子为结点，右儿子为结点 2i+1；求证对结点求证对结点 i+1 也成立也成立:完全二叉树中，结点完全二叉树中，结点 i 和结点和结点 i+1 之间的关系通常有两种情况，之间的关系通常有两种情况，或在或在同一层同一层上，或分别在上，或分别在相邻两层相邻两层上，且上，且最左和最右最左和最右。i+1i2i2i+1 2i+22i+3情况情况 1i+1i2i2i+12i+22i+3情况情况 2i+1i2i2i+1 2i+22i+3情况情况 1i+1i2i2i+12i+22i+

16、3情况情况 2结点结点 i+1 的儿子的序号一定紧挨在结点的儿子的序号一定紧挨在结点 i 的儿子的序号的后面，的儿子的序号的后面，根据归纳假设，结点根据归纳假设，结点 i 的儿子的序号为的儿子的序号为 2i 和和2i+1，则结点则结点 i+1 的左、右儿子的序号应为的左、右儿子的序号应为2i+2=2(i+1)、2i+3=2(i+1)+1。若若 2(i+1)+1n 则无右儿子，若则无右儿子，若 2(i+1)n 则无左儿子。则无左儿子。得证。得证。二叉树的存储结构二叉树的存储结构(顺序、链式顺序、链式)1.顺序存储结构顺序存储结构用一组用一组地址连续地址连续的存储单元依次的存储单元依次自上而下、自

17、左至右自上而下、自左至右存储二叉树上的结点元素。存储二叉树上的结点元素。#define MAX_TREE_SIZE 100typedef TElemType SqBiTreeMAX_TREE_SIZE 1 24 53完全二叉树完全二叉树:编号为编号为 i 的元素存储在数组下标为的元素存储在数组下标为 i-1 的分量中；的分量中；123450 1 2 3 4 1 23 4 5一般二叉树一般二叉树:对照完全二叉树，存储在数组的相应分量中；对照完全二叉树，存储在数组的相应分量中；在最坏情况下，深度为在最坏情况下，深度为 k 的的右单支二叉树右单支二叉树需要需要 2k-1 个存储空间。个存储空间。1

18、23结论结论:顺序存储结构适用于存储完全二叉树。顺序存储结构适用于存储完全二叉树。空间浪费空间浪费12345000 表示不存在此结点表示不存在此结点0 1 2 3 4 5 6 7 12300000 1 2 3 4 5 6 7例10-3 一个深度为K且只有K个结点的二叉树顺序存储最多需要多少个存储空间？最少需要多少个？例10-4 一个完全二叉树结点个数为1000，则n0、n1、n2和高度h各为多少？2.链式存储结构链式存储结构D (root，DL，DR)。链表结点包含链表结点包含 3 个域个域:数据域数据域、左指针域左指针域、右指针域右指针域数据域数据域左指针域左指针域右指针域右指针域datar

19、childlchilddatalchildrchild由这种结点结构得到的二叉树存储结构称为由这种结点结构得到的二叉树存储结构称为二叉链表二叉链表。二叉链表存储表示二叉链表存储表示typedef struct BitNode BitNode,*BitTree;TElemType data；struct BitNode *lchild，*rchild；ABCDEFGH有时还可以在结点结构中增加一个指向父亲的指针。有时还可以在结点结构中增加一个指向父亲的指针。数据域数据域左指针域左指针域右指针域右指针域datarchildlchildfather父指针域父指针域datalchildrchildfa

20、ther采用何种存储结构，依赖于进行何种操作采用何种存储结构，依赖于进行何种操作基本操作基本操作 P:InitBiTree(&T)DestroyBiTree(&T)CreateBiTree(&T)BiTreeEmpty(T)InsertChild(T，A，X)操作操作:二叉树二叉树 T 存在，向存在，向 T 中插入一个信息域为中插入一个信息域为 A 的结点，的结点，作为作为 T 中信息域为中信息域为 X 的结点的左儿子，而其原来的左子树的结点的左儿子，而其原来的左子树为新结点的左子树为新结点的左子树。DeleteChild(T，p，LR)操作操作:根据根据 LR 为为 0 或或 1，删除，删除

21、 T 中中 p 所指结点的左或右子树。所指结点的左或右子树。PreOrderTraverse(T，visit()操作操作:先序遍历二叉树先序遍历二叉树 T。InOrderTraverse(T，visit()操作操作:中序遍历二叉树中序遍历二叉树 T。PostOrderTraverse(T，visit()操作操作:后序遍历二叉树后序遍历二叉树 T。LevelOrderTraverse(T，visit()操作操作:层次遍历二叉树层次遍历二叉树 T。二叉树的基本操作二叉树的基本操作遍历二叉树遍历二叉树遍历二叉树遍历二叉树:如何按某条如何按某条搜索路径搜索路径巡访树中每个结点，巡访树中每个结点，使得每

22、个结点均被使得每个结点均被访问一次访问一次，而且仅被访问一次。，而且仅被访问一次。D (root，DL，DR)。如果能依次遍历这三部分，就可以遍历整个二叉树；如果能依次遍历这三部分，就可以遍历整个二叉树；设以设以 D、L、R 分别表示分别表示访问根结点访问根结点、遍历左子树遍历左子树、遍遍历右子树历右子树，则可以存在，则可以存在 6 种遍历方案种遍历方案:DLR、DRL、LDR、LRD、RDL、RLD；若限定若限定先左后右先左后右的原则，则只有的原则，则只有 3 种情况种情况:先先(根根)序序遍历、遍历、中中(根根)序序遍历、遍历、后后(根根)序序遍历。遍历。DLRLDR、LRD、DLRRDL

23、、RLD、DRL先先(根根)序遍历序遍历:若二叉树为空，则返回；否则若二叉树为空，则返回；否则(1)访问根结点；访问根结点；(2)先先(根根)序遍历左子树；序遍历左子树；(3)先先(根根)序遍历右子树；序遍历右子树；A AABCA B CADBCD L RAD L RD L RBDCD L R先序遍历序列：先序遍历序列：A B D C先序遍历先序遍历:printf(T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);if (T)Status PreOrderTraverse(BiTree T)算法算法 10.1 先序遍历递

24、归算法先序遍历递归算法else return OK;算法的C语言实现：void PreOrderTraverse(BiTree T)if(T!=NULL)printf(%dt,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);ABCDEFGH先序遍历先序遍历000000000beginend先序遍历顺序先序遍历顺序:A B D F G C E HABDFGCEH中中(根根)序遍历序遍历:若二叉树为空，则返回；否则若二叉树为空，则返回；否则(2)访问根结点；访问根结点；(1)中中(根根)序遍历左子树；序遍历左子树；(3)中

25、中(根根)序遍历右子树；序遍历右子树；A AABCB A CADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:printf(T-data);InOrderTraverse(T-lchild);InOrderTraverse(T-rchild);If (T)else return OK;Status InOrderTraverse(BiTree T)算法算法 10.2 中序遍历递归算法中序遍历递归算法ABCDEFGH中序遍历中序遍历000000000beginend中序遍历顺序中序遍历顺序:ABDFGC E HBFDGACEH后后(根根)序遍历序遍历:

26、若二叉树为空，则返回；否则若二叉树为空，则返回；否则(3)访问根结点；访问根结点；(1)后后(根根)序遍历左子树；序遍历左子树；(2)后后(根根)序遍历右子树；序遍历右子树；A AABCB C AADBC L R DL R DL R DADCL R D后序遍历序列：D B C A后序遍历:Bprintf(T-data);PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);If (T)else return OK;Status PostOrderTraverse(BiTree T)算法算法 10.3 后序遍历递归算法后序遍历递归算法AB

27、CDEFGH后序遍历后序遍历000000000beginend后序遍历顺序后序遍历顺序:F G D B H E C AABDFGCEH例，表达式例，表达式 a+b*c d /e-+/*d ebca先序遍历先序遍历:+a *b c /d e前缀式，波兰式前缀式，波兰式中序遍历中序遍历:a +b *c d /e中缀式，算术表达式中缀式，算术表达式后序遍历后序遍历:a b c *+d e /-后缀式，逆波兰式后缀式，逆波兰式中缀表示中缀表示:适于人的思维适于人的思维后缀表示后缀表示:适于计算机的思维适于计算机的思维a +b *c d /ea b c *+d e /-ABCDEFGH000000000

28、beginend中序遍历顺序中序遍历顺序:ABDFGC E HBFDGACEH用栈实现中序遍历的非递归算法用栈实现中序遍历的非递归算法栈用来打印栈用来打印结点信息及结点信息及访问右子树访问右子树 InitStack(S);p=T;pop(S,p);p=p-rchild;/遍历右子树遍历右子树 if (p)Push(S,p);p=p-lchild;/遍历左子树遍历左子树else While(p|!StackEmpty(S)Return OK;Status InOrderTraverse(BiTree T)printf(p-data);/打印根结点打印根结点用C语言实现中序遍历的非递归算法void

29、 InOrderTraverse(BiTree T)int i=0;BiTree p,sM;p=T;while(p!=NULL|i0)if(p)/如果当前结点非空 si+=p;/则当前结点入栈 p=p-lchild;/然后将p的左子树作为新的当前结点(遍历左子树)else p=s-i;/否则弹出当前栈顶元素 printf(“%dt”,p-data);/输出元素的值 p=p-rchild;/然后将p的右子树作为新的当前结点(遍历右子树)ABCDEFGH000000000beginend中序遍历顺序中序遍历顺序:ABDFGC E H例，例，AB DFGC E H对二叉树除可以进行先序、中序、后序的

30、遍历外，还对二叉树除可以进行先序、中序、后序的遍历外，还可以进行可以进行层次遍历层次遍历。H CF ED A层次遍历层次遍历:H,C,D,F,E,A过程过程:打印打印 H；打印打印 H 的左儿子的左儿子 C；打印打印 C 的左、右儿子的左、右儿子 F、E；打印打印 D 的左、右儿子的左、右儿子 A；打印打印 H 的右儿子的右儿子 D；队列实现层次遍历队列实现层次遍历 H CF ED AH入队入队出队出队HC DCF EDAFEAEnQueue(Q,T);While(!QueueEmpty(Q)Return OK;Status LevelOrderTraverse(BiTree T)printf

31、(p-data);/打印结点打印结点DeQueue(Q,p);EnQueue(Q,p-lchild);EnQueue(Q,p-rchild);H CF ED AHCDFEA占用了六个空间占用了六个空间HHCDCFEDAFE A二叉树插入操作二叉树插入操作利用遍历可以实现二叉树的插入、删除操作。利用遍历可以实现二叉树的插入、删除操作。InsertChild(T，A，X)操作操作:二叉树二叉树 T 存在，向存在，向 T 中插入一个数据域为中插入一个数据域为 X 的结点，的结点，作为作为 T 中数据域为中数据域为 A 的结点的左儿子，而其原来的左子树的结点的左儿子，而其原来的左子树为新结点的左子树为

32、新结点的左子树。思想思想:1.首先找到首先找到数据数据域为域为 A 的结点的结点 p。2.建立建立数据数据域为域为 X 的新结点的新结点 q。3.q-lchild=p-lchild。4.p-lchild=q。p H AF ED GXq/找到信息域为找到信息域为 A 的结点的结点 p。q=(BiTNode*)malloc(sizeof(BiTNode)；/新结点新结点 if (!q)exit(OVERFLOW)；q-data=x;q-lchild=p-lchild；p-lchild=q；InsertChild(BiTree&T，TElemType A，TElemType X)InitStack(

33、S);p=T;Pop(S,p);p=p-rchild;/遍历右子树遍历右子树If (p)Push(S,p);p=p-lchild;/遍历左子树遍历左子树Else While(p|!StackEmpty(S)Return ERROR;Status InOrderTraverse(BiTree T,TElemType A,BitNode&p)if (p-data=A)return OK;/找到结点找到结点/用中序遍历的方法，找到信息域为用中序遍历的方法，找到信息域为 A 的结点的结点 p。性质性质:含有含有 n 个结点的二叉链表中有个结点的二叉链表中有 n+1 个空链域。个空链域。证明证明:(1)

34、设，终端结点数为设，终端结点数为 n0，度为度为 1 的结点数为的结点数为 n1，故二叉树的结点总数为故二叉树的结点总数为 n=n0+n1+n2；度为度为 2 的结点数为的结点数为 n2，(2)空链域个数为空链域个数为 2n0+n1，已知，已知，n0=n2+1，故，故，2n0+n1=n0+n1+n2+1=n+1树和森林树和森林树的存储结构树的存储结构 父亲表示法父亲表示法 儿子表示法儿子表示法链式存储链式存储顺序存储顺序存储 父亲儿子表示法父亲儿子表示法 二叉树表示法二叉树表示法RBACDEFHGK一一.父亲表示法父亲表示法用一组地址连续空间存储树的结点，每个结点由两个域组成。用一组地址连续空

35、间存储树的结点，每个结点由两个域组成。RBACDEFHGKdatafather数据域数据域 指示器，指向其父结点指示器，指向其父结点R -1A 0B 0C 0D 1E 1F 30123456789G 6H 6K 6无父无父结点结点父结父结点为点为R父结父结点为点为Atypedef struct PTNode PTNode；/定义树结点定义树结点TElemType data；/数据域数据域int father；/指示器，指向其父结点指示器，指向其父结点#define MAX_TREE_SIZE 100 /定义最大结点定义最大结点数数typedef struct PTree；/定义树定义树PTNo

36、de nodesMAX_TREE_SIZE；/顺序结构存储顺序结构存储int r，n；/根的位置和结点总数根的位置和结点总数树的父亲表示法存储表示树的父亲表示法存储表示R -1A 0B 0C 0D 1E 1F 30123456789G 6H 6K 6结构特点结构特点:优优:获取获取祖先结点祖先结点(根结点根结点)比较方便比较方便RBACDEFHGK缺缺:获取某个结点的获取某个结点的儿子结点儿子结点需要遍历整个结构需要遍历整个结构二二.儿子表示法儿子表示法1.多叉树表示法多叉树表示法链式存储链式存储AchildA1childA2childA3BchildB1childB2childB3Cchil

37、dC1childC2childC3DchildD1childD2childD3链表中的结点存在两种格式链表中的结点存在两种格式:childnchild2child1data.每个结点均采用定长格式，每个结点均采用定长格式，n 为树的度。为树的度。childnchild2child1data.degree每个结点采用变长格式，每个结点采用变长格式，degree=n 为该结点的度。为该结点的度。定长操作方便，变长操作不方便定长操作方便，变长操作不方便结构分析结构分析定长浪费空间，变长节省空间定长浪费空间，变长节省空间采用定长存储格式，链表中存在很多采用定长存储格式，链表中存在很多空链域空链域，造成

38、空间浪费。，造成空间浪费。定义定义:在一棵有在一棵有 n 个结点，度为个结点，度为 k 的树中必有的树中必有(k-1)n+1 个空链域。个空链域。证明证明:(1)设度为设度为 0、1、k 的结点数分别为的结点数分别为 n0、n1、nk.设树中空链域总数为设树中空链域总数为 X则有则有 X=kn0+(k-1)n1+(k-(k-1)nk-1+(k-k)nk.=kn0+kn1+knk-1+knk.-(n1+2n2+(k-1)nk-1+knk ).(2)另外除根结点外，其它结点都有一个分支进入，另外除根结点外，其它结点都有一个分支进入，设设 B 为分支总数，故为分支总数，故 n=B+1，首先首先 n=

39、n0+n1+nk.又由于这些分支均是由度为又由于这些分支均是由度为 1、2、k的结点引出的，的结点引出的，.所以有所以有 B=n1+2n2+(k-1)nk-1+knk.=kn0+kn1+knk-1+knk.-(n1+2n2+(k-1)nk-1+knk ).X=kn-B=kn (n-1)=(k1)n+1得证得证2.顺序存储顺序存储把每个结点的儿子结点以把每个结点的儿子结点以单链表单链表的结构存储的结构存储；则则 n 个结点就构成了个结点就构成了 n 条条儿子单链表儿子单链表；将将 n 条单链表头指针以条单链表头指针以顺序线性表顺序线性表存储存储；RBACDEFHGK0123456789B A C

40、 D E R F G H K 4513267980123456789B A C D E R F G H K 451326798typedef struct CTNode *ChildPtr；/儿子结儿子结点点 int child；struct CTNode *next；typedef struct CTBox；/儿子头指针儿子头指针 TElemType data；ChildPtr firstchild；typedef struct CTree；/树结构树结构#define MAX_TREE_SIZE 100 /定义最大结点数定义最大结点数 CTBox nodesMAX_TREE_SIZE；in

41、t r，n；/根的位置和结点总数根的位置和结点总数RBACDEFHGK0123456789B A C D E R F G H K 451326798优点优点:方便搜索儿子结点方便搜索儿子结点缺点缺点:查找父结点需要从头遍历整个顺序表查找父结点需要从头遍历整个顺序表三三.父亲儿子表示法父亲儿子表示法如何既能方便搜索儿子结点，又能方便查找父结点？如何既能方便搜索儿子结点，又能方便查找父结点？0123456789B A C D E R F G H K 451326798-1000113666四四.二叉树表示法二叉树表示法将树以二叉树的形式表示。将树以二叉树的形式表示。令结点的令结点的两个链域两个链域

42、分别指向该结点的分别指向该结点的第一个儿子第一个儿子和和右边的兄弟右边的兄弟。RBACDEFHGKRADBECFGHKRADBECFGHKtypedef struct CSNode CSNode；/结点结点TElemType data；struct CSNode *firstchild；struct CSNode *nextsibling；查找结点的儿子查找结点的儿子:沿结点的沿结点的 firstchild 域可找到第一个儿子，域可找到第一个儿子，然后再沿然后再沿 nextsibling 域可找到其它儿子。域可找到其它儿子。查找结点的兄弟查找结点的兄弟:沿结点的沿结点的 nextsibling

43、 域可找到所有兄弟。域可找到所有兄弟。查找结点的父亲查找结点的父亲:为每个结点增加一个为每个结点增加一个 father 域指向父结点。域指向父结点。RBACDEFHGKRADBECFGHK性质性质:1.树可以表示成二叉树的形式树可以表示成二叉树的形式启示启示:树与二叉树的转换树与二叉树的转换2.树转换成一棵只有树转换成一棵只有左子树左子树的二叉树的二叉树森林与二叉树的转换森林与二叉树的转换 ACBDEFGHIJ(1).任何一棵树都可以转换为一棵任何一棵树都可以转换为一棵没有没有右子树右子树的二叉树。的二叉树。(2).森林是由若干棵树构成的集合，若把森林中森林是由若干棵树构成的集合，若把森林中第

44、二棵树第二棵树的的根结点看成是根结点看成是第一棵树第一棵树的根结点的根结点兄弟兄弟，就可以导出森林与二叉，就可以导出森林与二叉树的转换。树的转换。1.森林转换成二叉树森林转换成二叉树(1)增加增加一个根结点，作为原一个根结点，作为原森林中各树根结点的森林中各树根结点的父结点父结点。(2)将将新树新树转换成二叉树。转换成二叉树。(3)删除删除二叉树的根结点。二叉树的根结点。ACBDEFGHIJRBECDFGHIJRA2.二叉树转换成森林二叉树转换成森林(1)增加增加一个新根结点，原二叉树根一个新根结点，原二叉树根结点做为新根结点的结点做为新根结点的左儿子左儿子。(2)将将新二叉树新二叉树转换成树

45、。转换成树。(3)删除删除树的根结点变为森林。树的根结点变为森林。BECDFGHIJARACBDEFGHIJR2.二叉树转换成森林二叉树转换成森林(1)增加增加一个新根结点，原二叉树根一个新根结点，原二叉树根结点做为新根结点的结点做为新根结点的左儿子左儿子。(2)将将新二叉树新二叉树转换成树。转换成树。(3)删除删除树的根结点变为森林。树的根结点变为森林。BECDFGHIJARACBDEFGHIJR森林和树的遍历森林和树的遍历 1.分割分割从结构上，可以把任意的森林分成三部分从结构上，可以把任意的森林分成三部分:1)第一棵树的根结点。第一棵树的根结点。2)第一棵树根结点的子树构成的森林。第一棵

46、树根结点的子树构成的森林。3)其余的树构成的森林。其余的树构成的森林。按这三部分的不同排列次序可把森林的遍历次序分为前序、中序、按这三部分的不同排列次序可把森林的遍历次序分为前序、中序、后序。后序。2)访问第一棵树的根结点。访问第一棵树的根结点。3)按前序遍历根结点的子树构成的森林。按前序遍历根结点的子树构成的森林。4)按前序遍历其余的树构成的森林。按前序遍历其余的树构成的森林。森林的前序遍历森林的前序遍历1)如果森林中树的个数为如果森林中树的个数为 0，则返回。，则返回。ACBDEFGHIJBECDFGHIJAABCDEFGHIJ3)访问第一棵树的根结点。访问第一棵树的根结点。2)按中序遍历

47、第一棵树根结点的子树构按中序遍历第一棵树根结点的子树构成的森林。成的森林。4)按中序遍历其余的树构成的森林。按中序遍历其余的树构成的森林。森林的中序遍历森林的中序遍历1)如果森林中树的个数为如果森林中树的个数为 0，则返回。，则返回。ACBDEFGHIJBECDFGHIJABCDAFEHJIG4)访问第一棵树的根结点。访问第一棵树的根结点。2)按后序遍历第一棵树根结点的子树构按后序遍历第一棵树根结点的子树构成的森林。成的森林。3)按后序遍历其余的树构成的森林。按后序遍历其余的树构成的森林。森林的后序遍历森林的后序遍历1)如果森林中树的个数为如果森林中树的个数为 0，则返回。，则返回。ACBDE

48、FGHIJBECDFGHIJABCDFHJIGEA森林的前、中、后序遍历与对应二叉树的前、中、后序遍历一致。森林的前、中、后序遍历与对应二叉树的前、中、后序遍历一致。树的应用树的应用1.二叉分类树二叉分类树(二叉排序树二叉排序树)2.判定树判定树3.赫夫曼树赫夫曼树(最优二叉树最优二叉树)赫夫曼树赫夫曼树 Huffman(最优二叉树最优二叉树)基本概念基本概念:从树中一个结点到另一个结点之间的分支构成这两个结点之间的从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径路径。路径上的分支数目称做路径上的分支数目称做路径长度路径长度。XYZX 到到 Y 的路径的路径路径长度为路径长度为 2

49、树的路径长度树的路径长度是从树根到是从树根到每一个每一个结点的路径长度之结点的路径长度之和和。在具有相同结点数的所有二叉树中，在具有相同结点数的所有二叉树中，的路径长度是最短的。的路径长度是最短的。完全二叉树完全二叉树推广：为结点加权推广：为结点加权 w。735ABCDE结点的带权路径长度结点的带权路径长度为从根结点到该结点之间的路径长度与结点上为从根结点到该结点之间的路径长度与结点上权值的乘积。权值的乘积。树的带权路径长度树的带权路径长度为树中所有为树中所有叶子结点叶子结点的带权路径长度之和，通常的带权路径长度之和，通常记做记做 WPL=wk L(vk)nk=1wk 为叶子结点为叶子结点 v

50、k 的权值的权值L(vk)为叶子结点为叶子结点 vk 的路径长度的路径长度例，例，3 棵二叉树，都有棵二叉树，都有 4 个叶子结点个叶子结点 a、b、c、d，分别带权，分别带权7、5、2、4，求它们各自的带权路径长度。，求它们各自的带权路径长度。abcd7524(1)abdc7542(2)cdba2457(3)(1)WPL=72 +52 +22 +42 =36(2)WPL=73 +53 +21 +42 =46(3)WPL=71 +52 +23 +43 =35假设有假设有n个权值个权值 w1,w2,wn，试构造一棵有，试构造一棵有n个叶子结点个叶子结点的二叉树，每个叶子结点带权为的二叉树，每个叶