数据结构及应用算法教程（修订版） 数据结构_第6章_二叉树和树.ppt

《数据结构及应用算法教程（修订版） 数据结构_第6章_二叉树和树.ppt》由会员分享，可在线阅读，更多相关《数据结构及应用算法教程（修订版） 数据结构_第6章_二叉树和树.ppt（153页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、6.1 二叉树 6.3 树和森林 6.1.1 二叉树的定义和术语 6.3.1 树和森林的定义 6.1.2 二叉树的基本性质 6.3.2 树和森林的存储结构 6.1.3 二叉树的存储结构 6.3.3 树和森林的遍历 6.2 二叉树遍历 6.4 树的应用 6.2.1 问题的提出 6.4.1 堆排序 6.2.2 遍历算法的描述 6.4.2 二叉排序树 6.2.3 二叉树遍历应用举例 6.4.3 赫夫曼树及其应用 6.2.4 线索二叉树,主要内容,线性结构,线性表,定义 基本操作,顺序表,链 表,逻辑结构,存储结构,比较,基本操作的实现 时间性能 优缺点,知识回顾,特殊线性表,栈,栈的定义 操作特性,

2、顺序栈,链 栈,逻辑结构,存储结构,比 较,比较,基本操作的实现 时间性能,队 列,队列定义 操作特性,循环队列,链队列,操作的实现 时间性能,逻辑结构,存储结构,串,逻辑结构,存储结构,定义 基本操作,顺序存储,块 链存储,模式匹配,树型结构是一类重要的非线性数据结构，用来描述数据元素之间存在的一对多的层次关系。树结构所描述的信息模型在客观世界普遍存在,是现实生活和实际应用中一类问题的抽象。,例:磁盘文件结构,6.1 二叉树 6.1.1 二叉树的定义和术语 1.二叉树的结构定义： 二叉树是n(n=0)个数据元素的有限集，它或为空集(n=0)，或 为非空集。对于非空集有： （1）有一个特定的称

3、之为根的元素； （2）除根以外的其余元素分为两个互不相交的子集,每个子集自身也是一棵二叉树，分别称为根的左子树和右子树。 结点:二叉树中的数据元素，除根结点外每个结点有且仅有一个直接前驱，但有零个或多个直接后继。,二叉树的定义是采用递归方法,注意: (1)二叉树中的左子树和右子树是两棵互不相交的二叉树，因此，二叉树上除根之外的任何结点不可能同时在两棵子 树中出现，它或者在左子树中，或者在右子树中。 (2)二叉树上每个结点至多有两棵子树，并且，二叉树 的两棵子树有左右之分，其次序不能任意颠倒。,具有3个结点的二叉树的形态,2.基本术语,借用了家族中的一些惯用名词: 孩子结点 双亲结点 兄弟结点

4、堂兄弟结点 祖先结点 子孙结点,结点：包含一个数据元素及若干指向其它结点的分支信息 若r是二叉树中某个结点，n是它的左子树（或右子树）的根，则称n是r的左孩子（或右孩子），r是n的双亲。 注意：二叉树中的根结点没有双亲 若两个结点的双亲为同一结点，则这两个结点互为兄弟。 如右图，H和J及M和I 均互为兄弟，而K和M 不是兄弟，但可以称为 堂兄弟。 祖先结点：是从根到该结点所经分支上的所有结点。 子孙结点：以某结点为根的子树中的任一结点，都称为该 结点的子孙。,D,H,I,J,M,K,结点的度：一个结点的子树个数称为此结点的度。二叉树 中结点度数的最大值为2。 树的度：是树内各结点的度的最大值。

