[电脑基础知识]第7章 树.ppt

第 7 章 树,授课班级：可视化、数据库,学习目标,理解树的定义和与树相关的结点、度、路径等术语 理解树是一个非线性层次数据结构 掌握树的前序遍历、中序遍历和后序遍历方法 了解树的父结点数组表示法 了解树的儿子链表表示法 了解树的左儿子右兄弟表示法,理解二叉树和ADT二叉树的概念 了解二叉树的顺序存储结构 了解二叉树的结点度表示法 掌握用指针实现二叉树的方法 理解线索二叉树结构及其适用范围,7.1 树的定义,树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。,树是由一个集合以及在该集合上定义的一种层次关系构成。 定义：树(Tree)是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： （1）有且仅有一个特定的称为根(Root)的结点； （2）其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。,图7.1 树的层次结构,树结构中的一些基本概念和常用术语 结点：包含一个数据元素及若干指向其它结 点的分支信息。 结点的度：一个结点的子树个数称为此结点的度。 树的度： 树中所有结点的度的最大值。 叶结点：度为0的结点，即无后继的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。除根结点外的分支结点统称为内部结点。,结点的高度：从该结点到各叶结点的最长路径的长度。树的高度是指根结点的高度。 路径（道路）：若存在树中的一个结点序列k1,k2,kj，使得结点ki是结点ki+1的父结点，则称该结点序列是树中从结点k1到kj的一条路径。 路径长度：该路径所经过的边（即连接两个结点的线段）的数目。 祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。在图7.1中，结点F的祖先是A、B、F。 ,子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点。在图7.1中，结点F的子孙是F、I、 J。 注意：任一结点既是它自己的祖先也是它自己 的子孙。 真祖先、真子孙：树中一个结点的非自身祖先和子孙分别称为该结点的真祖先和真子孙。 兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。在图7.1中，结点F的兄弟是E。,结点的深度或层数：从根结点开始定义，根结点的层次为0，其余结点的深度为其父结点的深度加1，如根的直接后继的层次为1，依此类推。 有序树：在树T中，如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子（最左儿子或简称为左儿子），最右边的称为最后一个孩子（最右儿子或简称为右儿子） 。,森林是m(m=0)棵互不相交的树的集合。如果我们删去一棵树的树根，留下的子树就构成了一个森林。当我们删去的是一棵有序树的树根时，留下的子树也是有序的，这些树组成一个树表。在这种情况下，称这些树组成的森林为有序森林或果园。,7.2 树的遍历,定义：按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。 遍历方式： 前序遍历 中序遍历 后序遍历,三种遍历方式的定义: (1)若T是一棵空树，对T进行三种遍历操作都是空操作； (2)若T是一棵单结点树，对T进行三种遍历操作都只访问单结点； 否则，设以n为树根，树根的子树从左到右依次是T1,T2,TK，那么,对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,TK。 对T进行中序遍历是先中序遍历T1，然后访问树根n,接着依次对T2,TK进行中序遍历。 对T进行后序遍历是先依次对T1,T2,TK进行后序遍历，最后访问树根n。,图7.2 树T,例如，对图7.1进行前序遍历、中序遍历和后序遍历的结果分别为： 前序：A B E F I J C D G H 中序：E B I F J A C G D H 后序：E I J F B C G H D A,练习：写出下图所示的树， 其先序、 中序、 后序遍历的序列。 ,解答： 先序遍历： A、 B、 D、 F、 G、 C、 E、 H 。 中序遍历： B、 F、 D、 G、 A、 C、 E、 H 。 后序遍历： F、 G、 D、 B、 H、 E、 C、 A 。,非递归方式产生三种遍历的序列： 从树根出发，依逆时针方向沿树的外缘绕行， 若按第一次经过的时间次序将各个结点列出，就可以得到前序列表； 若按最后一次经过的时间次序将各个结点列出，就可以得到后序列表； 若将叶结点按第一次经过时列出，而内部结点在第2次经过时列出，就可以得到中序列表；,先序序列：A B D E H I C F,后序序列：D H I E B F G C A,中序序列：D B H E I A F C G,例：,最早提出遍历问题是对存储在计算机中的表达式求值。例如：(a+b*c)-d/e。该表达式用二叉树表示如图7.3所示。当我们对此二叉树进行先序、中序、后序遍历时，便可获得表达式的前缀、 中缀、 后缀书写形式： 前缀： -+a*bc/de 中缀： a+b*c-d/e 后缀： abc*+de/- 其中中缀形式是算术表达式的通常形式，只是没有括号。 前缀表达式称为波兰表达式。算术表达式的后缀表达式被称作逆波兰表达式。 在计算机内， 使用后缀表达式易于求值。,图7.3 算术式的树表示,7.3 树的表示法,图7.4 树,7.3.1 父结点数组表示法,1,2,3,4,5,6,7,8,9,10,7.3.2 儿子链表表示法,header,7.3.3 左儿子右兄弟表示法,7.4 二叉树,定义：二叉树是n(n=0)个结点的有限集合，此集合或者为空集（n=0），或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 特点： 1.每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点); 2.该两棵子树可以为空; 3.该两棵子树有次序之分，分别称之为左子树和右子树,其次序不能任意颠倒。,二叉树的5种基本形态：,二叉树与树和有序树的区别,特别要注意：二叉树不是树的特殊情况，它们是两个不同的概念。,A树中结点的最大度数没有限制，二叉树结点最大度数为2。 B树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。,树,二叉树,二叉树的性质,高度为h=0的二叉树至少有h+1个结点。 高度不超过h的二叉树至多有2h+1-1个结点。 含有n=1个结点的二叉树的高度至多为n-1。 含有n=1个结点的二叉树的高度至少为logn，因此其高度为(logn)。,性质5：在二叉树的第i层上至多有2i个结点(i=0)。,两种特殊形态的二叉树,满二叉树：一棵高度为h且由2h+1-1个结点的二 叉树称为满二叉树。,特点：1.每一层上都含有最大结点数 2.不存在度为1的结点，每个分支结点均有两棵高度相同的子树，且叶子都在最下一层。,完全二叉树-高度为k的，有n个结点的二叉树，当且仅当每一个结点都与高度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树（也称为近似满二叉树）,完全二叉树,特点： （1）叶子结点只可能在层次最大的两层上出现； （2）对任一结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙最大层次必为L或L+1。,(b)非完全二叉树,(c)非完全二叉树,（b）、（c）是2棵非完全二叉树。满二叉树是完全二叉树的特例。,(a)完全二叉树,对一棵完全二叉树，有： 1.至多只有最下面两层上结点的度数可以小于2； 2.最下面一层结点都集中在该层的最左边； 3.满二叉树是完全二叉树，反之不然，在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。,完全二叉树,7.5 ADT 二叉树,二叉树的基本运算 BinaryInit( ):创建一棵空二叉树 BinaryEmpty(T):判断一棵二叉树T是否为空 Root(T):返回二叉树T的根结点标号 MakeTree(x,T,L,R):以x为根结点元素，分别以L和R为左、右子树构建一棵新的二叉树T。,BreakTree(T,L,R) PreOrder(visit,t) InOrder(visit,t) PostOrder(visit,t) PreOut(T) InOut(T),PostOut(T) Delete(t) Height(t) Size(t),7.6 二叉树的实现,1.顺序存储结构 实现方法： 将二叉树的所有结点，按照一定的次序依次存储到一组连续的存储单元中。 对于完全二叉树，可采用“以编号为地址”的策略将结点存入作为顺序存储结构的一维数组。 具体实现如下： 将一棵具有n个结点的完全二叉树，从树根起，自上层到下层，逐层从左到右给所有结点编号，其中每个结点的编号作为结点的名称。将编号为i的结点存入一维数组的第i个单元，这样，就能得到一个足以反映整个二叉树结构的线性序列。,完全二叉树,a,b,c,d,e,f,g,h,i,j,k,l,(1) 顺序存储结构,1,2,3,4,5,6,7,8,9,10,11,12,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i（11，则其双亲是结点i/2。 （2）结点i的左儿子结点为2i，结点i的右儿子结点为2i+1。 （3）当i为奇数且不为1时，结点i的左兄弟结点为i-1,当i为偶数时，结点i的右兄弟结点为i+1。,i/2,i,i+1,2i+1,2(i+1),2i+3,i+1,2(i+1),2i+3,i,2i,2i+1,图 完全二叉树中结点i和i+1,(a)i和i+1结点在同一层,(b)i和i+1结点不在同一层,2i,如图所示为完全二叉树上结点及其左右子树在结点之间的关系。,由上述关系可知， 完全二叉树中结点的层次关系足以反映结点之间的逻辑关系。在这种存储结构中，借助二叉树的性质，可以比较方便地实现二叉树的各种基本运算。因此，对完全二叉树而言，顺序存储结构既简单又节省存储空间。,T16,(1) 顺序存储结构,0,0,0,0,F,E,0,0,0,D,C,0,B,A,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,0,一般二叉树,缺点: 对于一般的二叉树而言，存储空间造成极大的浪费。在最坏情况下，一个高度为k且只有k+1个结点的右单枝树却需要2k+1-1个结点的存储空间。,例如，只有3个结点的右单枝树:,2. 二叉树的结点度表示法 这种表示法将二叉树中所有结点依其后序列表排列，并在每个结点中附加一个03之间的整数，以表示结点的状态。,3.用指针实现二叉树（链式存储结构（二叉链表结构） 每个结点由数据域、左指针域和右指针域组成。,二叉树的二叉链表存储结构类型描述 Typedef struct btnode *btlink; struct btnode TreeItem element; btlink left; btlink right; Btnode;,课堂练习,分别画出下图所示二叉树的二叉链表、二叉树的结点度表示法和顺序存储结构示意图。,B,E,A,F,D,C,已知一棵二叉树的先序序列和中序序列分别为A B D G H E C F I J 及G D H B E A C I J F，请画出这棵二叉树 。,用指针实现的抽象数据类型二叉树结构定义为： typedef struct binarytree *BinaryTree; typedef struct binarytree btlink root; BTree;,btlink NewBNode( ) btlink p; if(p=malloc(sizeof(Btnode)=0) Error(“Exhausted memory.”); else return p; ,创建一棵空二叉树 BinaryTree BinaryInit( ) BinaryTree T=malloc(sizeof *T); T-root=0; return T; ,抽象数据类型二叉树的基本运算 1、返回根结点标号 int BinaryEmpty(BinaryTree T) return T-root=0; TreeItem Root(BinaryTree T) if(BinaryEmpty(T) Error(“Tree is empty”) return T-root-element; ,2、创建一棵新的二叉树T void MakeTree(TreeItem x, BinaryTree T，BinaryTree L,BinaryTree R) T-root=NewBNode(); T-root-element=x; T-root-left=L-root; T-root-right=R-root; L-root=R-root=0; ,3、将二叉树拆分 TreeItem BreakTree(BinaryTree T,BinaryTree L,BinaryTree R) TreeItem x; if(! T-root) Error(“Tree is empty”); x=T-root-element; L-root=T-root-left; R-root=T-root-right; T-root=0; return x; ,4、先序遍历 void PreOrder(void (*visit)(btlink u),btlink t) if(t) (*visit)(t); PreOrder(visit,t-left); PreOrder(visit,t-right); ,5、中序遍历 void PreOrder(void (*visit)(btlink u),btlink t) if(t) InOrder(visit,t-left); (*visit)(t); InOrder(visit,t-right); ,6、后序遍历 void PreOrder(void (*visit)(btlink u),btlink t) if(t) PostOrder(visit,t-left); PostOrder(visit,t-right); (*visit)(t); ,7、返回二叉树的高度 int Height(btlink t) int hl,hr; if( !t ) return -1; hl=Height(t-left); hr=Height(t-right); if(hlhr) return +hl; else return +hr; ,遍历二叉树和线索二叉树,一、遍历二叉树 1、先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。,2、中序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 3、后序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。,课堂练习二,写出下图二叉树的先序、中序、后序的遍历序列,线索二叉树 用指针实现二叉树时，在n个结点二叉树中含有n+1个空指针，可以利用这些空指针存放指向结点在某种遍历次序下的前驱和后继结点指针。这种附加的指针称为“线索”，加上线索的二叉树称为线索二叉树。,为了区分一个结点的指针是指向其儿子结点的指针，还是指向去前驱或后继结点的线索，可在每个结点中增加2个线索标志。这样，线索二叉树结点类型定义为： typedef struct btnode *tbtlink; struct tbtnode TreeItem element; btlink left; btlink right; int leftThread,rightThread; ThreadedNode;,改进后的结点结构 其中: 0 left 域指示结点的左孩子 leftThread= 1 left 域指示结点的前驱 0 right 域指示结点的右孩子 rightThread= 1 right 域指示结点的后继,例如下图是一棵中序线索二叉树，它的线索 链表如图 1所示。,图1 线索链表,如何在线索二叉树中找结点的前驱和后继结点？ 1、找结点的后继结点的过程（以中序线索为例）： 1）树中所有叶结点的右链是线索，因此叶结点的right指向该结点的后继结点。 2）非终端结点若无右孩子，则其右链是线索，指向后继，若有右孩子，则其后继是中序遍历其右子树时访问的第一个结点，即右子树中最左下结点 。,2、找结点的前驱结点的过程 （以中序线索为例）： 1）树中所有叶结点的左链是线索（左线索标志为1），因此叶结点的Left直接指向其前驱结点。 2）若该结点的左线索标志为0，则该结点的前驱为遍历其左子树时最后访问的那个结点，即左子树中最右下的结点为其前驱结点。 若线索二叉树的高度为h，则在最坏情况下，可在O(h)时间内找到一个结点的前驱和后继结点 。,如何进行二叉树的线索化呢？ 线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱和后继的信息只有在遍历时才能得到，因此线索化过程即为在遍历的过程中修改空指针的过程。,哈夫曼树及其应用,树的路径长度的概念： 1.结点间的路径长度-从树中一个结点到另一个结点之间的分支数目。 2.树的路径长度-从树根到每一结点的路径长度之和。如图所示：,树的路径长度PL=0+1+1+2+2+2+2=10,结点带权的路径长度：从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度（weighted path length of tree）：树中所有叶子结点的带权路径长度之和。,记作：,其中： Wk为树中每个叶子结点的权 L k为每个叶子结点到根的路径长度。,WPL最小的二叉树就称作最优二叉树或哈夫曼树 。,具有不同带权路径长度的二叉树,怎样构造一棵哈夫曼树呢？ 方法： （1）根据给定的n个权值W1,W2,Wn构成n棵二叉树的森林F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右子树均为空; （2）在森林F中选取两棵根结点权值最小的和次小的二叉树(当这样的树不止两棵树时，可以从中任选两棵)作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。 （3）在F中删除这两棵权值最小的树，同时将新的二叉树加入到森林F中; （4）重复2、3步骤，直至F中只剩一棵树为止。 这棵树便是哈夫曼树。