数据结构--第六章树和二叉树课件.ppt

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

1、6.1 树的定义与基本概念树的定义与基本概念6.2 二叉树的类型定义二叉树的类型定义6.3 二叉树的存储结构二叉树的存储结构6.4 二叉树的遍历二叉树的遍历6.5 树、森林和二叉树的关系及转换树、森林和二叉树的关系及转换6.6 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码26.1 树的定义与基本概念树的定义与基本概念一、树的基本概念一、树的基本概念二、树的抽象数据类型定义：二、树的抽象数据类型定义：三、树的基本术语三、树的基本术语3一、一、树的基本概念树的基本概念树：树：是是n(n0)个结点的有限集合个结点的有限集合T。当。当n=0时称时称 为空树；当为空树；当n0时，该集合满足如下条件时，该集合

2、满足如下条件：(1)其中必有一个称为其中必有一个称为根根(root)的特定结点，它没的特定结点，它没 有直接前驱，但有零个或多个直接后继。有直接前驱，但有零个或多个直接后继。(2)其余其余n-1个结点可以划分成个结点可以划分成m(m0)个互不相个互不相 交的有限集交的有限集T1，T2，T3，Tm，其中，其中Ti又又 是一棵树，称为是一棵树，称为根根root的的子树子树。每棵子树的。每棵子树的 根结点有且仅有一个直接前驱，但有零个或根结点有且仅有一个直接前驱，但有零个或 多个直接后继。多个直接后继。4数据对象数据对象D D：一个集合，该集合中的所有元素：一个集合，该集合中的所有元素具有相同的特性

3、。具有相同的特性。数据关系数据关系R R：若若D D为空集，则为空树。若为空集，则为空树。若D D中仅中仅含有一个数据元素，则含有一个数据元素，则R R为空集，否则为空集，否则R=HR=H，H H是如下的二元关系：是如下的二元关系：(1)(1)在在D D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素rootroot，它在关系，它在关系H H下下没有前驱没有前驱。(2)(2)除除rootroot以外，以外，D D中每个结点在关系中每个结点在关系H H下都有下都有且且仅有一个前驱仅有一个前驱。二、树的抽象数据类型定义二、树的抽象数据类型定义6基本操作：(1)InitTree（Tree）：

4、）：将将Tree初始化为一棵空树。初始化为一棵空树。(2)DestoryTree（Tree）：）：销毁树销毁树Tree。(3)CreateTree（Tree）：）：创建树创建树Tree。(4)TreeEmpty（Tree）：）：若若Tree为空，则返回为空，则返回TRUE，否则返回，否则返回FALSE。(5)Root（Tree）：）：返回树返回树Tree的根。的根。(6)Parent（Tree，x）：）：树树Tree存在，存在，x是是Tree中的中的某个结点。若某个结点。若x为非根结点，则返回它的双亲，为非根结点，则返回它的双亲，否则返回否则返回“空空”。7(7)FirstChild（Tree

5、，x）：）：树树Tree存在，存在，x是是Tree中的某个结点。若中的某个结点。若x为非叶子结点，则返为非叶子结点，则返回它的第一个孩子结点，否则返回回它的第一个孩子结点，否则返回“空空”。(8)NextSibling（Tree，x）：）：树树Tree存在，存在，x是是Tree中的某个结点。若中的某个结点。若x不是其双亲的最后不是其双亲的最后一个孩子结点，则返回一个孩子结点，则返回x后面的下一个兄弟结后面的下一个兄弟结点，否则返回点，否则返回“空空”。(9)InsertChild（Tree，p，Child）：）：树树Tree存在，存在，p指向指向Tree中某个结点，非空树中某个结点，非空树Ch

6、ild与与Tree不相交。将不相交。将Child插入插入Tree中，做中，做p所指向所指向结点的子树。结点的子树。8结点结点:结点的度结点的度:树的度树的度:叶子结点叶子结点:分支结点分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点三、树的基本术语三、树的基本术语10DHIJM孩子孩子结点、双亲双亲结点、兄弟兄弟结点、堂兄弟堂兄弟结点、祖先祖先结点、子孙子孙结点结点的层次结点的层次:树的深度：树的深度：ABCDEFGHIJMKL从根结点开始定义,根结点的层次为1，根的直接后继的层次为2，依此类推。树中叶子结点所在的最大层次11线性结构线性结构树