5、 叶子结点（或终端结点）:度为0的结点，即无后继的结点, 二叉树中其左右子树均为空的结点。 非叶子结点(分支结点)：度不为0的结点,至少有一棵子树。 结点在二叉树中的层次:从根开始定义起,根所在的层次为1,根的孩子为第2层,依次类推,若某节点在第L层,则其子树的 根在L+1层。 二叉树的深度：二叉树中叶子结点的最大层次数定义为二叉树的深度。,两种特殊形态的二叉树： (1)满二叉树：若二叉树中所有的分支结点的度数都为2，且叶 子结点都在同一层次上，则称这类二叉树为满二叉树。,满二叉树的特点：,叶子只能出现在最下一层； 只有度为0和度为2的结点。,(2)完全二叉树： 对满二叉树从上到下，从左到右进

6、行从1开始的编号，则得完全二叉树的定义：对一棵包含n个结点的二叉树中每个结点，都可以和满二叉树中编号为1至n的结点一一对应，则称这类二叉树 为完全二叉树。,完全二叉树特点： 若某结点没有左孩子,则它一定没有右孩子;即该结点必是叶子结点。 一棵深度为h的完全二叉树中,前h-1层中的结点都是“满”的,且 第h层的结点都集中在左边。 满二叉树本身也是完全二叉树.,3.基本操作 1）InitBiTree( / 二叉树的最大结点数 typedef struct TElemType *data; /存储空间基址 int nodenum; /树中结点数 SqBiTree; / 完全二叉树的顺序存储结构 若地

7、址从0编号，则第i号结点的左右孩子一定保存在第2(i+1)-1及2(i+1)号单元中；其双亲保存在(i+1)/2-1号单元中。 缺点：对非完全二叉树而言，浪费存储空间。 2.二叉树的链式存储表示 用链表存储二叉树中的结点,即利用指针表示结点之间的关系。由二叉树的定义可知，二叉树中的结点由一个数据元素和分别指向其左、右子树的两个分支构成。,通常采用的方法是： 二叉链表：每个结点中设置三个域，数据域和分别指向左、右子树的指针域。 结点结构: 三叉链表：为了便于找结点的双亲，可以在上述结点结构中增加一个指向其双亲的指针。 链表的头指针指向二叉树的根结点。 结点结构:, 二叉链表 typedef st

8、ruct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree；,A,D,F,C,B,E,root,G,H,I, 三叉链表 typedef struct TriTNode struct TriTNode *parent; TElemType data; struct TriTNode *lchild, *rchild; TriTNode, *TriTree;,6.2 二叉树遍历 6.2.1 问题的提出 1. 概念 问题：如何不重复地访问二叉树中每一个结点？ 遍历:是指按某一条搜索路径巡访二叉树中的结点

9、,使得每个结点均被访问一次，而且仅被访问一次。（将树线性化） “访问”的含义可以很广,如：输出结点的信息或修改数据信息等。 “遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继, 则存在按什么样的搜索路径遍历的问题。,2. 遍历二叉树方法： (1) 访问根，遍历左子树，遍历右子树（记做DLR）; (2) 访问根，遍历右子树，遍历左子树（记做DRL）; (3) 遍历左子树，访问根，遍历右子树（记做LDR）; (4) 遍历左子树，遍历右子树，访问根（记做LRD）; (5) 遍历右子树，访问根，遍历左

10、子树（记做RDL）; (6) 遍历右子树，遍历左子树，访问根（记做RLD）。 先左后右的遍历算法: DLR:先（根）序遍历（又称前序遍历） LDR:中（根）序的遍历算法 LRD:后（根）序的遍历算法 层次遍历(从上到下,从左向右),若二叉树为空树，则空操作；否则:,虚线代表先左后右的搜索路径:向下箭头为递归调用,向上箭头为从递归调用返回。 :先序访问序列（ABDEC）; :中序访问序列（DBEAC）; ：后序访问序列（DEBCA）。,三种遍历方式使用时注意: 在3种不同遍历方式中，各叶子结点之间的相对次序是相同 的，它们都按叶子结点之间从左到右的次序排列 ; 前序遍历有助于查询结点间的祖先和子

11、孙关系(先祖先 ,后子 孙); 后序遍历也有助于查询结点间的子孙和祖先关系.(先子孙,后 祖先)。 6.2.2 遍历算法的描述 二叉树的三种遍历，递归的终止条件是二叉树为空，此时为空操作。假设以二叉链表为存储结构，并将结点的访问操作抽象为一个函数visit，则先序遍历二叉树的递归算法如下：,算法 6.1 先序遍历以T为根指针的二叉树 void visit (BiTree T) coutdatalchild, visit); / 先序遍历左子树 PreOrder(T-rchild, visit); / 先序遍历右子树 /PreOrder,下面是一二叉树的先序递归算法的详细执行情况： 总结：在树中

