第六章树和二叉树精选文档.ppt

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

1、第六章 树和二叉树1本讲稿第一页，共七十五页 第六章第六章 树和二叉树树和二叉树6.1 树的有关概念6.2 二叉树6.3二叉树的遍历6.4 遍历的应用6.5 线索二叉树6.6 树和森林6.7 哈夫曼树及应用2本讲稿第二页，共七十五页 6.1 6.1 树的有关概念树的有关概念1.树的概念2.树的应用3.树的表示4.树的有关术语5树的基本操作3本讲稿第三页，共七十五页1树的概念树的概念 树是树是n个结点的有限集合，在任一棵非空树中：个结点的有限集合，在任一棵非空树中：（1）有且仅有一个称为根的结点。）有且仅有一个称为根的结点。（2）其余结点可分为个互不相交的集合，而且这些集合中的每一集合）其余结点

2、可分为个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。都本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念J JI IA AC CB BD DH HG GF FE E4本讲稿第四页，共七十五页从逻辑结构看：从逻辑结构看：1）树中只有根结点没有前趋；）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径；）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构）树是一

3、种分枝结构 （除了一个称为根的结点外）每个元素都有且仅有（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。一个直接前趋，有且仅有零个或多个直接后继。J JI IA AC CB BD DH HG GF FE E1树的概念树的概念 5本讲稿第五页，共七十五页4树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；树的高度：树中最大的结点层结点的度：

4、结点子树的个数树的度：树中最大的结点度。叶子结点：也叫终端结点，是度为0的结点；分枝结点：度不为0的结点；森林；互不相交的树集合；有序树：子树有序的树，如：家族树；无序树：不考虑子树的顺序；6本讲稿第六页，共七十五页5树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：（以DOS元文件系统为例解释树的基本操作）1）InitTree(&T);2）DestroyTree(&T);3）CreateTree(&T,definition);4）ClearTree(&T);5）TreeEmpty(T);6）TreeDepth(T);7）Root(T);8）Value(T,&cur

5、_e);9）Assign(T,cur_e,value);10）Paret(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本讲稿第七页，共七十五页 6.2 6.2 二叉树二叉树一 二叉树的概念二 二叉树的性质三 二叉树的存储结构8本讲稿第八页，共七十五页一一 二叉树的概念二叉树的概念1 1 二叉树的定义二叉树的定义二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、

6、右子树本身也是二叉树。说明说明1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2）左、右子树不能颠例有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;A A F F G G E E D D C C B B9本讲稿第九页，共七十五页 A A F F G G E E D D C C B B(a)、(b)是不同的二叉树，(a)的左子树有四个结点，(b)的左子树有两个结点，(a)A A G G E E D D B B C C F F(b)10本讲稿第十页，共七十五页2 二叉树的基本形态二叉树的基本形态11本讲稿第十一页，共七十五页3应用举例例1 可以用二叉树表示表达式

7、 e e d d c c b b f f a a +*/-a b c d-*+e f/-a b c d-*+e f/-表达式的后缀表示表达式的后缀表示 a+b*c a+b*c d d e/f -e/f -表达式的中缀表示表达式的中缀表示 -+a*b-+a*b c d/e f -c d/e f -表达式的前缀表示表达式的前缀表示 12本讲稿第十二页，共七十五页3应用举例例1 可以用二叉树表示表达式 e e d d c c b b f f a a +*/-a b c d-*+e f/-a b c d-*+e f/-表达式的后缀表示表达式的后缀表示 a+b*c a+b*c d d e/f -e/f

8、-表达式的中缀表示表达式的中缀表示 -+a*b-+a*b c d/e f -c d/e f -表达式的前缀表示表达式的前缀表示 13本讲稿第十三页，共七十五页下面是两个关于二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点（i=1)利用归纳法证明性质2：深度为k的二叉树至多有2k-1个结点（k=1)第比数列求和性质3：对任何一棵二叉树T,如果其终端结点数为n0，度为2的结点 数为n2，则n0=n2+114本讲稿第十四页，共七十五页两种特殊的二叉树满二叉树：如果深度为k的二叉树，有2k-1个结点则称为满二叉树；A A G G F F E E D D C C B B A A C C B B