7、型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)对比对比树型结构树型结构和和线性结构线性结构的结构的结构特点特点13 二叉树或为空树空树；或是由一个根结根结点点加上两棵两棵分别称为左子树左子树和右子树右子树的、互不交的互不交的二叉树二叉树组成。ABCDEFGHK根结点左子树右子树EF二叉树中不存在度大于2的结点，并且二叉树的子树有左子树

8、和右子树之分！15二、二叉树的基本操作二、二叉树的基本操作：(1)Initiate（bt）：将）：将bt初始化为空二叉树。初始化为空二叉树。(2)Create（bt）：）：创建一棵非空二叉树创建一棵非空二叉树bt。(3)Destory（bt）：）：销毁二叉树销毁二叉树bt。(4)Empty（bt）：）：若若bt为空，则返回为空，则返回TRUE，否则返回否则返回FALSE。(5)Root(bt)：求二叉树求二叉树bt的根结点。若的根结点。若bt为空为空二叉树，则函数返回二叉树，则函数返回“空空”。(6)Parent（bt，x）：）：求双亲函数。求二叉树求双亲函数。求二叉树bt中结点中结点x的双亲

9、结点。若结点的双亲结点。若结点x是二叉树的根是二叉树的根结点或二叉树结点或二叉树bt中无结点中无结点x，则返回，则返回“空空”。16三、二叉树的性质三、二叉树的性质18 性质性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i1)用归纳法用归纳法证明证明：归纳基归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1 层时，只有一个根结点，2i-1=20=1；假设对所有的 j，1 j i，命题成立;二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1。19性质性质 2：深度为 k 的二叉树上至多含 2k-1 个结点（k1）证明：证明：基于性质1，深度为 k 的二叉

10、树上的结点数至多为 20+21+2k-1=2k-1 20 性质性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1证明：证明：设设 二叉树上结点总数 n=n0+n1+n2又又 二叉树上分支总数 b=n1+2n2而 b=n-1=n0+n1+n2-1由此，由此，n0=n2+121123456789 1011 12 131415满二叉树满二叉树两类特殊的二叉树两类特殊的二叉树满二叉树：满二叉树：深度为深度为 k 且含有且含有2k-1个结点的二叉树。个结点的二叉树。结点编号：结点编号：一般从根开始按层自上而下一般从根开始按层自上而下,每层从每层

11、从左至右对结点连续编号。左至右对结点连续编号。22 性质性质 4：具有 n 个结点的完全二叉树的深度深度为 log2n +1证明：证明：设设 完全二叉树的深度为 k 则根据第二条性质得 2k-1-1n 2k-1,即2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子右孩子结点。用归纳法证明其中的用归纳法证明其中的(2)(2)和和(3)(3)，再导出，再导出(1)(1)。256.3 二叉树的存储结构二叉树的存储结构二、链式存储表示二、链式存储表示一、一

12、、顺序存储表示顺序存储表示 二二叉叉树树的的结结构构是是非非线线性性的的，每每一一个个结点最多可有两个后继。结点最多可有两个后继。26A B C D E F G HIJ K L 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树J123456789101112EFHIKLABDCG28一般二叉树12345711ABCEGFDA B C D EFG 1 2 3 4 5 6 7 8 9 10 11编号规则：根结点的编号为1；对于编号为i的结点，左孩子如果存在，则编号为2i，右孩子如果存在则编号为2i+1。29二、链式存储结构 对于任意的二叉树来说，每个结点最多只有对于任意的二叉树来说，

13、每个结点最多只有两个孩子，我们可以设计每个二叉树结点包括两个孩子，我们可以设计每个二叉树结点包括三个域：三个域：数据域、左孩子域和右孩子域数据域、左孩子域和右孩子域。1.1.二叉链表二叉链表2三叉链表三叉链表 有时，为了找到父结点，可以在二叉链表有时，为了找到父结点，可以在二叉链表中增加一个中增加一个ParentParent域域，ParentParent域指向该结点的域指向该结点的父结点。父结点。LChildDataRChildRChildParentDataLChild31DABCEFGA BCD E F G 二叉树二叉树T T二叉链表二叉链表 一个二叉树若含有一个二叉树若含有n n个结点，