12、，树深为2，递归调用的深度为3。,void InOrder (BiTree T , void (*visit)(BiTree) ) /中序遍历递归算法 if (T!=NULL) InOrder (T-lchild, visit); / 遍历左子树 visit(T); / 访问结点 InOrder (T-rchild, visit); / 遍历右子树 /InOrder void PostOrder (BiTree T , void (*visit)(BiTree) /后序遍历递归算法 if (T!=NULL) PostOrder (T-lchild, visit); / 遍历左子树 PostOr

13、der (T-rchild, visit); / 遍历右子树 visit(T); / 访问结点 /PostOrder,中序遍历算法的非递归描述 （1）需要设计一个栈S来存放所经过的根结点的指针；（2）对中序遍历来说，第一次遇到根结点并不访问,而是入栈，然后中序遍历左子树，左子树遍历结束后，第二次遇到根结点，就将根结点（指针）退栈，并且访问根结点，随后中序遍历右子树，在需要退栈时，若栈空则结束。定义栈的元素类型, 其中的任务性质域task记录遍历过程每一步的工作状态. typedef enumTravel=1,Visit=0 TaskType; /Travel为1:工作状态是遍历;Visit为0

14、:工作状态是访问. typedef struct BiTree ptr; /指向二叉树结点的指针 TaskType task; /任务的性质 SElemType; /栈元素的类型定义,算法 6.2 void InOrder_iter(BiTree BT,void(*visit)(BiTree) / 利用栈实现中序遍历二叉树，BT为指向二叉树的根结 /点的头指针 InitStack(S); e.ptr=BT; e.task=Travel; / e为栈元素 if(BT) Push(S, e); / 布置初始任务 while(!StackEmpty(S) / 每次处理一项任务 Pop(S,e); i

15、f(e.task=Visit) visit(e.ptr); / 处理访问任务 else,if(e.ptr) / 处理非空树的遍历任务 p=e.ptr; e.ptr=p-rchild; e.task=Travel; Push(S,e); / 最不迫切任务(遍历右子树)进栈 e.ptr=p; e.task=Visit; Push(S,e); /处理访问任务的工作状态进栈 e.ptr=p-lchild; e.task=Travel; Push(S,e); /迫切任务(遍历左子树)进栈 /if /while /InOrder_iter,/直接利用栈： void InOrder(BiTree root)

16、 SqStack S; InitStack (S); BiTree p=root; while(p!=NULL|!StackEmpty(S) if (p!=NULL) / 根指针进栈， 遍历左子树 Push(S,p); p=p-lchild; else Pop(S, p); visit(p); p=p-rchild; /根指针退栈， 访问根结点， 遍历右子树 /Inorder,对照下图所示的二叉树，在中根非递归遍历过程中其栈s的内容变化 :,T,B,遇根D进栈 遍D左子树,C,D,补：二叉树的层次遍历 层次遍历是指从二叉树的每一层(根结点)开始,按从上到下逐层遍历,每一层则按从左到右的顺序逐个

17、访问。如下图的二叉树，遍历结果为：A B C D E 分析：根据层次遍历的定义，在进行层次遍历时，对每一层结点访问完后，再按照它们的访问次序对各个结点的左右孩子顺序访问，这样一层一层进行，先遇到的结点其左右孩子也先被访问，与队列的操作原则吻合。,算法：设置一队列，根结点指针入队列，然后队首元素出队列，每出队一个元素，执行如下操作： 访问该元素所指结点 若该元素所指结点的左右孩子非空,则该元素所指结点的左右孩子指针入队列 如此不断进行，当队列为空，遍历结束。,层次遍历,遍历序列：,A,A,B,C,B,D,C,E,F,G,D,E,F,G,二叉树的层次遍历 void LevelOrder(BiTre

18、e T) SqQueue Q; /为循环队列 BiTree e; if(T=NULL) return;/二叉树为空，返回 EnQueue(Q,T); while(Q.front!=Q.rear) DeQueue(Q,e); visit(e); if(e-lchild!=NULL) EnQueue(Q,e-lchild); if(e-rchild!=NULL) EnQueue(Q,e-rchild); /while /LevelOrder,补充习题: 7.具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其中（ ）个指针域为空。 A）50 B）99 C）100

19、D）101 8.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为（ ）。 A）前序遍历 B）后序遍历 C）中序遍历 D）层次遍历 9.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ ）。 A）不发生变化 B）发生变化 C）不能确定 D）以上都不对,7.说明:已知:n=n0+n1+n2,指针域为空个数:2*n0+n1=n0+n1+n2+1, 即n+1. D 8.C 9.A,补充习题: 10.某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是（ ）的二叉树。 A）空或只有一个结点 B）高度等于其结点数 C）任一结点无左孩子 D）任一结点无右孩子 11

20、.如果某二叉树的先序遍历序列是abdcef，中序遍历序列是dbaefc，则其后序遍历序列是（ ）。 A）dbafec B）fecdba C）efcdba D）dbfeca 12.按照二叉树的定义，具有3个结点的二叉树形态有( )种。 A）3 B）4 C）5 D）6 13.二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的前面（ ）。 A）正确 B）错误,10.B 11.D 12.C 13.B,6.2.3 二叉树遍历应用举例 例6.1 建立二叉树的存储结构-二叉链表(算法6.3) 假设按先序遍历的顺序建立二叉链表,T为指向根结点的指针: 首先输入一个根结点，若输入的是#，则表明该二叉树为 空

21、树，即T=NULL; 否则输入的字符应赋给T-data,之后依次递归建立它的左 子树T-lchild和右子树T-rchild。 如图二叉树,输入顺序为:AB#DE#C# 其中#表示空子树.,void CreateBiTree(BiTree / 递归建(遍历)右子树 /else /CreateBiTree,算法执行过程举例如下：,cin ch; if (ch= #) T = NULL; else T = new BiTNode; T-data = ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); ,例6.2 求二叉树的深度(算法 6.4) 二

22、叉树的深度为二叉树中叶子结点所在层次的最大值。结点的层次需从根结点递推，设根结点为第1层，第k层结点的子树根在第k+1层。遍历二叉树时求每个结点的层次数,其中的最大值为二叉树的深度. void BiTreeDepth(BiTree T, int h, int /BiTreeDepth,主函数中求T所指二叉树的深度: d=0; BiTreeDepth(T, 1,d); 若T所指为空树，则算法6.4空操作，d 仍等于0。非空时执行过程：,L=1 H=0,L=1 H=1,L=2 H=2,L=3 H=3,L=2 H=3,L=3 H=3,L=4 H=4,L=3 H=4,H=4,求二叉树的深度(后序遍历

23、算法 6.5 ) 算法基本思想:从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子 树深度的最大值，然后加1。 int BiTreeDepth(BiTree T) / 后序遍历求T所指二叉树的深度 if (!T) return 0; else hL=BiTreeDepth(T-lchild); hR=BiTreeDepth(T-rchild); if (hL=hR) return hL+1; else return hR+1; /BiTreeDepth,例6.3 复制一棵二叉树 复制一棵二叉树即按原

24、二叉树的结构重新生成一棵二叉树,其实质是按原二叉树的二叉链表生成一个新的二叉链表。 生成一个二叉树的结点的算法： BiTNode *GetTreeNode(TElemType item,BiTree lptr,BiTree rptr) /生成一个其元素值为item，左指针为lptr,右指针为rptr的结点 BiTNode *T=new BiTNode; T-data=item; T-lchild=lptr; T-rchild=rptr; return T; 后序遍历复制二叉树的操作即为先分别复制已知二叉树的左、右子树，然后生成一个新的根结点，则复制得到的两棵 子树的根指针是这个新生成的结点的左

25、、右指针域的值。,算法 6.6：已知二叉树的根指针为T，本算法返回它的复制品的根指针。 BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; / 复制一棵空树 if (T-lchild ) newlptr = CopyTree(T-lchild); / 复制(遍历)左子树 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild); / 复制(遍历)右子树 else newrptr = NULL; newnode = GetTreeNode(T-data, newlptr,

26、newrptr); / 生成根结点 return newnode; / CopyTree,二叉树的复制过程：,newT,例6.4 求存于二叉树中表达式的值 以二叉树表示表达式的递归定义: 若表达式为数或简单变量，则相应二叉树只有一个结点，其数据域存放该表达式的信息；若表达式=(第一操作数)(运算符)(第二操作数)，则相应的二叉树以左子树表示第一操作数，以右子树表示第二操作数，根结点存放运算符（若为一元运算符，则左子树为 空），操作数本身也可是表达式。如表达式： exp=(a+b)/(c-d)e)(-f) 按运算符的优先关系分解为： 第一操作数：(a+b)/(c-d)e） 运算符： 第二操作数：

27、-f 类似，第一操作数可分解为：(a+b)、/、(c-d)e,表达式求值的过程实际上是一个后序遍历二叉树的过程，因二叉树上任何一个运算符的左右“操作数”都是一个表达式，则处理一个“运算符”前，其左右操作数表达式的值必须已经求出（空表达式的值为0）。 用一维数组存放所有和简单变量操作数对应的数值。 二叉树结点数据域为正数时，其值是操作数所在数组位置的对应下标；其值为负数时，其值为运算符，值的绝对值的大小用以表示运算符的类型。 const PLUS=-1； const MINUS=-2； const ASTERISK=-3； const SLANT=-4:,double value(BiTree

28、T, double opnd) /对以T为根指针的二叉树表示的算术表达式求值，操作 /数的数值存放在一维数组opnd中. if (!T) return 0; / 空树的值为0 if (T-data=0) return opndT-data; Lv = value(T-lchild, opnd); / 遍历左子树求第一操作数 Rv = value(T-rchild, opnd); / 遍历右子树求第二操作数 switch (T-data) case PLUS: v = Lv + Rv; case MINUS: v = Lv - Rv; case ASTERISK: v = LV * Rv; ca

29、se SLANT: v = Lv / Rv; default: ERROR(不合法的运算符); /switch return v; /value,6.2.4 线索二叉树 1.何谓线索二叉树？遍历二叉树的过程是沿着某一条搜索路径对二叉树中结点进行一次且仅仅一次访问。也就是说按一定规则将二叉树中结点排成一个线性序列之后进行依次访问 显然，这种信息是在遍历的动态过程中产生的，如果将这些信息在第一次遍历时就保存起来，当需要再次对二叉树进行“遍历”时就可以将二叉树视为线性结构进行访问了。 如何保存这种在遍历过程中得到的信息？ 最简单的方法是在每个结点上增加两个指针域：pred和succ用来指示此结点在遍

30、历中的前驱和后继结点，称这些指针为“线索”，加上线索的二叉树为“线索二叉树”，相应的存储结构，称作“线索链表”。,线索链表中的结点结构描述： typedef char TElemType; typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 struct BiThrNode *pred, *succ; / 前驱，后继线索 BiThrNode, *BiThrTree; 仿照线性表的双向链表，在二叉树的全线索链表上也添加一个“头结点”，该结点的“左指针”指向二叉树的根结点， “右指针”

31、为空，“右线索”指向中序遍历的第一个结点,“左线索” 指向中序遍历的最后一个结点。,实线表示指针，虚线表示线索,H,T,二叉树的中序全线索链表,以中序全线索链表作存储结构时的中序遍历算法（算法 6.8） void InOrder(BiThrTree H，void (*visit)( BiThrTree ) ) / H 为指向中序线索链表中头结点的指针， / 本算法中序遍历以H-lchild所指结点为根的二叉树 p = H-succ; while( p!=H ) visit(p); p = p- succ; /InOrder 建立中序线索链表的过程即为中序遍历的过程，需在遍历过程中附设一个指向“

32、当前访问”结点的“前驱”的指针pre，而访问操作就是“在当前访问结点与它的前驱之间建立线索”。,建立根指针T所指二叉树的中序全线索链表（算法 6.9） void InOrderThreading(BiThrTree /InOrderThreading,对以根指针p所指二叉树进行中序遍历，在遍历过程中进行线索化,p为当前指针,pre是跟随指针, pre指向他的前驱,比p慢一拍遍历二叉树（算法 6.10） void InThreading(BiThrTree p，BiThrTree / 右子树线索化 /InThreading,补充习题: 14.n个结点深度为h的二叉树的线索化所需的时间复杂度是(

33、)。 A)O(1) B)O(hn) C)O(n) D)O(nlog2h) 15.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是( )。 A)a是b祖先 B)a是b子孙 C)a在b左方 D)a在b右方 16.关于二叉树的三种遍历，下列说法正确的是( )。 A)任意两种遍历序列都不可以唯一决定该二叉树 B)任意两种遍历序列都可以唯一决定该二叉树 C)先序遍历序列和后序遍历序列可以唯一决定该二叉树 D)先序遍历序列和中序遍历序列可以唯一决定该二叉树 17.在某棵二叉树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可判断定这种序列为中序序列( )。 A)正确 B)不正确,1

