数据结构第5章-树-pa.ppt

第 5 章 树和二叉树,5.1 树的定义和基本术语 *5.2 二叉树 *5.3 遍历二叉树和线索二叉树 *5.4 树和森林 5.5 赫夫曼树及其应用,5.1 树的定义和基本术语,5.1.1 树的定义 5.1.2 基本术语 5.1.3 树的表示,1.树的定义 树是由n（n0）个结点组成的有限集合。若n=0，称为空树；若n0，则： （1）有且仅有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱； （2）当n1时,其余结点可以划分为m（m0）个互不相交的有限集合T1，T2，Tm，每个集合又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。,5.1.1 树的定义,图 5-1 树的逻辑结构图,由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。树的结构参见图5-1。,一棵树的逻辑结构可以用二元组描述为： tree =(k,R) k=ki1in;n0,kielemtype R=r 其中，n为树中结点个数，若 n=0，则为一棵空树， n0时称为一棵非空树，而关系 r 应满足下列条件： （1）有且仅有一个结点没有前驱,称该结点为树根; （2）除根结点以外,其余每个结点有且仅有一个直接前驱; （3）树中每个结点可以有多个直接后继(孩子结点)。,2. 树的逻辑结构描述,例如：对图5-1(c )的树结构,可以二元组表示为：,K=A，B，C，D，E，F，G，H，I，J，K，L，M R=r r=，,(1) InitTree(&T) 初始化树T。 (2) Root(T) 求树T的根结点 (3) Parent(T,x) 求树T中，值为x的结点的双亲。 (4) Child(T,x,i) 求树T中，值为x的结点的第i个孩子。 (5) AddChild(y,i,x) 把值为x的结点作为值为y的结点的第i个孩子插入到树中。 (6) DelChild(x,i) 删除值为x的结点的第i个孩子。 (7) TraverseTree(T) 遍历或访问树T。,3. 树的基本运算,1.结点: 树的结点包含一个数据元素及若干指向其子树的分支 2.度: 一个结点包含子树的数目，称为该结点的度。 3.叶子（终端）结点 度为0的结点，称为叶子结点或树叶，也叫终端结点。 4.孩子结点 若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图5-1（c）中A的孩子为B，C，D。 5.双亲结点 若结点X有子女Y，则X为Y的双亲结点。,5.1.2 基本术语,6.祖先结点 从根结点到该结点所经过分支上的所有结点为该结点的祖先，如图5-1（c）中M的祖先有A，D ，H 。 7.子孙结点 某一结点的子女及子女的子女都为该结点子孙。 8.兄弟结点 具有同一个双亲的结点，称为兄弟结点。 9.分支结点 除叶子结点外的所有结点，为分支结点，也叫非终端结点。(度不为0的结点) 10层数(层次) 根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。,11. 树的高度（深度） 树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度1。 12.树的度 树中结点度的最大值称为树的度。 13. 有序树 若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。 14. 无序树 若一棵树中所有子树的次序无关紧要，则称为无序树。 15森林（树林） 若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。,1树形结构表示法,5.1.3 树的表示,2. 凹入法表示法,3. 嵌套集合表示法,4. 广义表表示法 （A（B（E（J，K，L），F），C（G），D（H（M），I）,5.2 二叉树,5.2.1 二叉树的基本概念 5.2.2 二叉树的性质 5.2.3 二叉树的存储结构,5.2.1 二叉树的基本概念,1 二叉树的定义 和树结构定义类似，二叉树的定义也可以递归形式给出： 二叉树是n（n0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。 二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒。因此，二叉树有五种不同的形态。,(a) 空二叉树 (b) 仅有一个根结点的二叉树 (c) 右子树为空的二叉树 (d) 左子树为空的二叉树 (e) 左、右子树均非空的二叉树,二叉树的五种基本形态,（1）InitBitree(&T) 二叉树的初始化。 （2）Root(T) 求二叉树的根结点 （3）Parent(T,x) 求二叉树T中值为x的结点的双亲（4）Lchild(T,x) 求二叉树T中值为x的结点的左孩子。 （5）Rchild(T,x) 求二叉树T中值为x的结点的右孩子。 （6）Lbrother(T,x) 求二叉树T中值为x的结点的左兄弟。 （7）Rbrother(T,x) 求二叉树T中值为x的结点的右兄弟。,2. 二叉树的基本运算,（8）Traverse(T) 遍历二叉树T。 （9）CreateBiTree(&T) 建立一棵二叉树T。 （10）AddLchild(&T,x,y) 在二叉树T中，将值为y的结点作为值为x的结点的左孩子插入。 （11）AddRchild(&T,x,y) 在二叉树T中，将值为y的结点作为值为x的结点的右孩子插入。 （12）DelLchild(&T,x) 在二叉树T中，删除值为x 的结点的左孩子。 （13）DelRchild(&T,x) 在二叉树T中，删除值为x 的结点的右孩子。,性质1 若二叉树的层数从1开始，则二叉树的第i层结点数，最多为2i-1个（i1）。,5.2.2 二叉树的性质*,20=1,21=2,22=4,23=8,深度（高度）为k的二叉树最大结点数为2k-1（k1）。 证明:最大结点个数=20+21+22+2k-1 =2k-1,性质2,对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。 证明： 设n0,n1和n2分别为二叉树中度为0,度为1和度为2的结点个数，则二叉树中总的结点个数n满足： n=n0+n1+n2 再有除了根结点之外，每个结点都由一个分支射入，则分支数B与总的结点数之间的关系为： n=B+1 另外，由于这些分支是由度为1或2的结点射出的，则有 B=n1+2n2 则由上三式得： n0=n2+1,性质3,为继续给出二叉树的其它性质，先定义两种特殊的二叉树： 满二叉树 深度为k具有2k-1个结点的二叉树，称为满二叉树。 完全二叉树 如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1- n的结点一一对应，则称这棵二叉树为完全二叉树。,具有n个结点的完全二叉树的深度为 log2n +1 证明：设深度为k,则由性质2和完全二叉树的性质有： 2k-1-1n2k-1 即 2k-1 n 2k 则有 k-1 log2n k 由于k是整数，则有k= log2n +1,性质4,对于完全二叉树中任一个编号为i的结点(1in)，它的父结点和左、右儿子结点的编号与i值有如下的关系： (1) 如果i=1，则它是整个树的根结点，无父结点；若i1，则其父结点编号为 i/2 。 (2) 如果2in，则其左儿子结点编号为2i；若2in，则无左儿子结点。 (3) 如果（2i+1）n，则其右儿子结点编号为（2i+1）；反之，则无右儿子结点。,性质5,5.2.3 二叉树的存储结构,1.顺序存储结构 2.链式存储结构,1.顺序存储结构,思想: 用一个一维数组来存储二叉树的各个结点 C语言表示 #define MAX_TREE_SIZE 100/二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; /0号单元存储根结点 SqBiTree bt;,分析: 显然，二叉树的结点必须按某种次序分别存入数组的各个单元，这种次序应能反映结点间的逻辑关系，否则二叉树上的各种基本运算在顺序存储结构上很难实现。 对于完全二叉树来说，可以采用“以编号为地址”的方法，将编号为i的结点存入一维数组的第i个单元(下标为i-1)。,例: 对应的顺序存储结构: 下标,完全二叉树的顺序表示:,例: 对应的顺序存储结构: 一维数组的21单元中只用上了7个.最坏情况下,一个深度为k且只有k个结点的单支树,却需要长度为2k-1的一维数组.,非完全二叉树的顺序表示:,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21,2. 二叉链表,结点结构: 通常每个结点中设置三个域,即值域、左指针域和右指针域，其结点结构如下： 其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针。,存储表示,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BITree; 这里的TElemType可以是任何相应的数据类型如int、float或char等。,二叉链表,例: 链式存储:,3. 三叉链表,通常每个结点中设置四个域,即值域、左指针域、右指针域和双亲指针域，其结点结构如下： 其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针,parent指向双亲结点。,rchild,parent,总结:,顺序存储结构适合存储完全二叉树 对于非完全二叉树，采用链式存储结构更合适,5.3 遍历二叉树和线索二叉树* 5.3.1 遍历二叉树,定义:二叉树的遍历(Traverse)是指按一定的规律访问二叉树的每个结点，且每个结点只被访问一次的过程。 对二叉树的遍历过程实际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。 本节仅讨论二叉链表的遍历过程。,一个非空的二叉树由根结点及左、右子树这三个基本部分组成，因此若能依次遍历这三部分，便是遍历了整个二叉树。 在任一给定结点上，可以按某种次序执行三个操作：访问结点本身，遍历该结点左子树，遍历该结点右子树，操作排列次序： 左、根、右；根、左、右；左、右、根； 右、根、左；根、右、左；右、左、根； 由于实际问题一般都是要求左子树较右子树先遍历，故只采用其中、三种遍历次序，分别称为中序遍历、先序遍历和后序遍历。,(1) 中序（InOrder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 中序遍历左子树； 访问根结点； 中序遍历右子树。,三种遍历次序以递归的形式定义：,中序遍历左子树； 访问根结点； 中序遍历右子树。,结点访问顺序： D B E F C G A,结点访问顺序： 8 4 9 2 10 5 1 6 3 7,(2) 先序（PreOrder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 访问根结点； 先序遍历左子树； 先序遍历右子树。,结点访问顺序为： A B D C E F G,结点访问顺序为： 1 2 4 8 9 5 10 3 6 7,(3) 后序（PostOrder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 后序遍历左子树； 后序遍历右子树； 访问根结点。,遍历顺序： D F E G C B A,遍历顺序： 8 9 4 10 5 2 6 7 3,中序遍历序列： 先序遍历序列： 后序遍历序列：,二叉树遍历练习,HDIBEAFCG,ABDHIECFG,HIDEBFGCA,例题： 中序：C B E D A G H F J I 后序: C E D B H G J I F A,*,*,例题： 先序：ABCDEFGHIJ 中序: CDBFEAIHGJ,中序遍历递归算法,void InOrder(BITree T) if (T) InOrder(T-lchild); visit(T-data); InOrder(T-rchild); ,先序遍历递归算法,void PreOrder(BITree T) if (T) visit(T-data); PreOrder(T-lchild); PreOrder(T-rchild); ,后序遍历递归算法,void PostOrder(BITree T) if (T) PostOrder(T-lchild); PostOrder(T-rchild); visit(T-data); ,遍历算法的应用,二叉树的遍历算法是一个重要的应用 注意: 1.理解访问根结点的意义 2.对具体问题需要考虑遍历的顺序,1.先序创建二叉链表,Status CreateBiTree(BITree ,2.输出二叉树的结点,void PreOrder(BITree T) if (T) printf(T-data); PreOrder(T-lchild); PreOrder(T-rchild); ,3.输出二叉树的叶子结点,void PreOrder(BITree T) if (T) if(T-lchild=NULL ,4.统计二叉树的叶子结点个数,int n=0; void leafcount(BITree T) if (T) if(T-lchild=NULL ,5.求二叉树的高度,int PostTreeDepth(BITree T) if (T) hl=PostTreeDepth (T-lchild); hr=PostTreeDepth (T-rchild); max=hlhr?hl:hr; return(max+1); else return 0; ,练习,1. 假设二叉树包含的结点数据为1，3，7，2，12. (1)画出两棵高度最大的二叉树。 (2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。,练习,1. 假设二叉树包含的结点数据为1，3，7，2，12. (1)画出两棵高度最大的二叉树。 (