14、则它的二个结点，则它的二叉链表中含有叉链表中含有2n2n个指针域，其中必有个指针域，其中必有n n1 1个空的链域。个空的链域。1.1.二叉链表二叉链表32typedef struct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:33rootADEBCF 2三叉链表三叉链表34三叉链表类型表述如下：typedef char DataType;typedef struct

15、 Node DataType data;struct Node*parent;struct Node*lchild;struct Node*rchild;BiTNode,*BiTree;结点结构:lchild data rchildparent356.4二叉树的遍历二叉树的遍历一、遍历的含义一、遍历的含义三、算法的递归描述三、算法的递归描述四四、二叉树的应用举例二叉树的应用举例二、先左后右的遍历算法二、先左后右的遍历算法36五、由遍历序列确定五、由遍历序列确定二叉树二叉树遍历：遍历：按按一定规律一定规律访问访问二叉树中的每个结点，使二叉树中的每个结点，使得每个结点均被得每个结点均被访问一次访问

16、一次，而且，而且仅被访问一次仅被访问一次。“访问”的含义可以很广，如：输出结点的信息等。一、遍历的含义一、遍历的含义非线性的树线性化的结点访问序列遍历遍历目的：二叉树是非线性结构，每个结点有两个后继，二叉树是非线性结构，每个结点有两个后继，遍历时存在遍历时存在如何遍历如何遍历的问题，即按什么样的的问题，即按什么样的规律规律(搜索路径搜索路径)访问结点访问结点?37 对对“二二叉叉树树”而而言言，可可以以有有三三条条搜搜索索路径：路径：1先上后下先上后下的按层次遍历；2先左先左（子树）后右后右（子树）的遍历；3先右先右（子树）后左后左（子树）的遍历。二叉树的基本结构由二叉树的基本结构由根结点根结

17、点、左子树左子树和和右子树右子树组成组成:RChildDataLChildDataLChildLChildRChild38二叉树的搜索路径二叉树的搜索路径(先左后右先左后右)：39BDCEF第一次经过第一次经过B第二次经过第二次经过B第三次经过第三次经过B问题：那一次经过时访问问题：那一次经过时访问B?二、先左后右的遍历算法二、先左后右的遍历算法先先（根）序的遍历算法DLR中中（根）序的遍历算法LDR后后（根）序的遍历算法LRD根根左子树右子树根根根根根根根根根根401 1、先序遍历（、先序遍历（DLRDLR）操作过）操作过程程 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，

18、（1）访问根结点；）访问根结点；（2）先序遍历左子树；）先序遍历左子树；（3）先序遍历右子树。）先序遍历右子树。412 2、中序遍历（、中序遍历（LDRLDR）操作过）操作过程程 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）中序遍历左子树；）中序遍历左子树；（2）访问根结点；）访问根结点；（3）中序遍历右子树。）中序遍历右子树。423 3、后序遍历（、后序遍历（LRDLRD）操作过）操作过程程 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否则，（1）后序遍历左子树；）后序遍历左子树；（2）后序遍历右子树；）后序遍历右子树；（3）访问根结点。）访问根结点。

19、43ABCDEFGHK例如：例如：先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A44abcdefghij又如:先序遍历先序遍历:a b d h i e j c f g中序遍历中序遍历:h d i b j e a f c g后序遍历后序遍历:h i d j e b f g c a45用二叉树表示表达式用二叉树表示表达式-+/a*efb-cd先序先序:-+a*b-cd/ef:-+a*b-cd/ef中序中序:a+b*c-d-e/f:a+b*c-d-e/f后序后序:abcd-*+ef/-

