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

1,第6章 二叉树和树,2,【重点掌握】： 1. 二叉树的结构特性; 2. 二叉树的各种存储结构的特点及适用范围; 3. 二叉树各种遍历策略的递归算法，且能灵活运用遍历算法实现二叉树的其它操作； 4. 最优二叉树的特性，建立最优树和哈夫曼编码的方法。 【掌 握】： 1. 线索二叉树的建立、使用； 2. 树的各种存储结构及其特点； 3. 树、森林与二叉树之间的转换； 4. 树、森林的遍历。,3,线性结构的特点是逻辑结构简单，易于进行查找、删除、插入等操作。其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。 非线性结构是指在该结构中至少存在一个数据元素有两个或两个以上的直接前驱或直接后继。 树形结构是一类重要的非线性结构。树形结构是结点之间有分支、并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。 图形结构是十分重要的非线性结构，可以用来描述客观世界中广泛存在的网状结构的关系。,4,6.1 二叉树 6.1.2 二叉树的基本概念 1.二叉树(Binary Tree) (1)定义：二叉树是n（n=0）个数据元素的集合，该集合或为空，或含有唯一的称为根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为左子树和右子树。,说明: 1）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念 2）二叉树中每个结点最多有两棵子树,二叉树每个结点度小于等于2,5,3）左、右子树不能颠例 二叉树结点的子树要区分左子树和右子树：即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。,(2) 二叉树的 5 种基本形态,6,2. 二叉树的基本术语 1) 孩子(child)：结点的子树的根称为该结点的孩子；左孩子，右孩子。 2) 双亲(parents)：孩子结点的上层结点。 3) 兄弟(sibling)：同一双亲的孩子结点；堂兄弟、祖先结点、子孙结点 4) 叶子(leaf)：终端结点，左右子树均为空的结点；反之，分支结点。 5) 结点的度(degree)：结点拥有的子树数。 6) 二叉树的度： 树中最大的结点度。 7) 结点层(level)：从根结点开始算起，根为第一层；根的孩子为第2层结点； 8）二叉树的深度(depth)：二叉树中叶子结点的最大层次数。,7,二叉树的基本性质 性质1：一棵非空二叉树的第i层上最多有2i-1个结点（i1）。,8,性质2：一棵深度为k的二叉树中，最多有2k-1个结点（k1)。 深度为k的二叉树取最多结点时，二叉树中的每层上均应取最多结点。根据性质1得到每层上的最大结点数为2i-1，则二叉树中的总结点数为：20 + 2 1+ 2 k-1 = 2k-1。,此树的深度k=4，共有24-1=15个结点,9,性质3：对于非空二叉树，如果叶子结点数为n0，度为2的结点数为n2，则有n0=n2+1。 证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有： Nn0n1n2 (6-1) 再看二叉树中的分支数，除根结点外，其余结点都由一个分支与其双亲相连接，设B为二叉树中的分支总数，则有： NB1 （6-2) 由于这些分支都是由度为1和2的结点射出的，所以有： Bn1+2*n2 （6-3) 即：NB1n12n21 由式（6-1）得到：n0+n1+n2=n1+2*n2+1 即：n0n21,n0=3 n2=2,10, 两种特殊的二叉树 (1) 满二叉树：如果深度为k的二叉树有2k-1个结点，则称为满二叉树。 特点：每一层上都含有最大结点数。,k=4的满二叉树,11,（2）完全二叉树：如果二叉树除最后一层外每一层都是满的，且最后一层或者是满的，或者结点都连续地集中在该层的最左端，则称其为完全二叉树。,特点：1)所有的叶子结点都出现在第k层或k-1层; 2)对任一结点，如果其右子树的最大层次为L，则其左子树的最 大层次为L或L+1。,12,非完全二叉树,满二叉树（完全二叉树),完全二叉树,非完全二叉树,13,性质4：具有n个结点的完全二叉树的深度为： log2n+1。（符号x 表示不大于x的最大整数）,n2k-1,n2k-1,2k-1n2k-1 取对数得到：k-1log2nk 因为k是整数，所以k= log2n1。,假设此二叉树的深度为k:,14,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第log2n+1层，每层从左到右),则对任一结点i（1in) ： （1）如果i1，则结点i是二叉树的根,无双亲；如果i1，则其双亲是结点i/2 ； （2）如果2in，则其左孩子是结点2i；否则i无左孩子、为叶子结点； （3）如果2i+1n，则其右孩子是结点2i1；否则结点i无右孩子。,A,B,C,D,E,F,G,1,2,3,4,5,6,8,D,7,15,6.2 二叉树的存储结构 1. 顺序存储结构 所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树的结点。一般是按照从上至下、从左至右的顺序存储。但是，这样存储后结点在存储位置上的前驱、后继关系并不一定就是它们在逻辑上的邻接关系，只有通过一些方法能够确定结点在逻辑上的前驱和后继结点，这种存储才有意义。 (1)完全二叉树的顺序存储 完全二叉树按照这种编号方式时，所有结点编号时连续的；依据二叉树的性质5，树中结点的序号可以惟一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置以及结点之间的关系。所以比较适合于采用顺序存储方式。,16,若父结点在数组中 i 下标处，其左孩子在2*i处，右孩子在2*i+1处；结点i的双亲是 i/2。,例如下完全二叉树：,17,(2)一般二叉树的顺序存储 对于一般二叉树，如果仍按从上至下、从左至右的顺序将树中的结点顺序地存储在一维数组中可，则数组元素下标之间的关系不能反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使其成为一棵完全二叉树，再用一维数组存储。, 表示该处没有元素存在,18,这种存储方式对于需增加结点才能将一棵二叉树改造成一棵完全二叉树的存储时,会造成空间的大量浪费，不宜采取顺序结构。最坏的情况是单支树。,19,2.链式存储结构 用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 （1）二叉链表 链表中每个结点包含三个域，除数据域外，还有两个指针域，分别用来给出该结点的左孩子和右孩子所在的结点的存储地址。 结点的存储结构为：,结点存储结构的描述： typedef struct BiTNode datatype data; struct BiTNode *lchild,*rchild; BiTNode, *BiTree;,20,在n个结点的二叉链表中，有n+1个空指针域。,21,(2) 三叉链表存储结构 三叉链表中每个结点由4个域组成：数据域、双亲指针域、左指针域、右指针域。,parent域为指向该结点双亲结点的指针。 这种结构既便于查找孩子结点，又便于查找双亲结点；但是，相对二叉链表而言它增加了空间开销。 尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。,22,三叉链表示意图,23,6.2 二叉树的遍历 6.2.1 二叉树的遍历算法及递归实现 遍历：按某种搜索路径访问二叉树的每个结点，使每个结点被访问一次且仅被访问一次。 遍历是二叉树经常要用到的一种操作。因为在实际应用问题中，常要按一定次序对二叉树中的每个结点做逐一访问，或查找具有某个特点的结点，然后对这些满足条件的结点进行处理。遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。 访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。,24,由二叉树的定义可知，一棵二叉树是由根结点、根结点的左子树、根结点的右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树。,令：L：遍历左子树 D：访问根结点 R：遍历右子树 有六种遍历方法： DLR，LDR，LRD， DRL，RDL，RLD,约定先左后右,有三种遍历方法： DLR、LDR、LRD ，分别称为先序遍历、中序遍历、后序遍历。,25,1.先序遍历（DLR） 若二叉树空，遍历结束。否则， （1）访问根结点； （2）先序遍历根结点的左子树； （3）先序遍历根结点的右子树；,先序遍历序列为：A, B ,D ,E, G, C ,F,例：先序遍历右图所示的二叉树 （1）访问根结点A （2）先序遍历A的左子树：即按DLR顺序遍历A的左子树 （3）先序遍历A的右子树：即按DLR顺序遍历A的右子树,26,D L R,先序遍历序列：A B D C,先序遍历过程示例:,27,void PreOrder(BiTree T) /采用二叉链表结构，visit( )是访问结点的函数 if (T) /若T=NULL时,递归调用结束 visit(T)； /访问根结点 PreOrder(T-lchild); /先序遍历左子树 PreOrder(T-rchild); /先序遍历右子树 ,先序遍历递归算法,对于根结点，最简单的“访问”是输出处理。,28,例.求二叉树中的叶子结点数,分析： 需要对二叉树中的每个结点都进行判断 借用遍历算法（如：先序遍历算法） 方法：当访问到某个结点时，进行是否是叶子结点的判断； 如果是叶子结点，则将计数器加1,看先序遍历算法,29, 应用遍历算法求二叉树中的叶子结点数,void PreOder (BiTree T) /*先序遍历*/ if (T) Visit(T)； PreOrder(T-lchild); PreOrder(T-rchild); ,本算法中的访问是什么？, 判断T是否为叶子结点,T-lchilid=NULL ,30,void PreOder (BiTree T) /*先序遍历*/ if (T) Visit(T)； PreOrder(T-lchild); PreOrder(T-rchild); ,void PreOder (BiTree T) if (T) if (T-lchilid=NULL ,可以为函数换个名字（见名知义）,31,void Countleaf(BiTree T) if (T) if (T-lchild=NULL /*统计右子树中的叶子*/ ,调用前N的初值为0,注意：N需要在递归调用的各个子函数中有效，所以N必须是全局变量,32,void Countleaf(BiTree T) if (T) if (T-lchild=NULL /*统计右子树中的叶子*/ ,int N=0; main() BiTree T; /*建立二叉链表结构*/ Countleaf(T); printf(“the numbers of leaf: %d n”, N); ,33,2.中序遍历（LDR） 若二叉树为空，遍历结束。否则，（1）中序遍历根结点的左子树（2）访问根结点 （3）中序遍历根结点的右子树,中序遍历序列：D,B,G,E,A,C,F,例：中序遍历右图所示的二叉树： （1）中序遍历A的左子树：即按LDR的顺序遍历A的左子树 （2）访问根结点A （3）中序遍历A的右子树：即按LDR的顺序遍历A的右子树,问题：如何确定中序遍历过程中的第一个结点? 从根结点向左子树查找，第一个左子树为空的结点。,34,void InOrder (BiTree T) if (T=NULL) return; /*递归遍历结束*/ InOrder(T-lchild); /*中序遍历T的左子树*/ Visit(T-data)； /*访问根结点*/ InOrder(T-rchild); /*中序遍历T的右子树*/,中序遍历递归算法：,35,L D R,中序遍历序列：B D A C,中序遍历过程示例:,36,3.后序遍历（LRD） 若二叉树为空，则遍历结束。否则，（1）后序遍历根结点的左子树（2）后序遍历根结点的右子树 （3）访问根结点,后序遍历序列： G,D,B,E,F,C,A,例：后序遍历右图所示的二叉树 （1）后序遍历A的左子树：即按LRD的顺序遍历A的左子树 （2）后序遍历A的右子树：即按LRD的顺序遍历A的右子树 （3）访问根结点A,问题：如何确定后序遍历过程中的第一个结点? 从根结点向左子树查找，找到第一个左子树为空的结点，接着向右子树找，至一叶子结点。,37,void PostOrder(BiTree T) if(T=NULL) return; PostOrder(T-lchild); PostOrder(T-rchild); Visit(T-data); ,后序遍历递归算法：,38,L R D,后序遍历序列： D B C A,后序遍历过程示例:,39,6.2.2 由遍历序列恢复二叉树 任意一棵二叉树结点的先序序列和中序序列都是惟一的。反过来，若已知结点的先序序列和中序序列，也能惟一地确定这棵二叉树。, 在先序序列中，第一个结点一定是二叉树的根结点 中序序列必然以根为界分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列 在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列中的第一个结点是右子树的根结点 左子树和右子树的根结点又在中序序列中分别把左子序列和右子序列划分成两个子序列 ，如此递归下去，当取尽先序序列中的结点时，便可以得到一棵二叉树。,先序序列,中序序列,左子树,左子树,右子树,右子树,根,根,40,例：已知一棵二叉树的先序序列和中序序列分别为: 先序序列：ABCDEFGHI 中序序列：BCAEDGHFI 试恢复该二叉树。,41,分析： 需要建立二叉树中的所有结点 借用遍历算法 问题1：使用哪种遍历算法？ 先序遍历算法 问题2：“访问”所对应的运算是什么？ 建立该结点（分配存储空间），对其赋值。,【例1】 建立二叉树的存储结构 - 二叉链表,6.2.3 遍历算法的应用,42,方法： 输入先序序列（在空子树处添加字符#），按先序遍历的顺序，在遍历过程中建立二叉链表的所有结点并完成相应结点的链接。,输入序列： A B D # F # # C E # # #,43,BiTree CreatBiTree(BiTree /构造右子树 ,输入序列：A B # D # # C # #,44,分析： 通常，一个表达式由一个运算符和两个操作数构成。 即，表达式 = (第一操作数) (运算符) (第二操作数) 其中，操作数本身也可以是表达式 其结构类似于二叉树，因此可以用二叉树表示表达式（递归） 运算符：根结点； 第一操作数：L； 第二操作数：R 表达式求值过程：后序遍历表达式二叉树,【例2】 求存于二叉树中算数表达式的值,45,6.2.4 线索二叉树,遍历具有重要性 遍历存在的问题（建立线索二叉树的必要性） (1) 遍历将二叉树中所有结点排成一个线性序列，但每个结点在这个序列中的前驱和后继结点并没有直接在二叉树的存储结构中反映出来；只能在对二叉树遍历的动态过程中得到这些信息。 (2) 用递归的方式、利用栈或队列对二叉树遍历，都会存在栈或队列的额外空间的消耗。, 为了提高遍历的效率，保存结点在某种遍历序列中的前驱和后继的位置信息，利用二叉树的二叉链表存储结构建立线索二叉树。,46,线索二叉树的定义 （1）前驱和后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为前驱和后继。 （2）线索：指向前驱或后继结点的指针。 （3）线索二叉树：加上线索的二叉链表表示的二叉树。 （4）线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程。,47,方法：在线索二叉树的结点中增加两个域。,48,在线索二叉链表上增加头结点,目的：为了将二叉树中的所有空指针域都利用上，以及操作便利的需要，在存储线索二叉树时往往增设一头结点，其结构与其他线索二叉树的结点结构相同，只是其数据域不存储信息。,