《树的基础知识》PPT课件.pptVIP

1 树,1.1 树,1.2 二叉树,1.3 二叉树的遍历,1.4 线索二叉树,1.5 树和森林,1.1 树,树的定义：,树：T是n个结点构成的有限集合(n0)，其中有一个结点叫根，其余结点可划分为m个互不相交的子集T1，T2，Tm (m0)，并且这m个子集本身又构成树，称为T的子树。,注意：这里没给出空树的概念。,从树的定义可以看出，树的逻辑结构： （1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。 （2）树中所有结点可以有零个或多个后继结点。,1.1 树,树的表示形式：,图形表示法,嵌套集合表示法,凹入表表示法,广义表表示法,( A ( B ( D, E ( H, I ), F ), C ( G ) ) ),1.1 树,树的有关概念：,1、孩子结点、双亲结点(父结点)：某结点的子树的根为该结点的孩子结点，而该结点为其孩子结点的双亲结点。 兄弟结点：同一结点的孩子为兄弟结点。 可延伸到祖先结点和后代结点。,2、一个结点的度：该结点的直接后继结点(孩子)的个数。 树的度：树中最大的结点度。,3、叶子结点(终结点)：结点度为0。 分支结点：结点度不为0。 根结点：无直接前驱结点。,1.1 树,树的有关概念：,5、森林：多棵树。,4、一个结点的层次：根为1，其余为父结点的层次数加1。 树的深度：最大的结点层次数。,6、有序树：树中各兄弟结点之间的排列次序是有关的。 无序树：树中各兄弟结点之间的排列次序是无关的。,1.1 树,树的基本运算：,1、初始化树initial_tree(T)：建立树的初始结构。,2、插入子树insert_tree(T, S)：将以S为根的子树作为T的第一个子树插入到树中。,3、插入兄弟结点insert_sigling(T, S)：将以S为根的树作为T的兄弟子树插入到树中。,4、查询根结点rootof(T)：查询结点T所在树的根结点。,5、查询父结点fatherof(T)：查询结点T的父结点。,6、查询孩子结点childof(T)：查询结点T的所有或某个孩子结点。,7、查询兄弟结点siblingof(T)：查询结点T的所有或某个兄弟结点。,1.2 二叉树,1.2.1 二叉树的基本概念,二叉树T是n个结点的有限集合，其中n0,当n=0时，为空树，否则，其中有一个结点为根结点，其余结点划分为两个互不相交的子集TL、TR，并且TL、TR分别构成叫作左、右子树的二叉树。（即树中结点的最大度为2，每个结点的孩子有左、右之分）。,1.2 二叉树,1.2.1 二叉树的基本概念,1.2 二叉树,1.2.1 二叉树的基本概念：,满二叉树：每层都有最大数目结点的二叉树。,满二叉树：每层都有最大数目结点的二叉树。,完全二叉树：在满二叉树的最下层从右向左连续地删除若干个结点所得到的二叉树。（满二叉树是完全二叉树的一个特例）,1.2 二叉树,1.2.2 二叉树的性质,性质1：在二叉树的第i层上的结点个数2 i - 1（i0）。,性质2：深度为k的二叉树的结点个数2k -1（k0）。,性质3：对任一棵非空的二叉树T，如果其叶子数为n0，度为2的结点数为n2，则有：n0 = n2 +1。,性质4：有n个结点的完全二叉树(n0)的深度为log2n+1。,性质5：在编号的完全二叉树(根结点编号为1，顺序按从上到下、从左到右进行编号)中，各结点编号之间的关系为：i结点若有左孩子则其编号为2i，若有右孩子则其编号为2i+1，若有父结点则其编号为i/2。,证明,1.2 二叉树,性质1证明：用数学归纳法证明 。,性质2证明：结点个数n20 +21 +22 + +2k-1 =2k-1 。,性质3证明：设T的总结点数为n，度为1的结点数为n1，则T的结点数满足关系式： n=n0+n1+n2 (a) 从T的分支数来看：在这n个结点中，除根以外，每个结点有一个分支进入，因此其总分支数为n-1。而这些分支仅从度为1和2的结点发出，则有：n-1=n1+2n2 (b) 由(a)和(b)得：n0=n2+1,性质4证明：设树深为k，则结点数满足：2k-1-1n2k-1； 2k-1n2k ；k-1log2n k；k= log2n+1。,返回,1.2 二叉树,1.2.3 二叉树的存储结构,1、顺序存储结构,要能存储结点值并能体现结点间的关系，而结点间的关系可用完全二叉树的编号来表示，即要先向二叉树添加一些虚结点形成完全二叉树，如此可用数组存放结点的值，而其关系用下标来体现。,存储状态如下：,data：,下标：0 1 2 3 4 5 6,例如：,1.2 二叉树,1.2.3 二叉树的存储结构,2、二叉链表存储结构,1.2 二叉树,1.2.3 二叉树的存储结构,2、二叉链表存储结构,例如：,1.3 二叉树的遍历,遍历二叉树是指按某种次序访问二叉树中每个结点一次且仅一次。,1.3 二叉树的遍历,1.3.1 遍历算法的实现,1、先根序遍历（TLR） 若二叉树T不空，则(1)访问T的根结点； (2)先序遍历T的左子树；(3)先序遍历T的右子树。 2、中根序遍历（LTR） 若二叉树T不空，则(1)中序遍历T的左子树； (2) 访问T的根结点；(3)中序遍历T的右子树。 3、后根序遍历（LRT） 若二叉树T不空，则(1)后序遍历T的左子树；(2)后序 遍历T的右子树；(3)访问T的根结点。,1.3 二叉树的遍历,1.3.1 遍历算法的实现,例1.1 已知二叉树的先序和中序序列如下，试构造出相应的二叉树。 先序：ABCDEFGHIJ 中序：CDBFEAIHGJ,分析：先序序列的第一个节点是根节点，中序序列根结点处于左右子树的中序序列之间。（注意：二叉树的先序和后序序列不能唯一确定一棵二叉树，但由先序和中序或后序和中序序列能唯一确定一棵二叉树）,1.3 二叉树的遍历,1.3.2 二叉树遍历算法的应用,例1.2 设计算法按中序次序输出二叉树中度为2的结点的值。,分析：可按中序遍历的算法，但是仅输出度为2的结点(即结点的左、右孩子均不为空)，所以只要将中序遍历算法中的访问结点操作改为有条件的输出结点得知即可。,1.3 二叉树的遍历,1.3.2 二叉树遍历算法的应用,例1.3 设计算法求二叉树的结点数。,分析：由于二叉树的遍历算法对树T中每个结点都会执行一次且仅执行一次访问结点的操作，为此，可将某一遍历算法中的访问结点的操作改为计数操作，即将该结点的数目累加到一个全局变量中。,1.3 二叉树的遍历,1.3.2 二叉树遍历算法的应用,例1.4 设计算法求解给定二叉树的高度。,分析： （1）若T为空时，则其高度为0，求解结束。 （2）否则，若T不为空，其高度应是其左、右子树高度的最大值再加1，假设其左、右子树的高度能求解出来，则算法实现。而其左、右子树高度的求解又可通过递归调用本算法来完成。,例1.3 设计算法求二叉树的结点数。,1.3 二叉树的遍历,1.3.2 二叉树遍历算法的应用,1.4 线索二叉树,1.4.1 线索二叉树结构,把二叉链表中的n+1个空指针域改为指向其在某一遍历下的前驱和后继（空的左指针域指向其前驱，空的右指针域指向其后继），则这种指针称为线索，所得的二叉树则为线索二叉树，将二叉树转变成线索二叉树的过程被称为线索化。,为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。,1.4 线索二叉树,1.4.1 线索二叉树结构,即：ltag=0： lchild指示该结点的左孩子。 ltag=1： lchild指示该结点的前驱。 rtag=0： rchild指示该结点的右孩子。 rtag=1： rchild指示该结点的后继。,为了便于区分二叉链表中各结点的指针域是孩子指针还是线索，可在每个结点中增加两个区分标志ltag和rtag，约定其值为1时是线索，值为0时是孩子指针。,1.4 线索二叉树,1.4.1 线索二叉树结构,线索二叉树示例：,1.4 线索二叉树,1.4.1 线索二叉树结构,先序线索二叉树链表结构示例：,1.4 线索二叉树,1.4.2 线索二叉树中前驱、后继的求解,（1）若*P有左孩子(即P-ltag为0)，则其左子树PL中的第一个元素就是*P的后继，而PL中的先序序列的第一个结点即是其根结点，即P的左孩子(指针为P-lchild)。,1、先序线索二叉树中求解后继,（2）否则，若*P有右孩子，则其右孩子就是其后继，其指针为P-rchild。,按先序遍历，以*P为根的子树的遍历次序是*P、PL、PR，由此顺序可得：,（3）否则，P-rchild即是后继线索。,1.4 线索二叉树,1.4.2 线索二叉树中前驱、后继的求解,（1）若*P有右孩子(即P-rtag为0)，则其右子树PR中的第一个元素就是*P的后继，而PR中的第一个结点即是在以PR为根的子树中的最左下的第一个没有左孩子的结点。,2、中序线索二叉树中求解后继,（2）否则，若*P无右孩子，则P-rchild即是后继线索。,按中序遍历，以*P为根的子树的遍历次序是PL、*P、PR，由此顺序可得：,1.5 树和森林,1.5.1 树的存储结构,1、双亲表示法,树中的每个结点都有唯一的一个双亲结点，根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，数组元素为结构体类型，其中包括结点本身的信息data以及结点的双亲结点在数组中的序号parent。,类型定义： struct tnode datatype data; int parent; ; struct tnode treelistMAXNUM;,1.5 树和森林,1.5.1 树的存储结构,示例：,1.5 树和森林,1.5.1 树的存储结构,2、孩子链表表示法,其主体是一个与结点个数一样大小的一维数组，数组元素由两个域组成，一个用来存放结点信息info，另一个是指针firstchild，指向由该结点孩子组成的单链表的首位置。单链表的结点也由两个域组成，一个存放孩子结点在一维数组中的序号data，另一个是指针域next，指向下一个孩子。,链表结点类型定义： typedef struct node int data; struct node *next; listnode;,1.5 树和森林,1.5.1 树的存储结构,2、孩子链表表示法,数组元素类型定义： typedef struct datatype info; struct node *firstchild; arrelemnt;,定义数组： arrelemnt treeMAXNUM;,1.5 树和森林,1.5.1 树的存储结构,示例：,1.5 树和森林,1.5.1 树的存储结构,3、孩子兄弟链表表示法,在树中，每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点的指针firstson和下一个兄弟结点的指针nextbrother。,结点类型定义： typedef struct node datatype data; struct node *firstson，*nextbrother; tnode;,1.5 树和森林,1.5.1 树的存储结构,示例：,1.5 树和森林,1.5.2 树(森林)与二叉树的转换,1、森林到二叉树的转换,如果森林用有序表T=(T1，T2，Tm)来表示，则将森林T转换为对应的二叉树BT的形式化描述如下：,如果m=0，则BT为空；否则依次作如下操作：,（1）将T1的根作为BT的根；,（2）将T1的子树森林转换为BT的左子树；,（3）将(T2，T3，Tm)转换为BT的右子树。,1.5 树和森林,1.5.2 树(森林)与二叉树的转换,示例：,1.5 树和森林,1.5.2 树(森林)与二叉树的转换,1.5 树和森林,1.5.2 树(森林)与二叉树的转换,2、二叉树到森林的转换,将二叉树BT转换为森林T(T1，T2Tm)的形式化描述如下：,如果若BT不空，则依次执行如下操作：,（1）将BT的根转换为T1的根；,（2）将BT的左子树转换为T1的子树森林；,（3）将BT的右子树转换为（T2，Tm）。,1.5 树和森林,1.5.3 树(森林) 的遍历,1、先序遍历森林,先序遍历森林T=(T1，T2Tm)的描述如下：,若T不空，则依次执行如下操作：,（1）访问T1的根；,（2）先序遍历T1的子树森林；,（3）先序遍历森林（T2，T3Tm）；,1.5 树和森林,1.5.3 树(森林) 的遍历,1、先序遍历森林,算法如下： void preorder(Tnode *T) /先序遍历森林 if (t!=NULL) visite(T); /访问结点 preorder(T-firstson); /先序遍历T的子树森林 preorder(T-nextbrother); /先序遍历T的兄弟森林 ,1.5 树和森林,1.5.3 树(森林) 的遍历,2、后序遍历森林,后序遍历森林T=(T1，T2Tm)的描述如下：,若T不空，则依次执行如下操作：,（1）后序遍历T1的子树森林；,（2）访问T1的根；,（3）后序遍历森林（T2，