20、:abcd-*+ef/-三个序列恰好为它的三个序列恰好为它的前缀、前缀、中缀、中缀、后缀后缀表示式表示式原式原式:a+b*(c-d)-e/f:a+b*(c-d)-e/f46三、遍历算法的递归描述 1 1、先序遍历先序遍历void PreOrder(BiTree BiTree root)/*先序遍历二叉树先序遍历二叉树,root为二叉树根结点的指针为二叉树根结点的指针*/if(root!=NULL)Visit(root-data);/*访问根结点访问根结点*/PreOrder(root-LChild);/*先序遍历左子树先序遍历左子树*/PreOrder(root-RChild);/*先序遍历右

21、子树先序遍历右子树*/47void InOrder(BiTree root)/*中中序序遍遍历历二二叉叉树树,root为为二二叉叉树树根根结结点点的的指指针针*/if(root!=NULL)InOrder(root-LChild);/*中序遍历左子树中序遍历左子树*/Visit(root-data);/*访问根结点访问根结点*/InOrder(root-RChild);/*中序遍历右子树中序遍历右子树*/2、中序遍历483、后序遍历void PostOrder(BiTree root)/*后序遍历二叉树，后序遍历二叉树，root为二叉树根结点的指针为二叉树根结点的指针*/if(root!=NU

22、LL)PostOrder(root-LChild);/*后后序序遍遍历历左左子子树树*/PostOrder(root-RChild);/*后后序序遍遍历历右右子子树树*/Visit(root-data);/*访问根结点访问根结点*/49作业P135l2补充1：有3个结点的树有几种形态?有3个结点的二叉树有几种形态?50四四、二叉树的应用举例二叉树的应用举例3、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数4、求二叉树的深度、求二叉树的深度1 1、输出二叉树中的结点、输出二叉树中的结点(先序遍历先序遍历)2 2、输出二叉树中的叶子结点、输出二叉树中的叶子结点511.在二叉树不空的前提下,

23、输出二叉树的根节点;2.输出二叉树的左子树;1、输出二叉树中的结点算法基本思想算法基本思想:3.输出二叉树的右子树;52void Preorder(BiTree root)if(root!=NULL)printf(“%c”,root-data);Preorder(root-lchild);Preorder(root-rchild);1、输出二叉树中的结点说明：输出二叉树中结点无次序要求，三 种遍历都可用。532、输出二叉树中的叶子结点输出二叉树中的叶子结点void PreOrder(BiTree BiTree root)/*先先序序遍遍历历输输出出二二叉叉树树中中叶叶结结点点,root为为二二

24、叉叉树树根根结结点点的的指针指针*/if(root!=NULL)if(root-LChild=NULL&root-RChild=NULL)printf(root-data);/*输出叶结点输出叶结点*/PreOrder(root-LChild);/*先序遍历左子树先序遍历左子树*/PreOrder(root-RChild);/*先序遍历右子树先序遍历右子树*/543、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的参数，的参数，并将算

25、法中“访问结点”的操作改为:若是叶子，则计数器增若是叶子，则计数器增1 1。55void leaf(BiTree root)void leaf(BiTree root)if(root!=NULL)if(root!=NULL)leaf(root-LChild);leaf(root-LChild);leaf(root-RChild);leaf(root-RChild);if(root-LChild=NULL&root-RChild=NULL)LeafCount+;LeafCount+;方法一：设全局变量方法一：设全局变量LeafCount计叶子结点数目，计叶子结点数目，调用前赋初值为调用前赋初值为

26、0 56方法二：空树：返回方法二：空树：返回0；叶子结点，返回；叶子结点，返回1；否则为左右子树的叶子结点数之和否则为左右子树的叶子结点数之和。Int leaf (BiTree root)int LeafCount,L,R;if (root=NULL)LeafCount=0;else if (root-LChild=NULL)&(root-RChild=NULL)LeafCount=1;else L=leaf(root-LChild);R=leaf(root-RChild);LeafCount=L+R;return(LeafCount);574、求二叉树的深度、求二叉树的深度算法基本思想算法基

27、本思想:从二叉树深度的定义可知，二叉树的深度二叉树的深度应为其左、右子树深度的最大值加应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为:求得左、右子树深度的求得左、右子树深度的最大值，然后加最大值，然后加 1 1。首先分析二叉树的深度二叉树的深度和它的左左、右子右子树深度树深度之间的关系。后序遍历！后序遍历！58int Depth(BiTree T)/返回二叉树的深度 if(T=NULL)depthval=0;else depthLeft=Depth(T-lchild);depthRight=Depth(T-rc

28、hild);depthval=1+(depthLeft depthRight?depthLeft:depthRight);return depthval;59五、由遍历序列确定二叉树五、由遍历序列确定二叉树在对一棵二叉树进行遍历，只要遍历的策略已确定，就可以得到一个唯一的结点序列。那么，给定一个遍历的结点序列，能否唯一的确定一棵二叉树？答案：不能！l由结点序列恢复二叉树由结点序列恢复二叉树61先序序列：A B C结点序列确定二叉树的不唯一性ABCABCABCABC中序序列：B A C后序序列：C B A62l由扩展的结点序列恢复二叉树在前面讲述的结点序列中，我们忽略了空子树空子树的输出。假如在

