第5章二叉树与树.ppt
《第5章二叉树与树.ppt》由会员分享,可在线阅读,更多相关《第5章二叉树与树.ppt(77页珍藏版)》请在三一文库上搜索。
1、第五章 二 叉 树与树,树形结构是一种十分重要的数据结构。本章讨论的二叉树、树和树林都属于树形结构。 在树形结构中每个结点最多只有一个前驱,但可有多个后继的结构。 它们的共同之处是都表示了一种具有层次的分支关系。,5.1 二叉树及其抽象数据类型 5.1.1基本概念,二叉树可以定义为结点的有限集合,这个集合或者为空集,或者由一个根及两棵不相交的分别称作这个根的左子树和右子树的二叉树组成。 二叉树的定义是个递归定义。二叉树可以是个空集合,这时的二叉树称为空二叉树。二叉树也可以是只有一个结点的集合,这个结点只能是根;它的左子树和右子树均是空二叉树。 二叉树描述的是一种层次关系,除了根节点外其余节点都
2、有且只有一个前驱节点,所有节点可以有0到两个后继节点。 二叉树的五种基本形态,二叉树的相关术语,父结点、左(右)子结点、边:若节点x是根节点,y是x的左(右)子树的根,则称x是y的父节点,y是x的左(右)子节点,有序对称作x到y的边。 兄弟:具有同一个父节点的节点彼此称为兄弟。 祖先、子孙:若节点y在以节点x为根的左(右)子树中,且xy,则称x是y的祖先,y是x的子孙。 路径、路径长度: 如果x是y的祖先,又有x=x0,x1,xn=y满足xi为xi+1的父节点,称x0,x1,xn为从x到y的一条路径,n称为路径长度。 结点的层数:根的层数为1,其余节点的层数等于其父节点的措施加1。 结点的度数
3、:节点的非空子树的个数称作节点的度数。二叉树中节点的最大度数为2。 二叉树的高度:二叉树中结点的最大层数称为二叉树的高度。 树叶、分支结点:左(右)子树均为空二叉树的节点称作树叶;否则称为分支节点。,特殊的二叉树,满二叉树:如果一棵二叉树的任何结点或者是树叶,或有两棵非空子树,则此二叉树称作满二叉树(离散数学中称此树是正则的)。 完全二叉树:如果一棵二叉树至多只有最下面的两层结点度数可以小于2,其余各层结点度数都必须为2,并且最下面一层的结点都集中在该层最左边的若干位置上,则此二叉树称为完全二叉树。 完全二叉树不一定是满二叉树。满二叉树不一定是完全二叉树。,扩充的二叉树:把原二叉树的结点都变为
4、度数为2的分支结点,也就是说,如果原结点的度数为2,则不变,度数为1,则增加一个分支,度数为0(树叶),则增加两个分支。 新增加的结点(树叶结点)都用小方框表示,称为外部结点,树中原有的结点称为内部结点。 由非空二叉树扩充的二叉树都是满二叉树。 把空二叉树扩充得到的扩充二叉树规定为只有一个外部结点组成的二叉树。,在扩充的二叉树中,外部路径长度E定义为在扩充的二叉树中从根到每个外部结点的路径长度之和。内部路径长度I定义为在扩充的二叉树中从根到每个内部结点的路径长度之和。 如在图的扩充二叉树中: E =2+2+4+4+3+3+3= 21 I = 0+1+1+2+2+3 = 9,5.1.2 主要性质
5、,性质1 在非空二叉树的i层上至多有2i个结点(i0)。 证明:用归纳法来证。 性质2 高度为k的二叉树中最多有2k+1 - 1个结点(k0)。 证明:假设第i层上的最大结点个数是mi,由性质1可知,深度为k的二叉树中最大结点个数M为:,性质3 对于任何一棵非空的二叉树,如果叶结点个数为n0,度为2的结点个数为n2,则有:n0= n2 + 1 。 证明:设一棵非空二叉树中有n个结点,度为1的结点个数为n1,因为二叉树中所有结点的度均不大于2,所以 n = n0 + n1 + n2 (1) 在二叉树中,除根结点外,其余每个结点都有一个分支进入,假设B为分支总数,则有 B = n 1 (2) 又由
6、于二叉树中的分支都是由度为1和2的结点发出,所以有 B = n1 + 2n2 (3) 综合(1)、(2)、(3)式可得 n0 = n2 + 1。 性质4 具有n个结点的完全二叉树的深度k为 。 证明:根据性质2和完全二叉树的定义可知 2k - 1 n 2k+1 1 即:2k n 2k+1 对不等式取对数有:k k + 1 由于k为整数,所以有 k =,性质5 对于具有n个结点的完全二叉树,如果按照从上(根结点)到下(叶结点)和从左到右的顺序对二叉树中的所有结点从0开始到n-1进行编号,则对于任意的下标为i的结点,有: 如果i=0,则它是根结点,它没有父结点:如果i0,则它的父结点的下标为(i-
7、1)/2; 如果2i1n1,则下标为i的结点的左子结点的下标为2i1;否则,下标为i的结点没有左子结点: 如果2i+2n1,则下标为i的结点的右子结点的下标为2i+2;否则,下标为i的结点没有右子结点。 性质6 在满二叉树中,叶结点的个数比分支结点个数多1。 性质7 扩充二叉树中,外部结点的个数比内部结点的个数多1。 性质8 对任意扩充二叉树,外部路径长度E和内部路径长度I之间满足以下关系:E = I + 2n,其中n是内部结点个数。,5.1.3 二叉树的抽象数据类型,ADT BinTree is operations BinTree createEmptyBinTree(void) 创建一棵
8、空的二叉树。 BinTree consBinTree(BinTreeNode root, BinTree left, BinTree right) 返回一棵二叉树,其根结点是root,左右二叉树分别为left和right。 int isNull ( BinTree t ) 判断二叉树t是否为空。 BinTreeNode root ( BinTree t ) 返回二叉树t的根结点。若为空二叉树,则返回一特殊值。,BinTreeNode parent (BinTree t , BinTreeNode p ) 返回结点p的父结点。当指定的结点为根时,返回一个特殊值。 BinTree leftChil
9、d ( BinTree t , BinTreeNode p ) 返回p结点的左子树,当指定结点没有左子树时,返回一个特殊值。 BinTree rightChild ( BinTree t , BinTreeNode p) 返回p结点的右子树,当指定结点没有右子树时,返回一个特殊值。 end ADT BinTree 此外作为抽象数据类型,二叉树还应该有插入、删除和检索节点等运算,由于于本章关系不大,故省略。 由于二叉树的概念是递归定义的,二叉树中的每个结点也可标识以这个结点为根的二叉树,所以二叉树类型和二叉树中结点类型在具体实现时常常看成是同一种类型。,5.2 二叉树的周游 5.2.1什么是周游
10、,二叉树的周游(二叉树的遍历)是指按某种方式访问二叉树中的所有结点,使每个结点被访问一次且只被访问一次。 深度优先周游(深度优先遍历) 广度优先周游(广度优先遍历),5.2.2 周游的分类,深度优先周游 若以符号D、L、R分别表示根结点、左子树、右子树,则二叉树的周游共有六种方式:DLR,LDR,LRD,DRL,RDL和RLD。如果限定先左后右,则只能采用前三种周游方式,即DLR,LRD和LDR,它们分别被称为先根次序(简称先序或前序)周游、后根次序(简称后序)周游和中根次序(简称中序)周游(也叫对称序次序周游)。,先根次序:若二叉树不空,则先访问根;然后按先根次序周游左子树;最后按先根次序周
11、游右子树。 如图所示二叉树,结点序列为:A,B,D,C,E,G,F,H,I 将按先根次序周游二叉树得到的线性表称为该二叉树的先根序列。 后根次序:若二叉树不空,则先按后根次序周游左子树;然后按后根次序周游右子树;最后访问根。 如图所示二叉树,结点序列为:D,B,G,E,H,I,F,C,A 将按后根次序周游二叉树得到的线性表称为该二叉树的后根序列。,中根次序:若二叉树不空,则先按中根次序周游左子树;然后访问根;最后按中根次序周游右子树。 如图所示二叉树,结点序列为:D,B,A,E,G,C,H,F,I 将按中根次序周游二叉树得到的线性表称为该二叉树的中根序列。,对于给定的二叉树,可以唯一确定它的先
12、根序列、后根序列和中根序列。但是反过来,给定一个二叉树的任意一种周游的序列,无法唯一确定这个二叉树。 一般而言,如果已知一个二叉树的中根序列,又知道另外一种周游序列(无论是先根序列还是后根序列),就可以唯一确定这个二叉树。 广度优先周游 若二叉树的高度为h,则从0到h逐层如下处理:从左到右逐个访问存在的结点。 前图的二叉树,广度优先周游所得到的结点序列为:A,B,C,D,E,F,G,H,I 广度优先周游一棵二叉树所得到的结点序列,叫作这棵二叉树的层次序列。,5.2.3 一个例子,对于二叉树不同的周游策略,所得到的不同线性序列,常常具有不同的实际意义。 如图是算术表达式(a-b)(c+d)的一种
13、语法结构图。由于二叉树本身的层次已经可以定义计算的次序,所以原表达式中的括号就不需要了。 先根序列(前缀表达式): a b c d 后根序列(后缀表达式):a b c d 中根序列(中缀表达式) :a b c d,中缀表达式中计算的次序与运算符的优先级可能产生冲突,所以需要把每个子树的中根序列用括号括起来。但前缀表达式、后缀表达式不需要。如前所述,中缀可转换为后缀。 广度优先周游的层次序列没有什么实际意义。,5.2.4 周游的抽象算法,利用二叉树抽象数据类型中的定义,可以方便地写出二叉树的周游算法。 这里给出的算法,都是建立在上节关于抽象数据类型基本运算的基础上。它们不依赖于二叉树的具体存储结
14、构,所以称为抽象算法。,深度优先递归算法,三种深度优先周游的递归算法:,先根次序周游: void preOrder( BinTree t) 中根次序周游: void inOrder(BinTree t) 后根次序周游: void postOrder(BinTree t) 注意是抽象算法,需要根据二叉树的实现方式进行修改。,深度优先非递归算法,利用栈的帮助,可以写出各种深度优先周游的非递归算法。由于本节给出的算法,基本都不涉及具体的存储结构,所以对于栈或者队列的使用,算法中也不依赖于具体的表示方式。 先根次序周游非递归 中根次序周游非递归 后根次序周游非递归,先根次序周游非递归,采用非递归算法实
15、现先根次序周游二叉树的主要思路是:首先把根结点压入栈中;然后从栈顶中取出元素(包括退栈),只要取出元素非空,就访问该结点,然后顺序将其右子结点和左子结点进栈,重复执行上述过程,直到当从栈顶中取出的元素(包括退栈)为空,并且栈也为空时,周游结束。 程序实现:void nPreOrder(BinTree t)。注意是抽象算法,需要根据二叉树的实现方式进行修改。 算法中每个二叉树恰好进栈、出栈各一次,所以它的时间代价为O(n),其中n为二叉树中子二叉树(也是结点)的个数。,采用非递归算法实现中根次序周游二叉树的主要思路是:若二叉树不为空时,则沿其左子树前进,在前进过程中,把所经过的二叉树逐个压入栈中
16、,当左子树为空时,弹出栈顶元素,并访问该二叉树的根,如果它有右子树,再进入当前二叉树的右子树,从头执行上述过程;如果它没有右子树,则弹出栈顶元素,从前面继续执行。直到当前二叉树为空并且栈也为空时,周游结束。 程序实现:void nInOrder(BinTree t)。注意是抽象算法,需要根据二叉树的实现方式进行修改。 算法中每个二叉树恰好进栈、出栈各一次,所以它的时间代价为O(n)。,中根次序周游非递归,采用非递归算法实现中根次序周游二叉树的主要思路与中根周游有些类似:若二叉树不为空时,则沿其左子树前进,在前进过程中,把所经过的二叉树逐个压入栈中,当左子树为空时,将右子树重复上述过程,直到左、
17、右子树都为空时弹出栈顶元素,并访问该二叉树的根。如果该二叉树是左子树,进入作为其兄弟的右子树,从头执行上述过程;如果该二叉树是右子树,则弹出栈顶元素,从前面继续执行。直到当前二叉树为空并且栈也为空时,周游结束。 程序实现:void nPostOrder2(BinTree t)。注意是抽象算法,需要根据二叉树的实现方式进行修改。 算法中每个二叉树恰好进栈、出栈各一次,所以它的时间代价为O(n)。,后根次序周游非递归,根据广度优先周游的思想不难想到,可以利用一个队列实现其算法:首先把二叉树送入队列;其后,每当从队首取出一个二叉树访问之后,马上把它的子二叉树按从左到右的次序送入队列尾端;重复此过程直
18、到队列为空。 程序实现:void levelOrder(BinTree t)。注意是抽象算法,需要根据二叉树的实现方式进行修改。 每个二叉树进队列一次出队列一次,所以时间代价为O(n)。主要空间代价是需要队列的附加空间。若二叉树结点个数为n,最坏的情况出现在完全二叉树时,需要大约n/2个队列元素的空间。,广度优先周游非递归,5.3 二叉树的实现,顺序表示 链接表示 线索二叉树,5.3.1 顺序表示,二叉树的顺序表示,也是采用一组连续的存储单元来存放二叉树中的结点,但是,由于二叉树是非线性结构,所以结点之间的逻辑关系难以从存储的先后确定。不过,由二叉树的性质5可知,对于完全二叉树,如果按照从上(
19、根结点)到下(叶结点)和从左到右的顺序,对二叉树中的所有结点从0到n-1编号,这样存放到一维数组中。只要通过数组元素的下标关系,就可以确定二叉树中结点之间的逻辑关系。,对于一般的二叉树,如果仍采用顺序表示,首先要对它进行扩充,增加一些并不存在的空结点,使之成为一棵完全二叉树,然后再用一维数组顺序存储。在二叉树中人为增加的空结点,在数组所对应的元素中,可以用一个特殊值表示。,采用顺序存储表示的二叉树,可用下列方式定义: struct SeqBinTree / 顺序二叉树类型定义 int MAXNUM /完全二叉树中允许结点的最大个数 int n; / 改造成完全二叉树后,结点的实际个数 Data
20、Type *nodelist; /存放结点的数组 ; typedef struct SeqBinTree *PSeqBinTree; /顺序二叉树类型的指针 nodelist数组中的每个元素表示二叉树中的一个结点,以这个结点为根的子二叉树的根就是它自己,它的左子树以nodelist2*i+1为根,它的右子树以nodelist2*(i+1)为根,它的父结点则是nodelist(i-1)/2(前提是这些结点存在)。 n是扩充成完全二叉树以后结点的实际个数。当二叉树为空二叉树时,n=0。 MAXNUM是完全二叉树中允许结点的最大个数,它可以作为数组空间的大小参数提供给二叉树的创建函数使用,也可以在数
21、组溢出时,通过程序扩充空间。,运算的实现,返回下标为p的结点的父结点的下标 int parent_seq(PSeqBinTree t, int p) 返回下标为p的结点的左子结点的下标 int leftChild_seq(PSeqBinTree t, int p) 返回下标为p的结点的右子结点的下标 int rightChild_seq (PSeqBinTree t, int p) 顺序表示法对完全二叉树比较适合,既可以节省存储空间,又可以利用数组元素的下标确定节点在二叉树中的位置以及节点间的关系。,5.3.2 链接表示,二叉树的链接表示是用一个链表来存储一棵二叉树,二叉树中的每个结点对应链表
22、中的一个结点。由于二叉树是非线性结构,每个结点最多有两个后继,所以最常用的链接表示方式是左-右指针表示法,这种表示法在每个结点中,除了存储结点本身的数据外,再设置两个指针字段:llink和rlink,分别存放结点的左子结点和右子结点的位置,当结点的某个子树为空时,则相应的指针为空指针。,struct BinTreeNode; / 二叉树中结点 typedef struct BinTreeNode * PBinTreeNode; /结点的指针类型 struct BinTreeNode DataType info; / 数据域 PBinTreeNode llink; / 指向左子结点 PBinTr
23、eeNode rlink; / 指向右子结点 ; 由于递归是二叉树的固有特性,二叉树的许多处理都可以用递归算法来描述,因此,为了运算和参数传递的方便,不再对二叉树进行封装,直接将二叉树定义为指向结点的指针类型: typedef struct BinTreeNode *BinTree; 在实际应用中,将二叉树作为参数传递时,可能需要传递二叉树根结点指针的地址(避免被调用函数中修改根节点位置)。因此,为了说明方便,可以引入二叉树类型的指针类型: typedef BinTree *PBinTree;,运算的实现,返回结点p的左子结点的地址 PBinTreeNode leftChild_link(PB
24、inTreeNode p) 返回结点p的右子结点的地址 PBinTreeNode rightChild_link(PBinTreeNode p) 求父节点的操作就比较困难,只能从根节点出发,使用前面的周游算法,跳过算法中的访问函数(visit),检查当前节点是否是所求节点的父节点。最坏的时间代价与周游整个二叉树的代价相同。 为了提高求父结点操作的速度,可以采用的另一种链接表示方式是三叉链表表示,即给二叉树中的每个结点增加一个指向父结点的指针域。采用三叉链表表示,既便于查找子结点,又便于查找父结点,但是相对于左右指针表示而言,它增加了空间开销。,5.3.3 线索二叉树,周游是二叉树中许多操作的基
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉
链接地址:https://www.31doc.com/p-2909794.html