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

,第六章 树和二叉树,第六章 树和二叉树6.1 树的有关概念6.2 二叉树6.3 二叉树的遍历6.4 遍历的应用6.5 * 线索二叉树（简单介绍）6.6 树和森林6.7 哈夫曼树及应用,第六章 树和二叉树,6.1 树的有关概念,1树的定义,定义：树是n个结点的有限集合。在任一棵非空树中： （1）有且仅有一个称为根的结点；。 （2）其余结点可分为m个互不相交的有限集合，而且这些集合中的每一集合本身又是一棵树，称为根的子树。,树是递归结构，在树的定义中又用到了树的概念,树结构 （除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。,6.1 树的有关概念,从逻辑结构看： 1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构,6.1 树的有关概念,2树的应用1）树可表示具有分枝结构关系的对象,例1家族族谱,例2单位行政机构的组织关系、系统功能模块图,6.1 树的有关概念,2）树是常用的数据组织形式 有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3 计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。,6.1 树的有关概念,3 、树的基本术语,1）结点的度：结点所拥有的子树的个数。2）树的度：树中各结点度的最大值。,DA=3,DB=2,DC=1,DG=0,DTree=3,6.1 树的有关概念,3）叶子结点：度为0的结点，也称为终端结点。4）分支结点：度不为0的结点，也称为非终端结点。,叶子结点：K,L,F,G,M,I,J,分支结点：A,B,C,D,E,H,6.1 树的有关概念,5）孩子、双亲：树中结点的子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；6）兄弟：具有同一个双亲的孩子结点互称为兄弟。,孩子结点：B,C,D双亲结点：A兄弟结点：E，F,6.1 树的有关概念,7）路径：如果树的结点序列n1, n2, , nk有如下关系：结点ni是ni+1的双亲，则把n1, n2, , nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。,结点序列：nA,nB, nE, nK路经长度=3,6.1 树的有关概念,8）祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。,6.1 树的有关概念,9）结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。10）树的深度：树中所有结点的最大层数，也称高度。,6.1 树的有关概念,11）有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的（即不能互换），称这棵树为有序树；反之，称为无序树。,数据结构中讨论的一般都是有序树,6.1 树的有关概念,12）森林：m (m0)棵互不相交的树的集合。,树中每一个结点的子树的集合即为森林。,6.1 树的有关概念,树结构和线性结构的比较,线性结构,树结构,无前驱,无双亲,无后继,无孩子,一个前驱,一个后继,一个双亲,多个孩子,一对一 一对多,6.1 树的有关概念,4、树的基本操作 树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作： 1）InitTree( /返回树T的根值,6.1 树的有关概念,8） Value(T, /按某种次序访问树中每个结点,6 2 二 叉 树,树是一种分枝结构的对象，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树二叉树。,6.2 二 叉 树,一 二叉树的概念1 二叉树的定义二叉树： 或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。,说明：1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2）左、右子树不能颠例有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;,6.2 二 叉 树,2 二叉树的基本形态,6.2 二 叉 树,二、二叉树性质 性质1 在二叉树的第i 层上最多有2i-1个结点（i=1）,证明： 当i=1时，第1层只有一个根结点，结点数=20 =1，结论显然成立。,假设j=i-1时，结论正确，即第j层最多有2i-2，,所以当j=i时，第i层最多有2*2i-2=2i-1；结论正确,6.2 二 叉 树,性质2 一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。,证明：由性质1可知，深度为k的二叉树中结点个数最多= =2k-1；,每一层至少要有一个结点，因此深度为k的二叉树，至少有k个结点。,6.2 二 叉 树,证明: 设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有： nn0n1n2 在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由于这些分枝是由度为1和度为2的结点射出的，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有： nn12n21因此可以得到：n0n21 。,性质3 在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有: n0n21。,6.2 二 叉 树,两种特殊的二叉树满二叉树：如果深度为k的二叉树，有2k-1个结点则称为满二叉树；,满二叉树的特点：,叶子只能出现在最下一层；只有度为0和度为2的结点。,满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多,6.2 二 叉 树, 完全二叉树 深度为K，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点都一一对应时，称之为完全二叉树。,6.2 二 叉 树,在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。,A,1,5,2,3,4,6,7,9,10,B,C,D,E,F,G,H,I,J,8,不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点,6.2 二 叉 树,完全二叉树的特点,1. 叶子结点只能出现在最下两层；2. 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。 3. 深度为k的完全二叉树在k-1层上一定是满二叉树。,A,1,5,2,3,4,6,7,9,10,B,C,D,E,F,G,H,I,J,8,6.2 二 叉 树,性质4 具有n个结点的完全二叉树的深度为 log2n +1。,6.2 二 叉 树,性质5 对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1in）的结点，有： （1）如果i1，则结点i的双亲结点的序号为 i/2（取整）；如果i1，则结点i是根结点，无双亲结点。,6.2 二 叉 树,（2）如果2in，则结点i的左孩子的序号为2i； 如果2in，则结点i无左孩子。,6.2 二 叉 树,（3）如果2i1n，则结点i的右孩子的序号为2i1； 如果2i1n，则结点 i无右孩子。,6.2 二 叉 树,对一棵具有n个结点的完全二叉树中从1开始按层序编号，则 结点i的双亲结点为 i/2； 结点i的左孩子为2i； 结点i的右孩子为2i1。,性质5表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。,6.2 二 叉 树,三二叉树存贮结构 1 二叉树的顺序结构,二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系父子关系。,如何利用数组下标来反映结点之间的逻辑关系?,完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系 。,6.2 二 叉 树,完全二叉树的顺序存储,以编号为下标,6.2 二 叉 树,二叉树的顺序存储,按照完全二叉树编号,以编号为下标,6.2 二 叉 树,二叉树的顺序存储结构一般仅 存储完全二叉树和满二叉树。,6.2 二 叉 树,2 二叉树的链式存储结构,1）基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。,结点结构：,其中，data：数据域，存放该结点的数据信息； lchild：左指针域，存放指向左孩子的指针； rchild：右指针域，存放指向右孩子的指针。,6.2 二 叉 树,二叉树的二叉链表存储表示：Typedef struct BiNode TElemType data; struct BiNode *lchild, *rchild;/ 左右孩子指针BiNode, *BiTree;,6.2 二 叉 树,2）二叉链表 二叉链表中每个结点至少包含三个域：数据域、左指针域、 右指针域,在n个结点的二叉树中，有n+1个空链域。,6.2 二 叉 树,3 ）三叉链表 三叉链表中每个结点至少包含四个域：数据域、双亲指针域、左指针域、右指针域,结点结构：,其中，data：数据域，存放该结点的数据信息； parent:双亲指针域，存放指向指向双亲节点的指针； lchild：左指针域，存放指向左孩子的指针； rchild：右指针域，存放指向右孩子的指针。,rchild,6.2 二 叉 树,第六章 树和二叉树,6.3 二叉树的遍历,一、二叉树的遍历方法,二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。,二叉树遍历操作的结果？,对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事。 二叉树是非线性结构，每个结点可能有两个后继，如何访问二叉树的每个结点，而且每个结点仅被访问一次？,二叉树的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD,如果限定先左后右，则二叉树遍历方式有三种：前序：DLR中序：LDR后序：LRD,层序遍历：按二叉树的层序编号的次序访问各结点。,考虑二叉树的组成：,6.3 二叉树的遍历,1、先序（根）遍历若二叉树为空，则空操作返回；否则：访问根结点；先序遍历根结点的左子树；先序遍历根结点的右子树。,先序遍历序列：A B D G C E F,6.3 二叉树的遍历,6.3 二叉树的遍历,2、中序（根）遍历若二叉树为空，则空操作返回；否则：中序遍历根结点的左子树；访问根结点；中序遍历根结点的右子树。,中序遍历序列：D G B A E C F,6.3 二叉树的遍历,3、后序（根）遍历若二叉树为空，则空操作返回；否则：后序遍历根结点的左子树；后序遍历根结点的右子树；访问根结点。,后序遍历序列：G D B E F C A,4、层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。,层序遍历序列：A B C D E F G,6.3 二叉树的遍历,6.3 二叉树的遍历,例如：,先序序列：,中序序列：,后序序列：,A B C D E F G H K,B D C A E H G K F,D C B H K G F E A,6.3 二叉树的遍历,二. 遍历的递归算法,void Preorder (BiTree T, void( *visit)(TElemType/ 遍历右子树 ,先序遍历递归算法,6.3 二叉树的遍历,二叉树前序遍历的非递归算法的关键：在前序遍历过某结点的整个左子树后，如何找到该结点的右子树的根指针。解决办法：在访问完该结点后，将该结点的指针保存在栈中，以便以后能通过它找到该结点的右子树。,先序遍历非递归算法,先序遍历算法的执行轨迹,A,B,D,G,C,E,F,A,栈内容,B,D,G,C,E,F,1.栈s初始化；2.循环直到root为空或栈s为空 2.1 当root不空时循环2.1.1 输出root-data;（可将输出变为任何处理） 2.1.2 将指针root的值保存到栈中； 2.1.3 继续遍历root的左子树2.2 如果栈s不空，则2.2.1 将栈顶元素弹出至root；2.2.2 准备遍历root的右子树；,步骤：,6.3 二叉树的遍历,void Preorder (BiTree T, void( *visit)(TElemType p=p-rchild ,先序遍历非递归算法（伪代码）,6.3 二叉树的遍历,2 中序遍历递归算法,void Inorder (BiTree T, void( *visit)(TElemType/ 遍历右子树 ,6.3 二叉树的遍历,中序遍历非递归算法：,void Inorder (BiTree T, void( *visit)(TElemType / 访问结点 p=p-rchild ,6.3 二叉树的遍历,3 后序遍历递归算法,void Postorder (BiTree T, void( *visit)(TElemType / 访问结点 ,若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？,例如：已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABCDEFGHI 和BCAEDGHFI，如何构造该二叉树呢?,6.3 二叉树的遍历,先序：A B C D E F G H I中序：B C A E D G H F I,先序：B C中序：B C,先序： D E F G H I中序： E D G H F I,6.3 二叉树的遍历,先序：F G H I中序：G H F I,先序： D E F G H I中序： E D G H F I,6.3 二叉树的遍历,第六章 树和二叉树,6.4 遍历的应用,遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。,6.4 遍历的应用,例1 编写 求二叉树的叶子结点个数的算法输入：二叉树的二叉链表结果：二叉树的叶子结点个数基本思想：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。所以可在二叉树遍历的过程中，统计叶子结点的个数。,void leaf(BiTree T) /n计数二叉树的叶子结点的个数，初值n=0if(T) if(T-lchild=null /if/leaf,例2 求二叉树的结点个数。,void Count(BiNode *root) /n为全局量并已初始化为0 if (root) Count(root-lchild); n+ +; Count(root-rchild); ,6.4 遍历的应用,例3 、求二叉树的深度。,int Depth(BiNode *root) if (root= =NULL) return 0; else hl= Depth(root-lchild); hr= Depth(root -rchild); return max(hl, hr)+1; ,6.4 遍历的应用,二叉树的深度应为其左、右子树深度的最大值加1。,6.4 遍历的应用,例4 为二叉树建立二叉存储链表 输入：二叉树的先序序列 结果：建立二叉树的二叉存储链表,按先序编历的顺序输入先序序列（设每个元素是一个字符），建立二叉链表的所有结点并完成相应结点的链接。,为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如“#”，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。,扩展二叉树的先序遍历序列:A B # D # # C # #,6.4 遍历的应用,6.4 遍历的应用,Status CreateBiTree(BiTree /CreateBiTree,第六章 树和二叉树,6.5 线索二叉树 1. 线索二叉树的概念 2 线索链表 3. * 线索二叉树的遍历,6.5 线索二叉树,一、 线索二叉树,遍历的目的： 将二叉树中的结点按一定规律（先、中、后序）线性化的过程。,问题：当以二叉链表作为存储结构时，只能找到某结点的左、右孩子信息，不能得到结点在某种遍历序列中的前驱和后继信息。,解决办法： 重新遍历，在遍历过程中得到前驱、后继信息。但这种动态 访问浪费时间。 充分利用二叉链表的空链域，将遍历过程中结点的前驱、后 继信息保留下来。,结点结构,6.5 线索二叉树,线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；线索二叉树：加上线索的二叉树称为线索二叉树。,ABDGCEF,DGBAECF,GDBEFCA,NULL,NULL,NULL,NULL,先序,中序,后序,DGBAECF,NULL,NULL,中序,找前驱结点1、PLtag=1,PLchild为前驱2、“根”P的前驱结点是中序遍历P的左子树时访问的最后一个结点,找后继结点1、PRtag=1,PRchild为后继驱2、“根”P的后继结点是其右子树的“最左下端”的结点,A,头指针,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序线索链表的建立过程,已经建立起二叉链表,D G B A E C F,A,头指针,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序线索链表的建立过程,中序遍历二叉链表p为正在访问的结点pre为刚访问的结点,1,D,D G B A E C F,A,头指针,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序线索链表的建立过程,中序遍历二叉链表p为正在访问的结点pre为刚访问的结点,1,1,D G,D G B A E C F,A,头指针,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序遍历二叉链表p为正在访问的结点pre为刚访问的结点,1,1,1,中序线索链表的建立过程,D G B,D G B A E C F,A,头指针,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序遍历二叉链表p为正在访问的结点pre为刚访问的结点,1,1,1,1,中序线索链表的建立过程,D G B A,D G B A E C F,A,头指针,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序遍历二叉链表p为正在访问的结点pre为刚访问的结点,1,1,1,1,1,中序线索链表的建立过程,D G B A E,D G B A E C F,A,头指针,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序遍历二叉链表p为正在访问的结点pre为刚访问的结点,1,1,1,1,1,1,中序线索链表的建立过程,D G B A E C,D G B A E C F,A,头指针,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序遍历二叉链表p为正在访问的结点pre为刚访问的结点,1,1,1,1,1,1,1,中序线索链表的建立过程,D G B A E C F,D G B A E C F,A,头指针,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序遍历二叉链表p为正在访问的结点pre为刚访问的结点,1,1,1,1,1,1,1,1,中序线索链表的建立过程,D G B A E C F,D G B A E C F,第六章 树和二叉树,6.6 树和森林 一. 树的存储结构 二. 树和二叉树的转换 三. 树的遍历 四. 森林,6.6 树和森林,一树的存贮结构 1、双亲表示法,基本思想：用一维数组来存储树的各个结点（一般按层序存储），数组中的一个元素对应树中的一个结点，包括结点的数据信息以及该结点的双亲在数组中的下标。,6.6 树和森林,#define MAX_TREE_SIZE 100type struct PTNode /结点结构 TEleType data; /数据域 int parent; /双亲在数组中的下标 PTNode;Typedef struct /树结构 PTNode nodesMAX_TREE_SIZE int r,n /根的位置和结点数PTree,树的双亲表示法实质上是一个静态链表。,6.6 树和森林,找某一结点的双亲，按照该结点的双亲下表即可找到。但求某一结点的孩子，要遍历整个结构。,6.6 树和森林,2、孩子表示法,链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。,6.6 树和森林,缺点：浪费空间,A,B,C,D,E,F,G,H,I,6.6 树和森林,方案二： 指针域的个数等于该结点的度,其中：data：数据域，存放该结点的数据信息； degree：度域，存放该结点的度； child1childd：指针域，指向该结点的孩子。,缺点：结点结构不一致,A 2,B 3,C 2,E 1,I 0,G 0,H 0,F 0,D 0,6.6 树和森林,6.6 树和森林,方案三：将结点的所有孩子放在一起，构成线性表。,基本思想： 把每个结点的孩子排列起来，看成是一个线性表，且以单链表存储，则n个结点共有 n 个孩子链表。这 n 个单链表共有 n 个头指针，这 n 个头指针又组成了一个线性表，构成孩子链表的表头数组。,6.6 树和森林,typedef struct CTNode int child; struct CTNode *next;,Typedef struct TElemType data; ChildPtr *firstchild; CTBox;typedef struct CTBox nodesMAX_TREE_SIZE int n,r;CTree;,6.6 树和森林,012345678,下标 data firstchild,A B C D E F G H I,带双亲的孩子链表：将双亲表示法和孩子表示法结合,-1,A,0,B,0,C,1,D,1,E,1,F,2,G,2,H,4,I,0,1,2,3,4,5,6,7,8,下标 para data firstchild,6.6 树和森林,6.6 树和森林,3、孩子兄弟表示法又称二叉树表示法,结点结构,data： 数据域，存储该结点的数据信息；firstchild：指针域，指向该结点第一个孩子；rightsib： 指针域，指向该结点的右兄弟结点。,typedef struct CSNode ElemType data; struct CSNode *firstchild, *rightsib;CSNode,*CSTree;,A,B,C,D,E,F,I,G,H,6.6 树和森林,二 树与二叉树的转换 二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。,存储结构,二叉树逻辑结构,树逻辑结构,1.兄弟加线.,树和二叉树之间的转换,6.6 树和森林,2.保留双亲与第一孩子连线,删去与其他孩子的连线.,树和二叉树之间的转换,1.兄弟加线.,6.6 树和森林,3.顺时针转动,使之层次分明.,树和二叉树之间的转换,2.保留双亲与第一孩子连线,删去与其他孩子的连线.,1.兄弟加线.,A,B,C,D,E,F,G,6.6 树和森林,3.顺时针转动,使之层次分明.,树和二叉树之间的转换,2.保留双亲与第一孩子连线,删去与其他孩子的连线.,1.兄弟加线.,6.6 树和森林,树转换为二叉树,加线树中所有相邻兄弟之间加一条连线。 去线对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。 层次调整以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。,6.6 树和森林,ABEFCDG,ABEFCDG,树的先序遍历等价于二叉树的先序遍历！,6.6 树和森林,EFBCGDA,EFBCGDA,树的后序遍历等价于二叉树的中序遍历！,6.6 树和森林,因此，我们得出，树只有先序和后序两种遍历,6.6 树和森林,