34、4.C 15.C 16.D 17.B,补充习题: 18.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是（ ）。 A)acbed B)decab C)deabc D)cedba 19.前序遍历和中序遍历结果相同的二叉树为（ ）。 A)只有根结点的二叉树 B)所有非叶子结点只有右子树的二叉树 C)根结点无右孩子的二叉树 D)根结点无左孩子的二叉树 20.前序遍历和后序遍历结果相同的二叉树为（ ）。 A)只有根结点的二叉树 B)所有非叶子结点只有右子树的二叉树 C)根结点无右孩子的二叉树 D)根结点无左孩子的二叉树,18.D 19.B 20.A,知识小结: 1.

35、二叉树的遍历算法:先序、中序、后序和层次遍历 2.中序遍历的非递归算法 3.先序遍历创建二叉树（注意输入序列） 4.先序遍历及后序遍历求二叉树的深度 5.后序遍历复制一棵二叉树（后序创建二叉树） 6.后序遍历求存于二叉树中的表达式的值。 7.线索二叉树。,6.3 树和森林 6.3.1 树和森林的定义 1.树的定义:是n个数据元素的有限集D，若D为空集，则为空树，否则： (1)在D中存在惟一的称为根的数据元素root; (2)当n1时，其余结点可分为m(m0)个互不相交的有限集 T1,T2, ，Tm,其中每一个子集本身又是一棵符合本定义 的树，并称为根root的子树。 2.基本术语（与二叉树的类