9、K=3的满二叉树K=2的满二叉树15本讲稿第十五页，共七十五页完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树；A A E E D D C C B B G G A A E E D D C C B B(a)a)(c)c)(b)b)(a)(a)、(b)b)完全二叉树(c)c)不是完全二叉树 A A G G F F E E D D C C B B16本讲稿第十六页，共七十五页下面是两个关于完全二叉树的性质性质4 具有n个结点的完全二叉树的深度为：log2 n+1对完全二叉树的结点编号：从上到下，每一层从左到右 A A F F E E D

10、 D C C B B1 12 23 34 45 56 6性质5：在完全二叉树中编号为i的结点，1）若有左孩子，则左孩编号为2i；2）若有右孩子，则有孩子结点编号为2i+1；3）若有双亲，则双亲结点编号为i/2；17本讲稿第十七页，共七十五页三二叉树存贮结构三二叉树存贮结构 1 二叉树的顺序结构完全二叉树的顺序结构用一组连续的内存单元，按编号顺序依次存储完全二叉树的元素顺序结构图示1 2 3 4 5 6 7 1 2 3 4 5 6 7 m-1m-1 A B C D E FA B C D E F A A F F E E D D C C B B1 12 23 34 45 56 618本讲稿第十八页，

11、共七十五页二叉树的顺序结构 假想，我们补齐二叉树所缺少的那些结点，对二叉树结点编号 A A F F G G E E D D C C B B7 71 16 62 24 45 53 3 A A F F G G E E D D C C B B9 98 8101019本讲稿第十九页，共七十五页1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 m-m-1 1 A B A B C C D E D E F F G G二叉树的顺序结构图示将二叉树原有的结点按编号存储到内存单元“相应”的位置上1 16 62 24 45 53 3 A A F F G G E E D D C C B B9 9

12、8 8101020本讲稿第二十页，共七十五页2 二叉链表 二叉链表中每个结点包含三个域：数据域、左指针域、右指针域 D D A A B B C C E E F F A A F F E E D D C C B B3 三叉链表 三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域二叉链表图示21本讲稿第二十一页，共七十五页4 静态链表 上面二叉链表或三叉链表是用指针实现，是一种动态的链式存储结构，链式存储结构也可用一维数组来实现，用一维数组表示的二叉链表或三叉链表，称为静态链表 A A F F E E D D C C B B孩子结点在数组中的位置-1表示无左或右孩子静态二叉链表2

13、A 13 C -15 B -1-1 E-1-1 F-1-1 D 4 0123456Lchild data rchild22本讲稿第二十二页，共七十五页 6.3 6.3 二叉树的遍历二叉树的遍历 一.二叉树的遍历方法 二.遍历的递归算法23本讲稿第二十三页，共七十五页遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。如何访问二叉树的每个结点，而且每个结点仅被访问一次？24本讲稿第二十四页，共七十五页一一二叉树的遍历方法二叉树的遍历方法 二叉树

14、由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：令：L L：遍历左子树 D D：访问根结点 R R：遍历右子树 有六种遍历方法：D DL LR R，L LD DR R，L LR RD D，D DR RL L，R RD DL L，R RL LD D 约定先左后右,有三种遍历方法：D DL LR R、L LD DR R、L LR RD D，分别称为 先序遍历、中序遍历、后序遍历 A A F F G G E E D D C C B B25本讲稿第二十五页，共七十五页 先序遍历（DLR）若二叉树非空（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；

15、先序遍历序列：A,A,B,D,E,G,B,D,E,G,C,FC,F A A F F G G E E D D C C B B例：先序遍历右图所示的二叉树 （1）访问根结点A （2）先序遍历左子树：即按D DL LR R的顺序遍历左子树 （3）先序遍历右子树：即按D DL LR R的顺序遍历右子树26本讲稿第二十六页，共七十五页中序遍历（L LD DR R）若二叉树非空（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树 中序遍历序列：D,B,G,E,D,B,G,E,A,A,C,FC,F A A F F G G E E D D C C B B例：中序遍历右图所示的二叉树 （1）中序遍历左子树：