29、遍历二叉树时，我们使用某个特定的符号表示空子树，则称得到的序列为扩展的结点序列。如：扩展的先序序列：AB#C#DE#ADBEC63建立一棵二叉树算法基本思想算法基本思想:首先首先读入当前根结点数据，读入当前根结点数据，如果是如果是，则表示当前树根置为空则表示当前树根置为空，否则否则申请一个申请一个新结点新结点，存入当前根结点的数据，存入当前根结点的数据，分别分别用当前根结点的左子域和右子域进行递用当前根结点的左子域和右子域进行递归调用，归调用，创建左、右子树创建左、右子树。64BiTree CreateBiTree()char ch;BiTreeNode*p;ch=getchar();if(c

30、h=#)return NULL;else p=(BiTreeNode*)malloc(sizeof(BiTreeNode);p-data=ch;p-LChild=CreateBiTree();p-RChild=CreateBiTree();return(p);创建二叉树的算法创建二叉树的算法65 从二叉树的遍历可知，任意一棵二叉树结从二叉树的遍历可知，任意一棵二叉树结点的遍历序列是唯一的。但是，给定结点的遍点的遍历序列是唯一的。但是，给定结点的遍历序列，却不能唯一确定一棵二叉树！历序列，却不能唯一确定一棵二叉树！l 由遍历序列确定二叉树二叉树的先序序列二叉树的先序序列二叉树的中序序列二叉树的中

31、序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根 那么，给定一棵二叉树结点的先序序列和那么，给定一棵二叉树结点的先序序列和中序序列，能否唯一确定一棵二叉树呢？中序序列，能否唯一确定一棵二叉树呢？66 二叉树先序遍历是先访问根结点二叉树先序遍历是先访问根结点D,D,即即第一结第一结点必是根点必是根；另一方面，中序遍历是先左子树，其；另一方面，中序遍历是先左子树，其次是根，最后是右子树，则次是根，最后是右子树，则根结点根结点D D将中序序列将中序序列分割成两部分分割成两部分：D D之前是左子树结点的中序序列，之前是左子树结点的中序序列，D D之后是右子树结点的中序序列。之后是右子树

32、结点的中序序列。对对左子树左子树及及右子树右子树仍可按此方式进一步分解仍可按此方式进一步分解.依次类推，便可递归得到整棵二叉树。依次类推，便可递归得到整棵二叉树。分析：67由结点序列恢复二叉树可恢复二叉树的结点序列组合：（1）先序序列和中序序列（2）中序序列和后序序列不可恢复二叉树的结点序列组合：先序序列和后序序列68a b c d e f gc b d a e g f例如例如:aab bccddeeffggabcdefg先序序列中序序列69由遍历序列确定二叉树由遍历序列确定二叉树练习：由先序和中序序列恢复二叉树，并写出后序遍历序列。先序序列：E B A D C F H G I K J中序序列