36、似）不同的是： a.树的度：一棵树中各结点度的最大值称为该树的度。 b.有序树：子树之间存在确定的次序关系。 c.无序树：子树之间不存在确定的次序关系。,3.森林：是m（m0）棵互不相交的树的集合,任何一棵非空树是一个二元组。 Tree =（root，F） 其中：root 被称为根结点，F被称为子树森林。,4.树的基本操作 InitTree( typedef struct PTNode /结点结构 elem data; /结点数据域 int parent; /双亲位置域 PTNode; typedef struct /树结构 PTNode nodesmax_tree_size; int r,

37、n; /树根结点的位置和结点个数 PTree;,双亲表示法:,2. 孩子链表表示法:以单链表将所有双亲相同的孩子结点连接在一起,并将该链表的头结点和双亲构成树中的一个结点,全部树结点以顺序组织构成树结构。定义如下： typedef struct CTNode /孩子结点结构 int child; struct CTNode *next; *ChildPtr; typedef struct /双亲结点结构 Elem data; ChildPtr firstchild; /孩子链的头结点 CTBox; typedef struct /树结构 CTBox nodesmax_tree_size; in

38、t n,r; /结点数和根结点的位置 CTree;,孩子链表表示法:,A,B,C,D,E,F,G,0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 4,r=0 n=7,data firstchild,1 2 3,4 5,6,-1 0 0 0 2 2 4,3. 树的二叉链表 (孩子-兄弟）存储表示法 类似于二叉树的二叉链表，只是树结点中的两个指针域分别指向其“最左”孩子结点和“右兄弟”结点。类型定义如下： typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CS

39、Node, *CSTree; 分析：左指针为空，说明该结点无孩子。 右指针为空，说明该结点无右兄弟;那么，根结点有右兄弟吗？,树的二叉链表存储结构表示:,要求:将一棵树转化为二叉树,4. 森林存储结构 把森林中的各棵子树分别用树的二叉链表（孩子-兄弟）表示法存储，然后，将第二棵子树的根结点作为第一棵子树的右孩子，第三棵子树的根结点作为第二棵子 树的右孩子。 森林和二叉树的对应关系 设森林 F = ( T1, T2, , Tn ); T1 = (root，t11, t12, , t1m); 二叉树 B =( LBT, Node(root), RBT );,由森林转换成二叉树的转换规则为: 若 F

40、 = ，则 B = ； 否则，由 ROOT( T1 ) 对应得到 Node(root)； 由 (t11, t12, , t1m ) 对应得到 LBT； 由 (T2, T3, Tn ) 对应得到 RBT。 由二叉树转换为森林的转换规则为： 若 B = ， 则 F = ； 否则，由 Node(root) 对应得到 ROOT( T1 )； 由LBT 对应得到 ( t11, t12, ，t1m)； 由RBT 对应得到 (T2, T3, , Tn)。 由此，树的各种操作均可由对应二叉树的操作来完成。 应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为： 左是孩子，右是兄弟。,A,E,G,B,C,

41、F,H,I,J,D,A,B,C,D,E,F,G,H,I,J,A,B,C,D,E,F,G,H,I,J,树与二叉树对应,树根相连,森林与二叉树对应,6.3.3 树和森林的遍历 1树的遍历 先根（次序）遍历树：若树不空，则先访问根结点，然后 依次先根遍历根的各棵子树； 后根（次序）遍历树：若树不空，则先依次后根遍历根的 各棵子树，然后访问根结点； 按层（次序）遍历树：若树不空，则从根结点，依结点所 在层次从小到大、每一层从左到右依次访问各个结点； 分析：树的先根遍历和后根遍历和其对应二叉树的先序遍历 和中序遍历相同。,树的先根遍历:ABCEHDFG 树的后根遍历:BHECFGDA 树的层次遍历:AB

42、CDEFGH,A,B,C,D,E,H,F,G,A,B,C,D,E,H,F,G,二叉树的先序遍历:ABCEHDFG 二叉树的中序遍历:BHECFGDA,2.森林的遍历 森林由三部分构成:森林中第一棵树的根结点； 森林中第一棵树的子树森林； 森林中其它树构成的森林。 先序遍历森林：若森林非空，则可按下述规则遍历： 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。 即：依次从左至右对森林中的每一棵树进行先根遍历。 中序遍历森林：若森林非空，则可按下述规则遍历： 中序遍历第一棵树中根结点的子树森林； 访问第一棵树的根结点； 中序遍历除去第

43、一棵树之后剩余的树构成的森林。 即：依次从左至右对森林中的每一棵树进行后根遍历,树的遍历和二叉树遍历的对应关系 ？ 树 森林 二叉树 先根遍历 先序遍历 先序遍历 后根遍历 中序遍历 中序遍历 例6.5 求森林的深度 森林的深度为森林中各棵树的深度的最大值，则树的深度可定义为: 子树森林的深度。取孩子-兄弟链表作为森林的存储结构时，根结点的左分支所指是森林中第一棵树的子树森林，右分支所指是森林中去掉第一棵树之后，由其余的树 构成的森林。 深度（森林）max（左分支所指森林的深度+1，右分支所指 森林深度）,算法 6.11 int TreeDepth(CSTree T) if(!T) retur

44、n 0; else h1 = TreeDepth( T-firstchild ); h2 = TreeDepth( T-nextsibling); return(max(h1+1, h2); / TreeDepth,例6.6 输出树T中从根到所有叶子结点的路径（先序遍历） 叶子结点的特征:左子树为空;对树中兄弟结点而言, 其“兄长”不应是路径上的结点，因此在遍历右子树时，应将根结点从路径中删除。 void OutPath( CSTree T，Stack / 继续遍历右子树求其它叶子结点路径 / while / OutPath 算法 6.12(a),A,B,C,D,E,H,F,G,例6.7:按自

45、上而下自左至右的次序输入双亲-孩子的有序对(#,A), (A, B), (A,C), (A,D), (C, E), (D, F), (D,G), (E,H), (#,#),建立树的二叉链表。输入时，以一对#字符作为结束标志，根结点的双亲空，亦以# 表示之。 按层次遍历的顺序来建立孩子-兄弟链表,即先建根结点,再建第二层,同时建立根与孩子结点间的链接关系依次类推。结点输入顺序为“先到先建”，用队列作辅助工具，即按照结点生成的先后顺序，将已建好的结点“指 针”入队列。,void CreateTree( CSTree / 链接其它孩子结点 /else /CreateTree,(A,B), (A,C)

46、,(A,D),(B,E),(D,F),(D,G),(A,B),a,b,c,d,e,f,(A,C),(A,D),(B,E),(D,F),队列,(#,A),树结构和线性结构的比较,线性结构,树结构,无前驱,无双亲,无后继,无孩子,一个前驱,一个后继,一个双亲,多个孩子,一对一 一对多,补充习题: 21.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树对应的二叉树。那么以下结论中，( )是正确的。 A)树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B)树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C

47、)树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D)以上都不对 22.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（ ） A)根结点无右子树的二叉树 B)根结点无左子树的二叉树 C)根结点可能有左二叉树和右二叉树 D)各结点只有一个儿子的二叉树,21.A 22.C,知识小结: 1.树和森林的定义及相关概念 2.树的三种存储结构及其特点(双亲表示法、孩子链表表示法、孩子-兄弟二叉链表) 3.树和森林与二叉树的转换方法 4.树和森林的遍历及与二叉树遍历的比较 5.层次遍历建立孩子-兄弟链表 6.先根遍历求根到叶子结点的路径 7.类后序遍历求森林的深度,6.4 树的应用 6.4.1 堆排序(heap sort)的实现 1. 堆的定义：堆是满足下列性质的数列r1, r2, r3 rn :,则r1必是数列中最小值或最大值，称作小顶堆或大顶堆