16、即按L LD DR R的顺序遍历左子树 （2）访问根结点A A （3）中序遍历右子树：即按L LD DR R的顺序遍历右子树27本讲稿第二十七页，共七十五页后序遍历（L LR RD D）若二叉树非空（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点 后序遍历序列：D,G,E,B,D,G,E,B,F,C,F,C,A A例：后序遍历右图所示的二叉树 （1）后序遍历左子树：即按L LR RD D的顺序遍历左子树 （2）后序遍历右子树：即按L LR RD D的顺序遍历右子树 （3）访问根结点A A A A F F G G E E D D C C B B28本讲稿第二十八页，共七十五页 e e d

17、 d c c b b f f a a +*/-后序遍历序列：a b c d-*+a b c d-*+e f/e f/-中序遍历序列：a+b*c a+b*c d d e/fe/f 先序遍历序列：-+a*b+a*b c d c d/e f/e f例：先序遍历、中序遍历、后序遍历下图所示的二叉树29本讲稿第二十九页，共七十五页按层遍历:从根出发,依次访问第一层、第二层结点 A A F F G G E E D D C C B B按层遍历序列:A B C D E F G30本讲稿第三十页，共七十五页 若二叉树非空 （1）访问根结点；（2）先序遍历左子树 （3）先序遍历右子树；二二.遍历的递归算法遍历的递

18、归算法先序遍历（DLR）的定义：上面先序遍历的定义等价于：若二叉树为空，结束 基本项（也叫终止项）若二叉树非空 递归项 （1）访问根结点；（2）先序遍历左子树 （3）先序遍历右子树；31本讲稿第三十一页，共七十五页1先序遍历递归算法先序遍历递归算法void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)/采用二叉链表存贮二叉树，visit()是访问结点的函数。/本算法先序遍历以T为根结点指针的二叉树if(T)/若二叉树不为空，Visit(T-data)；/访问根结点 PreOrderTraverse(T-lchild,Visit);/

19、先序遍历T的左子树，PreOrderTraverse(T-rchild,Visit);/先序遍历T的右子树/PreOrderTraverse最简单的Visit函数是：StatusPrintElement(TElemTypee)/输出元素e的值printf(e);returnOK;D D A A B B C C E E F F T T32本讲稿第三十二页，共七十五页2 中序遍历递归算法中序遍历递归算法void InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)/采用二叉链表存贮二叉树，visit()是访问结点的函数。/本算法中序中序遍历以T,

20、为根结点指针的二叉树 if(T)/若二叉树不为空，访问根结点，遍历右子树InOrderTraverse(T-lchild,Visit);/中序中序遍历T的左子树Visit(T-data)；/访问根结点InOrderTraverse(T-rchild,Visit);/中序中序遍历T的右子树/InOrderTraverse 33本讲稿第三十三页，共七十五页3 后序遍历递归算法后序遍历递归算法voidPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存贮二叉树，visit()是访问结点的函数。/本算法后序遍历以T为根结点指针的二叉树