33、：A B C D E F G H I J KEBADFHG后序序列：A C D B G J K I H F ECIKJ70由遍历序列确定二叉树由中序和后序序列恢复二叉树中序序列：D C B G E A H F I J K后序序列：D C E G B F H K J I AA练习：IJKHFBGECD71 6.5 树、森林和二叉数的关系及转换树、森林和二叉数的关系及转换1.树和森林的表示方法树和森林的表示方法2.树、森林和二叉树的转换树、森林和二叉树的转换72树的三种存储结构树的三种存储结构一、一、双亲表示法双亲表示法二、二、孩子链表表示法孩子链表表示法三、三、树的二叉链表树的二叉链表(孩子孩子

34、-兄弟）兄弟）存储表示法存储表示法1.树和森林的表示方法树和森林的表示方法73ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent一、双亲表示法一、双亲表示法:结点结构结点结构:data parent74 用一组连续的空间来存储树中的结点，每个用一组连续的空间来存储树中的结点，每个结点附设一个指示器指示其双亲结点在表中的位结点附设一个指示器指示其双亲结点在表中的位置，其结点的结构如下：置，其结点的结构如下：双亲表示法的优点：双亲表示法的优点：利用了树中每个结点（根结点除外）利用了树中每个结点（根结点除外）只有一个双亲结点的性质，使得查找

35、某只有一个双亲结点的性质，使得查找某个结点的双亲结点非常容易。个结点的双亲结点非常容易。双亲表示法的缺点：双亲表示法的缺点：求某个结点的孩子时，需要遍历整求某个结点的孩子时，需要遍历整个表。个表。75 通常是把通常是把每个结点的孩子每个结点的孩子结点排列结点排列起来，起来，构成一个单链表构成一个单链表，称为孩子链表。，称为孩子链表。n n个结点共有个结点共有n n个孩子链表（叶结点的孩个孩子链表（叶结点的孩子链表为空表）。子链表为空表）。n n个结点的数据个结点的数据和和n n个孩子链表的头个孩子链表的头指针又指针又组成一个顺序表组成一个顺序表。二、孩子链表表示法二、孩子链表表示法:76 da

36、ta firstchildABCDEFG64 5 1 2 30 A 1 B2 C 3 D 4 E 5 F 6 G 孩子结点结构孩子结点结构:child nextchild双亲结点结构：双亲结点结构：data firstchild77typedef struct CSNode Elem data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;结点结构结点结构:firstchild data nextsibling三、树的二叉链表三、树的二叉链表(孩子孩子-兄弟）存储表示法兄弟）存储表示法 孩子兄弟表示法孩子兄弟表示法又称又称二叉链表表

37、示法二叉链表表示法，表，表中每个结点设有两个链域，分别指向该结点的中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。第一个孩子结点和下一个兄弟（右兄弟）结点。78树与二叉树均可用树与二叉树均可用二叉链表二叉链表作为存储作为存储结构，则以二叉链表为媒介可导出树与二结构，则以二叉链表为媒介可导出树与二叉树之间的一个对应关系叉树之间的一个对应关系即给定一棵即给定一棵树，可以找到唯一一棵二叉树与之对应树，可以找到唯一一棵二叉树与之对应。【注意】：和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。第一个孩子下一个兄弟FirstChild data Next

38、Sibing左孩子右孩子LChild data RChild79ABCDEFGroot AB C E D F G AB C E D F G 森林的二叉链表森林的二叉链表(孩子孩子-兄弟）存储表示法兄弟）存储表示法root可用于表示森林可用于表示森林80作业P136l8，9并写出后序遍历序列l16 写出递归程序补充2：写出图5-40的两棵二叉树的先序，中序，后序遍历序列812.2.树、森林和二叉树的转换树、森林和二叉树的转换82 树转化成二叉树树转化成二叉树在同胞兄弟之间加在同胞兄弟之间加虚线虚线；保留结点与保留结点与左边第一个左边第一个孩子之间的孩子之间的连线，去掉其余连线；连线，去掉其余连线

39、；顺时针旋转顺时针旋转45度。度。以根结点为轴；左孩子不再旋转。以根结点为轴；左孩子不再旋转。83树二叉树举例：ABCDGEFHABEDHCFG在同胞兄弟之间加在同胞兄弟之间加虚线虚线；保留结点与保留结点与左边第一个左边第一个孩子之间的连线，孩子之间的连线，去掉其余连线；去掉其余连线；顺时针旋转顺时针旋转45度。度。84森林转化成二叉树森林转化成二叉树将森林中的每棵树转换成对应的二将森林中的每棵树转换成对应的二叉树；叉树；按照给出的森林中树的次序，依次按照给出的森林中树的次序，依次将将后一棵后一棵二叉树插入二叉树插入为前一棵为前一棵二叉二叉树根结点树根结点的右子树的右子树；85森林二叉树举例：

40、将森林中的每棵树转换成对应的二叉树；将森林中的每棵树转换成对应的二叉树；按照给出的森林中树的次序，依次将按照给出的森林中树的次序，依次将后一棵后一棵二叉树插入二叉树插入为前一棵为前一棵二叉树根结点二叉树根结点的右子树的右子树；GHIJABCDEFABDCFEGHIJABDCFEGHIJ86二叉树转化成树二叉树转化成树前提：二叉树的根结点前提：二叉树的根结点无右孩子无右孩子1、加线加线：若某结点：若某结点i是双亲结点的左孩子，是双亲结点的左孩子，则将该结点的右孩子以及连续地沿着此则将该结点的右孩子以及连续地沿着此右孩子的右孩子的右链右链不断搜索到的所有右孩子不断搜索到的所有右孩子都分别与结点都分

41、别与结点i的的双亲用虚线连起来双亲用虚线连起来。2、抹线抹线：抹掉原二叉树中所有双亲结点与：抹掉原二叉树中所有双亲结点与右孩子的连线。右孩子的连线。3、归整化归整化：将图形归整化，使各结点：将图形归整化，使各结点按层按层次次排列且将加上去的虚线变成实线。排列且将加上去的虚线变成实线。87二叉树树举例：ABEDHCFG1、加线：若某结点i是双亲结点的左孩子，则将该结点的右孩子以及当且仅当连续地沿着此右孩子的右链不断搜索到的所有右孩子都分别与结点i的双亲用虚线连起来。2、抹线：抹掉原二叉树中所有双亲结点与右孩子的连线。3、归整化：将图形归整化，使各结点按层次排列且将加上去的虚线变成实线。ABDCE

42、GFH88二叉树转化成森林二叉树转化成森林前提：二叉树的根结点必前提：二叉树的根结点必有右孩子有右孩子1、抹线：抹线：将将二叉树的根结点二叉树的根结点与其右孩与其右孩子子i的连线及连续地沿着的连线及连续地沿着i的的右链右链不断不断搜索到的所有右孩子间的连线全部抹搜索到的所有右孩子间的连线全部抹掉，这样得到若干掉，这样得到若干 棵孤立的二叉树。棵孤立的二叉树。2、还原还原：将各棵孤立的二叉树按二叉：将各棵孤立的二叉树按二叉树还原为一般树的方法还原为树。树还原为一般树的方法还原为树。89二叉树森林举例：1、抹线：将二叉树的根结点与其右孩子i的连线当且仅当连续地沿着i的右链不断搜索到的所有右孩子间的

43、连线全部抹掉,这样得到若干棵孤立的二叉树。2、还原：将各棵孤立的二叉树按二叉树还原为一般树的方法还原为树。ABDCFEGHIJGHIJABCDEF906.6 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码哈夫曼树的定义哈夫曼树的定义如何构造最优树如何构造最优树前缀编码前缀编码 91哈夫曼树哈夫曼树 哈夫曼树最典型、最广泛的应用是在哈夫曼树最典型、最广泛的应用是在编码技术上，利用哈夫曼树，可以得到编码技术上，利用哈夫曼树，可以得到平均长度最短的编码。这在通讯领域是平均长度最短的编码。这在通讯领域是极其有价值的。极其有价值的。计算机程序操作码的优化也可以利用计算机程序操作码的优化也可以利用哈夫曼树实现。

44、哈夫曼树实现。92路径：路径：从一个结点到另一个结点之间的分支从一个结点到另一个结点之间的分支 序列。序列。路径长度：路径长度：从一个结点到另一个结点所经过从一个结点到另一个结点所经过 的分支条数。的分支条数。树的路径长度：树的路径长度：树中每个结点与根之间的路径树中每个结点与根之间的路径 长度之和长度之和（PL）。a例：例：PL(a)=1+1+2+2+2+2=10 bPL(b)=1+1+2+2+3+3=12一、基本概念：93带权路径长度：带权路径长度：在树形结构中，我们把从树根在树形结构中，我们把从树根到某一结点的路径长度与该结点权的乘积，称到某一结点的路径长度与该结点权的乘积，称做该结点的

45、带权路径长度。做该结点的带权路径长度。树的带权路径长度：树的带权路径长度：树中所有叶子结点的带权树中所有叶子结点的带权路径长度之和，称为树的带权路径长度，通常路径长度之和，称为树的带权路径长度，通常记为记为WPL：WPL=wilii=1n其中：其中：n n为叶子结点的个数；为叶子结点的个数；w wi i为第为第i i个叶子的权值；个叶子的权值；l li i为第为第i i个叶子结点的路径长度。个叶子结点的路径长度。结点的权：结点的权：给树中每个结点赋予一个具有实际意给树中每个结点赋予一个具有实际意义的数值，我们称该数值为这个结点的权。义的数值，我们称该数值为这个结点的权。94例如下图所示的三棵二

46、叉树例如下图所示的三棵二叉树WPL(a)=7252224236其带权路径长度分别为：其带权路径长度分别为：2 457a7 5 4b25 42c7WPL(b)=4273532146WPL(c)=7152234335 95什么样的树的带权路径长度什么样的树的带权路径长度WPL最小？最小？例如：给定一个权值序列例如：给定一个权值序列2,4,5,7，可构造，可构造多种二叉树的形态多种二叉树的形态:问题：2 457a7 5 4b25 42c7 WPL(a)36 WPL(b)46 WPL(c)35 其带权路径长度分别为：其带权路径长度分别为：96 在各种形态的含有在各种形态的含有 n个叶子结点的个叶子结点

47、的 二二 叉叉树中树中,必存在一棵必存在一棵(几棵几棵)其其带权路径长度值带权路径长度值WPL 最小最小的树，被称为的树，被称为“最优二叉树最优二叉树”。特征：特征：在最优二叉树中没有度数为在最优二叉树中没有度数为 1 的结的结点点(可用反证法证明可用反证法证明);含含 n个叶子结点的最优二个叶子结点的最优二叉树的总结点数为叉树的总结点数为 2*n-1(依据二叉树性质三依据二叉树性质三)。最优二叉树的构造方法最早由哈夫曼最优二叉树的构造方法最早由哈夫曼研究，所以又称为研究，所以又称为“哈夫曼树哈夫曼树”。97二、如何构造最优树二、如何构造最优树（哈夫曼算法）（哈夫曼算法）Step 1:根据给定

48、的根据给定的 n 个权值个权值 w1,w2,wn，构造构造 一个具有一个具有n 棵二叉树的森林棵二叉树的森林F=T1,T2,Tn，其中每棵二叉树中均其中每棵二叉树中均只含一个带权值为只含一个带权值为 wi 的根结点的根结点，其左、右子树为空树；其左、右子树为空树；Step 2:在在 F 中选取其中选取其根结点的权值为最小和次小的根结点的权值为最小和次小的两棵二叉树两棵二叉树，分别作为左、右子树构造一棵新的二，分别作为左、右子树构造一棵新的二叉树，并置这棵叉树，并置这棵新的二叉树根结点的权值为其左、新的二叉树根结点的权值为其左、右子树根结点的权值之和右子树根结点的权值之和；Step 3:从从F中

49、删去这两棵树中删去这两棵树,同时加入刚生成的新树；同时加入刚生成的新树；Step 4:重复重复 2 和和 3 两步两步,直至直至 F 中只含一棵树为止。中只含一棵树为止。98例如:已知权值已知权值 W=5,6,2,9,7 9562752769767139527构造哈夫曼树如下：构造哈夫曼树如下：952716671329哈夫曼算法的实现 n个叶子结点个叶子结点的哈夫曼树共有的哈夫曼树共有2n-1个结点个结点,因此可用有因此可用有2n-1个元素的个元素的数组数组来存储哈夫曼树来存储哈夫曼树,结点间的结点间的关系用游标表示关系用游标表示，即采用，即采用静态链表静态链表来来存储哈夫曼树。存储哈夫曼树。

50、1、存储结构、存储结构 每个结点需包含其双亲结点信息和孩子结每个结点需包含其双亲结点信息和孩子结点信息，所以构成一个静态三叉链表。点信息，所以构成一个静态三叉链表。weight parent Lchild Rchild 权值权值 双亲序号双亲序号 左孩子序号左孩子序号 右孩子序号右孩子序号 100静态三叉链表结构定义#define N 20#define M 2*N-1 typedef struct int weight;int parent，Lchild，Rchild;HTNode,HuffmanTreeM+1;/*0号单元不用号单元不用*/静态三叉链表静态三叉链表数组中数组中前前 n 个元