大学数据结构课件6.树和二叉树.ppt

第6章 树和二叉树,前面讲的线性表主要表现的是数据元素之间的前后次序关系，是一种线性结构。树型结构是以分支关系定义的层次结构。树形结构在客观世界中广泛存在，如人类的家庭族谱及各种社会组织机构。又如计算机文件管理和信息组织也用到树形结构。本章讨论树的基本概念，重点讨论二叉树的有关概念、性质、存储结构和各种运算。,6.1.1 树的定义,树(tree)是由n(n0)个结点组成的有限集合T。n=0的树称为空树；对n0的树，有:(1)仅有一个特殊的结点称为根(root)结点，根结点没有前驱结点；(2)当n1时，除根结点外其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm，其中每个集合Ti本身又是一棵树，称之为根的子树（subtree）。,注：树的定义具有递归性，即“树中还有树”。仅有一个根结点的树是最小树，,6.1 树基本概念和术语,6.1.2 若干术语（从结构上分）,分支结点：度不为0的结点，除叶结点之外的其余结点。,结点（node）：由数据元素和构造数据元素之间关系的指针组成,结点的度：结点所拥有的子树的个数,树的度：树中所有结点的度的最大值,叶结点：度为0的结点，也称作终端结点,结点的层次：从根结点到树中某结点所经路径上的分支数,树的深度：树中所有结点的层次的最大值,森林：m（m0）棵树的集合,6.1.2.若干术语（从关系上分）,孩子(child)结点：树中一个结点的子树的根结点双亲(parent)结点：若树中某结点有孩子结点，则这个结点就称作它的孩子结点的双亲结点 兄弟(sibling)结点：具有相同的双亲结点的结点,无序树：树中任意一个结点的各孩子结点之间的次序构成 无关紧要的树有序树：树中任意一个结点的各孩子结点有严格排列次序的树,6.1.2 若干术语（从结构上分）,树的表示形式,6.1.4 树的抽象数据类型,数据集合:树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。操作集合:（1）创建MakeTree(T)（2）撤消DestroyTree(T)（3）双亲结点Parent(T,curr)（4）左孩子结点LeftChild(T,curr)（5）右兄弟结点RightSibling(T,curr)（6）遍历树Traverse(T,Visit(),树的存储结构,树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。指针有常规指针和仿真指针,(1)双亲表示法,(a)一棵树,（b)仿真指针的双亲表示法存储结构,树及其使用仿真指针的双亲表示法,(2)孩子表示法,常规指针的孩子表示法,双亲孩子表示法,(3)双亲孩子表示法,(4)孩子兄弟表示法,常规指针的孩子兄弟表示法,6.2 二叉树,二叉树(binary tree)：是n(n0)个结点的有限集合。n=0的树称为空二叉树；n0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。其逻辑结构：一对二（1:2）左、右子树也是二叉树，所以子树也可以为空树。下图展现了五种不同形态的二叉树。,二叉树的定义,基本特征:每个结点最多只有两棵子树（不存在度大于2的结点）；左子树和右子树次序不能颠倒。所以下面是两棵不同的树,二叉树的定义,满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。,完全二叉树：如果一棵深度为k，有n个结点的二叉树中各 结点能够与深度为k的顺序编号的满二叉树从1到n标号的 结点相对应的二叉树称为完全二叉树。如下图所示,(a)满二叉树,(b)完全二叉树,数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。操作集合：（1）创建MakeTree(T)（2）撤消DestroyTree(T)（3）左插入结点InsertLeftNode(curr,x)（4）右插入结点InsertRightNode(curr,x)（5）左删除子树DeleteLeftTree(curr)（6）右删除子树DeleteRightTree(curr)（7）遍历二叉树Traverse(T,Visit(),二叉树抽象数据类型,二叉树的重要性质,性质1:二叉树的第i（i1）层上至多有2i-1个结点。,二叉树的重要性质,性质2:深度为k(k1)的二叉树至多有2k-1个结点。,证明一：20+21+22+2k-1=2k-1,1+,-1,=21,=22,=23,=2k-1,=2k,=20,1 00 0 0,+1,证明三：等比数列前n项和的计算公式：,证明二：,n=k,a1=1,q=2,性质3 对于一棵非空的二叉树，如果叶结点个数为n0，度为2的结点数为n2，则有n0=n2+1。,n0=n2+1。,证明：设n为二叉树的结点总数，n1为二叉树中度为1的结点个数，则有：,n=n0+n1+n2(1),由于二叉树中除根结点外，每个结点都有一条与其父结点相连的边。所以，有n个结点的二叉树总共有 n-1条边。于是有：,n-1=0n0+1n1+2n2(2),再把(1)代入(2)，得：,n0+n1+n2-1=n1+2n2,则可以得到:,性质4:具有n个结点的完全二叉树的深度为log2(n)+1。,k-1=log2(n),证明：根据性质2，对于有n个结点的深度为k的完全二叉树有:,2k-1-1n2k-1,因为该不等式各项均为整数，当对两端各加1时不等式发生变化得：,2k-1 n 2k,对不等式求对数，有,k-1log2(n)k,因为k必须是整数，所以对log2(n)取整，即log2(n),显然得到：,即:k=log2(n)+1,性质5:对于一棵有n个结点的完全二叉树，按照从上至下和从左至右的顺序对所有结点从1开始顺序编号。,当i=1时，该结点为根结点，它无双亲结点；,则对于序号为 i 的结点(1in),有：,当i1时，其双亲是结点i/2(“/”表示整除）；,若2in，则第i个结点有编号为2i的左孩子；,若2i+1n，则第i 个结点有编号为2i+1的右孩子,完全二叉树的结点可按从上到下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。下面两棵树在数组中的存储结构分别为：,二叉树的存储结构,二叉树的存储结构有多种，最常用的有两种：,顺序存储结构和链表存储结构,1.二叉树的顺序存储结构,满二叉树：,结点：i=5,父结点：i/2=5/2=2,左孩子：2i=2*5=10,右孩子：2i+1=2*5+1=11,完全二叉树：,对于一般的非完全二叉树,必须首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态。,然后再用顺序存储结构存储在一维数组中。,显然不能直接使用二叉树的顺序存储结构。,所以，顺序存储结构仅适于满二叉树或完全二叉树，一般二叉树更适宜用链表存储结构,二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树最常用的的链式表储结构是二叉链和三叉链。二叉链存储结构的每个结点包含三个域，分别是数据域data、左孩子指针域leftChild和右孩子指针域rightChild。二叉链存储结构中每个结点的图示结构为：,三叉链表的结点比前者多了一个指向双亲的指针域。,2.二叉树的链式存储结构,结点结构描为：,typedef struct node ElemType data;struct node*lch,*rch;Bnode;,typedef struct node ElemType data;struct node*lch,*par,*rch;/*par是双亲指针域*/Bnode3;,结点结构描为：,二叉链表,三叉链表,二叉树,二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。,二叉树的仿真二叉链存储结构,B,A,C,D,G,二叉树的仿真指针,6.2.5 二叉树二叉链表的一个生成算法,创建二叉树的方法有多种，并且算法都比较复杂，这里我们运用二叉树的性质5，学习一种较简单的生成算法。,对任意二叉树，首先按满二叉树的结构对其结点进行编号。,此树并非完全二叉树，因此结点编号不连续。算法中用一个辅助向量s存放树结点的指针。该向量的类型为：Bnode*sMAXSIZE,Bnode*creat()Bnode*t=NULL;printf(“n i,x=”);scanf(“%d%d”,/*creat end*/,typedef struct node ElemType data;struct node*lch,*rch;Bnode;,*s,ti的父结点：ti/2 左孩子：t2i 右孩子：t2i+1,6.3 二叉树遍历,遍历二叉树是指以一定的次序访问二叉树中的每个结点，并且每个结点仅访问一次。所谓访问结点是指对结点进行各种操作的简称。,遍历二叉树的过程实质上是把二叉树的结点进行线性排列的过程。假如访问结点的操作是输出结点数据域的值，那么遍历的结果就会得到一个线性序列。,由于二叉树有左、右子树，因此遍历的次序不同，得到的结果也就不同。,从二叉树的定义知，一棵二叉树由三部分组成：根结点、左子树和右子树。,则有三种不同的遍历次序：TLR-前序遍历（先根遍历）LTR-中序遍历（中根遍历）LRT-后序遍历（后根遍历）,若规定：T-代表访问根结点 L-代表遍历根结点的左子树 R-代表遍历根结点的右子树,T,L,R,遍历搜索示意图,图中二叉树有四个结点ABCD，为了便于理解遍历的思想，为每个没有子树的结点补上相应的空子树。,设想有一条搜索路线.，它从根结点的左侧开始，自上而下，自左至右搜索，最后从根结点的右侧向上出去。恰好搜索线途经每个有效树结点都是三次,搜索线第一次经过就访问的结点序列ABCD，称先根遍历；搜索线第二次经过才访问的结点序列BADC，称中根遍历；搜索线第三次经过才访问的序列BDCA,称后根遍历,A,B,C,D 先根（前序）遍历,B,A,D,C 中根（序）遍历,B,D,C,A 后根（序）遍历,二叉树选择不同的存储结构，遍历算法的程序代码会有所不同。这里确定用二叉链表作为存储结构，树中结点的结构定义为：,typedef struct node ElemType data;struct node*lch,*rch;Bnode;,若根为空则结束；否则：（1）访问根结点；（2）按先根次序遍历左子树；（3）按先根次序遍历右子树。,6.3.1 先根遍历,先根遍历（TLR）递归算法为：,若根为空则结束；否则：（1）访问根结点；（2）按先根次序遍历左子树；（3）按先根次序遍历右子树。,若根为空则结束；否则：（1）访问根结点；（2）按先根次序遍历左子树；（3）按先根次序遍历右子树。,Void preorder(Bnode*p)if(p!=NULL)printf(“%6c”,p-data);preorder(p-lch);preorder(p-rch);/*preorder*/,此处假设ElemType为char型,先根遍历递归调用示意图,若根为空则结束；否则：（1）按中根次序遍历左子树；（2）访问根结点；（3）按中根次序遍历右子树。,6.3.2 中根遍历,中根遍历（LTR）与先根遍历相似，只是在根不空时将算法的第一步与第二步次序对换而已，即：,Void inorder(Bnode*p)if(p!=NULL)inorder(p-lch);printf(“%6c”,p-data);inorder(p-rch);/*inorder*/,此处假设ElemType为char型,实现算法的代码也是在先根算法基础上稍做改动，即：,递归算法简练但执行效率较低，而且有些高级也不支持递归调用，作为程序设计能力的训练，有必要学习非递归算法。,中根遍历的非递归算法如下：,voide inorderz(Bnode*p)/*栈s是Bnode*s10*/q=p;top=0;/*栈顶指针*/bool=1;/*bool=1表示栈不空*/printf(“n 中根遍历：n”);do while(q!=NULL)top+;stop=q;q=q-lch;if(top=0)bool=0;else q=stop;top-;printf(“%6c”,q-data);/*访问根结点*/q=q-rch;while(bool);printf(“n”);/*inorderz*/,C,A,B,D,B,A,D,C,6.3.3 后根遍历,若根为空则结束；否则：（1）按后根次序遍历左子树；（2）按后根次序遍历右子树；（3）访问根结点。,Void postorder(Bnode*p)if(p!=NULL)postorder(p-lch);postorder(p-rch);printf(“%6c”,p-data);/*postorder*/,后根遍历的非递归算法较为复杂，它需要两个栈，第一个栈的用途与中根遍历相同，第二个栈用来经过某根结点的次数。两个栈的数据类型为：Bnode*s10;int s220;具体算法程序留给同学们课外阅读。（P111）,void levelorder(Bnode*p)Bnode*q20;front=0;rear=0;if(p!=NULL)rear+;qrear=p;/*根结点不空，进队*/while(front!=rear)front+;p=qfront;printf(“%6c”,p-data);/*出队并访问*/if(p-lch!=NULL)rear+;qrear=p-lch;/*若左孩子不空，进队*/if(p-rch!=NULL)rear+;qrear=p-rch;/*若左孩子不空，进队*/*levelorder*/,6.3.4 按层遍历二叉树,F,R,R,R,R,R,R,R,R,F,F,F,F,F,F,F,a,b,c,d,f,j,k,（1）初始化设置一个队列；（2）把根结点指针入队列；（3）当队列非空时，循环执行步骤（3.a）到步骤（3.c）（3.a）出队列取得一个结点指针，访问该结点；（3.b）若该结点的左子树非空，则将该结点的左子树指针入队列；（3.c）若该结点的右子树非空，则将该结点的右子树指针入队列；（4）结束。,按层遍历二叉树的算法可以用语言描述如下：,按层遍历二叉树被称为层序遍历。层序遍历的要求是：按二叉树的层序次序（即从根结点层至叶结点层），同一层中按先左子树再右子树的次序遍历二叉树。,可以借助队列实现二叉树的层序遍历。,它的特点是，在所有未被访问结点的集合中，排列在已访问结点集合中最前面结点的左孩子将最先被访问，然后是该结点的右孩子。这样，如果把已访问的结点放在一个队列中，那么，所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此,把二叉树逆时针旋转900C，按照二叉树的凹入表示法打印二叉树。可把此函数设计成递归函数。由于把二叉树逆时针旋转900C后，在屏幕上方的首先是右子树，然后是根结点，最后是左子树，所以打印二叉树算法是一种特殊的中序遍历算法。,6.3.5 二叉树遍历的应用,1 打印二叉树,void PrintBiTree(Bnode*bt,int n)int i;if(bt=NULL)return;PrintBiTree(bt-rightChild,n+1);for(i=0;i 0)printf(-);printf(%cn,bt-data);PrintBiTree(bt-leftChild,n+1);,在二叉树中查找数据元素操作的要求是：在bt为根结点指针的二叉树中查找数据元素x，若查找到数据元素x时返回该结点的指针；若查找不到数据元素x时返回空指针。在二叉树bt中查找数据元素x算法可设计成先序遍历算法，此时查找结点的次序是：首先在根结点查找，然后在左子树查找，最后在右子树查找。但是，和常规递归算法不同的是，此算法当一个分支上的结点比较完仍未查找到数据元素x时，要返回到该结点的双亲结点处继续查找。因此，此算法是一个回溯算法。,2 查找数据元素,BiTreeNode*Search(Bnode*bt,ElemType x)BiTreeNode*p;if(bt=NULL)return NULL;if(bt-data=x)return bt;if(bt-leftChild!=NULL)p=Search(bt-leftChild,x);if(p!=NULL)return p;if(bt-rightChild!=NULL)p=Search(bt-rightChild,x);if(p!=NULL)return p;return NULL;,6.4 线索二叉树,线索二叉树是另一种分步遍历二叉树的方法。它既可以从前向后分步遍历二叉树，又可以从后向前分步遍历二叉树。,当按某种规则遍历二叉树时，保存遍历时得到的结点的后继结点信息和前驱结点信息的最常用的方法是建立线索二叉树。,对二叉链表存储结构的二叉树分析可知，在有n个结点的二叉树中必定存在n+1个空链域。,先根遍历：A,B,C,D,中根遍历：B,A,D,C,后根遍历：B,D,C,A,6.4.1 线索二叉树的基本概念,规定：当某结点的左指针为空时，令该指针指向按某种方法遍历二叉树后得到的线性序列中该结点所处位置的前驱结点；当某结点的右指针为空时，令该指针指向按某种方法遍历二叉树后所得线性序列中该结点所处位置的后继结点。仅仅这样做会使我们不能区分左指针指向的结点到底是左孩子结点还是前驱结点，右指针指向的结点到底是右孩子结点还是后继结点。因此我们需要在结点中增加两个线索标志位来区分这两种情况。线索标志位定义如下：,每个结点的结构：,结点中指向前驱结点和后继结点的指针称为线索。在二叉树的结点上加上线索的二叉树称作线索二叉树。对二叉树以某种方法（如前序、中序或后序方法）遍历使其变为线索二叉树的过程称作按该方法对二叉树进行的线索化。,typedef struct node ElemType data;struct node*lch,*rch;int ltag,rtag;Btnode;,先根遍历：A,B,C,D,中根遍历：B,A,D,C,后根遍历：B,D,C,A,6.4.1 线索二叉树的逻辑表示图,按照不同的遍历次序进行线索化,可得到不同的线索二叉树。有：,要求同学们能熟练掌握三种不同线索二叉树逻辑图的画法。注意线索要用带箭头的虚线，从线点的左下方或右下方出发，左右分明，指向准确。,线索二叉树,一旦建立了某种方式的线索二叉树后，用户程序就可以像操作双向链表一样操作该线索二叉树。,