21、，对每个数据元素调用函数Visit()if(T)/若二叉树不为空，PostOrderTraverse(T-lchild,Visit);/后序遍历T的左子树PostOrderTraverse(T-rchild,Visit);/后序遍历T的右子树，Visit(T-data)；/访问根结点/PostOrderTraverse34本讲稿第三十四页，共七十五页遍历的非递归算法遍历的非递归算法中序遍历的非递归算法中序遍历的非递归算法(使用栈实现非递归中序遍历使用栈实现非递归中序遍历)StatusInOrderTraverse(BiTreeT,Status(*Visit)(TelemTypee)/采用二叉链

22、表存储结构，Visit是对数据元素操作的应用函数。/中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。InitStack(S);p=T;While(p|!StackEmpty(s)if(p)Push(s,p);p=p-lchild;/根指针进栈，遍历右子树else/根指针退栈，访问根结点，遍历右子树Pop(S,p);Visit(p-data);p=p-rchild;/else/WhilereturnOK;/InOrderTraverse35本讲稿第三十五页，共七十五页按层遍历算法 与图的广度优先遍历类似,利用队列实现树的按层遍历StatusLevelTraverse(BiTree

23、T,Status(*Visit)(TelemTypee)/采用二叉链表存储结构，Visit是对数据元素操作的应用函数。使用辅助队列Q,按层遍历二叉树T。InitQueue(Q);InitQueue(Q);/建空的辅助队列Q p=T;p=T;Visit(p-data)Visit(p-data)，EnQueue(Q,p)/EnQueue(Q,p)/访问访问p p所指结点所指结点,p,p入队入队 While(!QueueEmpty(Q)While(!QueueEmpty(Q)DeQueue(Q,p);DeQueue(Q,p);/队头元素出队,并赋值给p p=p p=p-lchild,Visit(p-

24、data);EnQueue(Q,p);,Visit(p-data);EnQueue(Q,p);p=p p=p-rchild,Visit(p-data);EnQueue(Q,p);,Visit(p-data);EnQueue(Q,p);/while /while/LevelTraverse36本讲稿第三十六页，共七十五页 6.4 6.4 遍历的应用遍历的应用 1.求二叉树的叶子结点个数 2.建立二叉链表 37本讲稿第三十七页，共七十五页例1编写求二叉树的叶子结点个数的算法输入：二叉树的二叉链表结果：二叉树的叶子结点个数 D D A A B B C C E E F F T Tvoidleaf(Bi

25、TreeT)/采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点的个数。本算法在先序遍历二叉树的过程中，统计叶子结点的个数/第一次被调用时，n=0if(T)if(T-lchild=null&T-rchild=null)n=n+1;/若T所指结点为叶子，则累加。leaf(T-lchild);leaf(T-rchild);/if/leaf与与先序遍历算法先序遍历算法比较一下比较一下！38本讲稿第三十八页，共七十五页voidleaf(BiTreeT)/采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点,的个数。/本算法在先序遍历二叉树的过程中，统计叶子结点的个数第一次被调用时

26、，n=0if(T)/若二叉树为空，结束返回/若二叉树不为空，在先序遍历二叉树的过程中，统计叶子结点的个数if(T-lchild=null&T-rchild=null)n=n+1;leaf(T-lchild);leaf(T-rchild);/if/leaf viod PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)/采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法先序/遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit()if(T)/若二叉树为空，返回/若二叉树不为空，访问根结点；遍历左子树，遍历右子树 Visit

27、(T-data)；PreOrderTraverse(T-lchild,Visit);PreOrderTraverse(T-rchild,Visit);/PreOrderTraverse比较先序遍历算法和计算叶子结点算法，有什么相同和不同？结构类似函数名不同访问结点时调用visit()访问结点时统计叶子结点的个数39本讲稿第三十九页，共七十五页例2建立二叉链表输入：二叉树的先序序列结果：二叉树的二叉链表遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用遍历，建立二叉链表的所有结点并完成相应结点的链接？基本思想：输入（在空子树处添加字符*的二叉树的）先序序列（设每个元素是一个字符

28、）按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的链接 A A F F E E D D C C B B*A B D*F*C E*40本讲稿第四十页，共七十五页StatusCreateBiTree(BiTree&T)/输入（在空子树处添加字符*的二叉树的）先序序列（设每个元素是/一个字符）按先序遍历的顺序，建立二叉链表，并将该二叉链表根结/点指针赋给Tscanf(&ch);if(ch=*)T=NULL;/若ch=*则T=NULL返回else/若ch!=*if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-date=ch;/建立（

29、根）结点CreateBiTree(T-lchild);/构造左子树链表，并将左子树根结点指针/赋给（根）结点的左孩子域CreateBiTree(T-rchild);/构造右子树链表，并将右子树根结点指针/赋给（根）结点的右孩子域returnOK;/CreateBiTree41本讲稿第四十一页，共七十五页 D D A A B B C C E E F F T T 先序序列：A B D F C E（在空子树处添加*的二叉树的）先序序列：A B D*F*C E*A A F F E E D D C C B B*A A F F E E D D C C B B42本讲稿第四十二页，共七十五页掌握利用先序和中

30、序，中序和后序来建立一个二叉树 已知一个二叉树的先序和中序，怎样建立二叉树？先序：-+a*bcd/ef 中序：a+b*cde/f 已知一个二叉树的后序和中序，怎样建立二叉树？中序：a+b*cde/f 后序：abcd-*+ef/-43本讲稿第四十三页，共七十五页小结 小小 结结1 二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树；2 二叉树即可以用顺序结构存储，也可用链式结构存储；3 遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树，本课程介绍了三种遍历算法：先序遍历、中序遍历、后序遍历；

31、44本讲稿第四十四页，共七十五页HW:6.1 6.3(不用交）不用交）6.14 6.27 6.285月月16号交作业号交作业45本讲稿第四十五页，共七十五页 6.4 6.4 线索二叉树线索二叉树 1.线索二叉树和线索链表 2.二叉树的线索化 3.线索二叉树的遍历46本讲稿第四十六页，共七十五页1 线索二叉树线索二叉树和线索链表和线索链表加上结点前趋后继信息（线索）的二叉树称为线索二叉树 A A G G H H E E D D C C B B F F以中序遍历为例，通过遍历可以得到二叉树结点的中序序列。中序遍历序列：D,B,H,E,A,F,C,G在中序序列中，D的后继是B，H的前趋是B，后继是E

32、47本讲稿第四十七页，共七十五页线索链表线索链表线索二叉树的存贮方法：T T D D A A B B C C F F H H E E G G A A G G H H E E D D C C B B F F2)每个n个结点的二叉链表，有n+1个空指针域。可利用这些的空指针域存放结点的前趋和后继指针。这种二叉链表称为线索链表1）为每个结点增加二个指针域48本讲稿第四十八页，共七十五页线索二叉树 A A G G H H E E D D C C B B F F孩子指针前趋指针后继指针线索链表线索链表头结点F F1 11 1E E0 01 1G G1 11 1D D1 11 1A A0 00 0B B0

33、 00 0H H1 11 1C C0 00 00 01 149本讲稿第四十九页，共七十五页2.2.二叉树的线索化二叉树的线索化StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT)A A0 00 0B B0 00 0C C0 00 0D D0 00 0H H0 00 0E E0 00 0G G0 00 0F F0 00 0在二叉树加线索F F1 11 1E E0 01 1G G1 11 1D D1 11 1A A0 00 0B B0 00 0H H1 11 1C C0 00 00 01 1头结点50本讲稿第五十页，共七十五页二叉树的二叉线索存储表示

34、typedef enumLink,ThreadPointerTag;/Link=0 指针 Thread=1 线索 typedef struct BiThrNode TElemType data;Struct BiThrNode *lchild,*right;PointerTag LTag,RTag;BiThrNode,*BiThrTree;51本讲稿第五十一页，共七十五页StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT)/中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。if(Thrt=(BiThrTree)malloc(sizeof)(B

35、iThrNode)exit(OVERFLOW);Thrt-Ltag=Link;Thrt-Rtag=Thread;/建头结点Thrt-rchild=Thrt;/右指针回指if(!T)Thrt-lchild=Thrt;/若二叉树空，则左指针回指elseThrt-lchild=T;/若二叉树非空，则左指针指向根结点pre=Thrt;/头结点看作是中序序列第一个结点的前趋InThreading(T);/中序遍历进行中序线索化Pre-rchild=Thrt;pre-Rtag=Thread;/最后一个结点线索化Thrt-rchild=pre;returnOK;/InOrderThreading52本讲稿第

36、五十二页，共七十五页voidInThreading(BiThrTreep)if(p)InThreading(p-lchild);/左子树线索化if(!p-lchild)p-Ltag=Thread;p-lchild=pre;/为当前结点加上前趋线索if(!p-rchild)pre-Rtag=Thread;pre-rchild=p;/为当前结点的前趋加上后继线索pre=p;/保持pre指向p的前趋InThreading(p-rchild);/右子树线索化/if/InThreading53本讲稿第五十三页，共七十五页基本思想：基本思想：1）若p所指结点的右孩子域为线索，则p的右孩子结点即为后继结点；

37、2）若p所指结点的右孩子域为孩子指针，则p的后继结点为其右子树的最左下结点；中序遍历序列：D,B,H,E,A,F,C,G3线索二叉树的遍历线索二叉树的遍历F F1 11 1E E0 01 1G G1 11 1D D1 11 1A A0 00 0B B0 00 0H H1 11 1C C0 00 00 01 1头结点54本讲稿第五十四页，共七十五页线索链表的遍历算法VoidInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TE1emTypee)/T指向头结点，头结点的左链lchild 指向根结点，/中序遍历二叉线索树T算法，对每个数据元素调用函数Visi

38、t。P=T-lchild;/p指向根结点While(p!=T)/空树或遍历结束时，p=TWhile(p-Ltag=Link)p=p-lchild;/找到最左下结点；访问之Visit(p-data)while(p-Rtag=Thread&p-rchild!=T)/若p所指结点的右孩子域为线索且不是最后一个结点p=p-rchild;Visit(p-data);/访问后继结点p=p-rchild;/若p所指结点的右孩子域不是线索returnOK;/InOrderTraverse_Thr为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数visit()访问结点总

39、是成功的。55本讲稿第五十五页，共七十五页 6.6 6.6 树和森林树和森林 一.树的存储结构 二.树和二叉树的转换 三.树的遍历四.森林 56本讲稿第五十六页，共七十五页 一树的存贮结构一树的存贮结构1 双亲表示法双亲表示法：通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。双亲表示类型定义#defineMAX_TREEE_SIZE100typedefstructPTNodeTelemTypedata;intparent;/双亲位置域PTNode;typedefstructPTNodenodesMAX_TREE_SIZE;intn;/结点数Ptree;I IA AC CB BD

40、DH HG GF FE E A -1 A -1 B 0 B 0 C 0 C 0 D 0 D 0 E 1 E 1 F 1 F 1 G 2 G 2 H 3 H 3 I 3 I 30 01 12 23 34 45 56 67 78 8.data parent 9 9T.nodesT.n结点数双亲结点在数组中的位置-1表示无双亲57本讲稿第五十七页，共七十五页2、孩子表示法孩子表示法：通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。方法1：多重链表（类似二叉链表）两种方式：定长结点 不定长结点定长结点优点结点结构一致，便于实现树的操作。缺点是浪费一些内存。不定长结点优点：节省内存缺点：不

41、定长会使一些操作实现复杂一些58本讲稿第五十八页，共七十五页 A B C D E F G H I 0 1 2 3 4 5 6 7 8 99结点数和根的位置9013245867T.nodesT.nT.rdatafirstchild树的孩子链表图示结点的孩子结点链表I IA AC CB BD DH HG GF FE E方式II孩子链表：对树的每个结点用线性链表存贮它的孩子结点59本讲稿第五十九页，共七十五页树的孩子链表类型定义typedefstructCTNode/孩子结点intchild;structCTNode*next;*ChildPtr;typedefstructTElemTypedata

42、;ChildPtrfirstchild;/孩子链表头指针CTBox;typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;/结点数和根的位置；CTree;A B C D E F G H I 0 1 2 3 4 5 6 7 8 999013245867T.nodesT.nT.rdatafirstchild60本讲稿第六十页，共七十五页 3 孩子兄弟表示法 孩子兄弟表示法用二叉链表作为树的存贮结构孩子兄弟表示法类型定义typedefstructCSNodeTElemTypedata;structCSNode*firstchild,*nextsibling;CSNo

43、de,*CSTree;I IA AC CB BD DH HG GF FE EA AI IH HD DG GF FC CE EB B树的孩子兄弟表示法图示B的第一个孩子结点B的右兄弟结点61本讲稿第六十一页，共七十五页I IA AC CB BD DH HG GF FE E此二叉链表既是树(a)(a)的孩子兄弟表示又是二叉树(b)(b)的二叉链表(a)(a)(b)(b)由此可将树与二叉树对应起来A AI IH HD DG GF FC CE EB BF FI IA AB BD DH HG GC CE E62本讲稿第六十二页，共七十五页二 树与二叉树的转换 二叉树与树都可用二叉链表存贮，以二叉链表作中

44、介，可导出树与二叉树之间的转换。树与二叉树转换方法树根结点X的第一个孩子结点X紧邻的右兄弟二叉树根结点X的左孩子结点X的右孩子63本讲稿第六十三页，共七十五页树根结点X的第一个孩子结点X紧邻的右兄弟二叉树根结点X的左孩子结点X的右孩子I IA AC CB BD DH HG GF FE EF FI IA AB BD DH HG GC CE E64本讲稿第六十四页，共七十五页三三 树的遍历树的遍历先根遍历先访问根，然后依次先根遍历每一颗子树。例 先根遍历序列 A B E F C G D H I 后根遍历依次后根遍历根的每一颗子树，然后访问根。后根遍历序列 E F B G C H I D A 树的先

45、根遍历对应二叉树的先序遍历；树的后根遍历对应二叉树的中序遍历。不论是先根遍历还是后根遍历都是对树按深度方向的遍历，也可按宽度方向（按层）遍历树。I IA AC CB BD DH HG GF FE E65本讲稿第六十五页，共七十五页四四 森林森林森林：树的集合森林：树的集合 将森林中树的根看成兄弟，可用树孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；可用树的遍历方法对森林进行遍历；J J O O P P N N M M L L K KI IA AC CB BD DH HG GF FE E包含两棵树的森林66本讲稿第六十六页，共七十五页小结 小小 结结1以中序遍历为例，将中

46、序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。加上结点前趋后继信息（线索）的二叉树称为线索二叉树；2二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换；67本讲稿第六十七页，共七十五页 6.7 6.7 哈夫曼树及应用哈夫曼树及应用 6.7.1 哈夫曼树及构造 6.7.1 哈夫曼编码 68本讲稿第六十八页，共七十五页6.7.1 6.7.1 哈夫曼树及构造哈夫曼树及构造1 哈夫曼树哈夫曼树的概念的概念路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；路径长度：路径上的分支数目称为路径长度；结点的

47、权：根据应用的需要可以给树的结点赋权值；结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作WPL=wiLi哈夫曼树：假设有n个权值(w1,w2,wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。哈夫曼树。69本讲稿第六十九页，共七十五页3 哈夫曼树的构造哈夫曼树的构造构造哈夫曼树的步骤：1根据给定的n个权值，构造n棵只有一个根结点的二叉树，n个权值分别是这些二叉树根结点的权。设F是由这n棵二叉树构成的集合2在F中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的

48、二叉树，置新二叉树根的权值=左、右子树根结点权值之和；3从F中删除这两颗树，并将新树加入F；4重复2、3，直到F中只含一颗树为止；70本讲稿第七十页，共七十五页40403030606015155 510101515303040403030606015155 5101015153030100100例：构造以W=（5，15，40，30，10）为权的哈夫曼树。30305 51010151540404040303015155 51010151540403030303015155 510101515哈夫曼树中权值小的结点离根远权值大的结点离根近71本讲稿第七十一页，共七十五页w p lch rch012

49、3456789101112131415 5 9 0 029 14 0 0 7 10 0 0 8 10 0 014 12 0 023 13 0 0 3 9 0 011 11 0 0 8 11 1 715 12 3 419 13 8 929 14 5 10 42 15 6 1158 15 2 12100 0 13 14哈夫曼树对应的静态三叉链表w,p,lch,rch 是weight,parent,lchild,rchild的缩写292919195858424210010015158 87 73 35 58 81111232314142929以5,29,7,8,14,23,3,11为权值的哈夫曼树2

50、构造哈夫曼树的算法输入：n个权值结果：哈夫曼树72本讲稿第七十二页，共七十五页例某通讯系统只使用8种字符a、b、c、d、e、f、g、h，其使用频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11。构造以字符使用频率作为权值的哈夫曼树。a:0110a:0110b:10b:10c:1110c:1110d:1111d:1111e:110e:110f:00f:00g:0111g:0111h:010h:010292919195858424210010015158 87 73 35 58 8111123231414292973本讲稿第七十三页，共七十五页HW:6.377