《《数据结构（第二版）》课件 包振宇 第五章 树》由会员分享，可在线阅读，更多相关《《数据结构（第二版）》课件 包振宇 第五章 树（65页珍藏版）》请在金锄头文库上搜索。
1、第五章 树,5.1 树的定义和术语 5.2 二叉树 5.3遍历二叉树 5.4 线索二叉树 5.5 树和森林 5.6 树的应用 5.7 典型例题,5.1 树的定义和术语,一、树的定义 树（tree）是n(n0)个结点的有限集。在一棵非空树中： （1）有且仅有一个特定的称为根（root）的结点； （2）当n1时，其余结点可分为m(m0)个互不相交的有限集（T1,T2,Tm），其中每一集合本身又是一棵树，并且称为根的子树（subtree）。,举 例,例51 （a）只有根结点的树 （b）一般的树 图5-1-1的（b）中A为根结点，其余结点分成三个互不相交的子集：T1=B，E，F，K，L，T2=C，G，
2、T3=D，H，I，J而T1，T2，T3本身又都是只有一个根结点的树。,A,L,K,E,F,G,H,I,J,D,C,B,A,M,二、树结构中的一些基本术语：,（1）结点：包含一个数据元素及若干指向其子树的分支 （2）结点的度：结点拥有子树数目称为结点的度。如图5-1-1的（b）中，A的度为3；C的度为1；M的度为0。 （3）叶子（或终端）结点：度为零的结点。 （4）分支结点（或非终端结点）：除根结点外度不为零的结点，也称为内部结点。 （5）树的度：树内各结点的度的最大值。,基本术语(续),（6）孩子：结点的子树的根称为该结点的孩子。如图5-1-1的（b）中，D为A的子树T3的根，则D是A的孩子。
3、 （7）双亲：和孩子定义相应地该结点称为孩子的双亲。如图5-1-1的（b）中，A为D的双亲。 （8）兄弟：同一个双亲的孩子之间互称兄弟。如图5-1-1的（b）中的H，I，J。 （9）祖先：从根到该结点所经过分支上的所有结点。如：M的祖先为A，D，H （10）子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如图5-1-1的（b）中B的子孙为E，F，K，L,基本术语(续),（11）层次：从根开始定义为第一层，根的孩子为第二层，依次例推。 （12）深度（或高度）：树中结点的最大层次。 （13）有序树：将树中结点的各子树看成从左到右是有序的。 无序树：树中结点的各子树没有次序的。有序树中最左边
4、的子树的根称第一个孩子，最右边的称为最后一个孩子。 （14）森林：是m(m0)棵互不相交的树的集合，对树中每个结点而言，其子树的集合即为森林。,5.2 二叉树,一、 二叉树的定义和性质： 1、定义：二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点）并且二叉树的子树有左右之分，其次序不能任意颠倒。 2、如图5-2-1所示二叉树的五种基本形态 （a） (b) (c) (d) (e),二叉树的性质,(1)性质1：在二叉树的第i层上至多有2i-1个结点（i1）。 (2)性质2：深度为k的二叉树的最大结点数为2k-1(k1)。 (3)性质3：对任何一棵二叉树T，
5、如果其终端结点数为n,度为2的结点数为 n2,则n0=n2+1 (4)一棵深度为k且有2k-1个结点的二叉树称满二叉树。 特点：每层上的结点数都为最大结点数，除终端结点外，每个结点都有两棵子树。,二叉树的性质(续),（5）完全二叉树：如深度为k，有N个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到N的结点一一对时，称之为完全二叉树。 完全二叉树的特点是：深度为k的完全二叉树，其前k-1层是一棵满二叉树，最后第k层结点都尽量排在靠左的位置上。显然一棵满二叉树一定是完全二叉树，但一棵完全二叉树不一定是满二叉树。,二叉树的性质(续),（6）完全二叉树的两个特性： 性质4：具有n
6、个结点的完全二叉树的深度为Log2n+1。 性质5：如果对一棵有n个结点的完全二叉树（其深度为Log2n+1）的结按顺序编号，则任一结点i(1in)有： 如i=1,则结点i是二叉树的根结点，若i1，则i的双亲结点为结点i/2; 如2in，则i的左孩子是结点2i，否则无左孩子； 若2i+1n，则i的右孩子是结点2i+1 ,否则无右孩子。,二叉树,二、二叉树的存储结构 （一）顺序存储结构 用一组连续的存储单元存储二叉树的数据元素，按满二叉树的结点顺序编号依次存放二叉树中数据元素。 0 1 2 3 4 5 T(6) 图5-3完全二叉树,二叉树的存储结构,（二）链式存储结构 链表的结点至少包含：数据域
7、和左右指针域的链有时还需增一指向双亲的指针域，有两个指针域的链表称为二叉链表，有三个指针域的链表称为三叉链表，如图5-5所示：,例5-3分别画出二叉树链式存储结构,5.3 遍历二叉树,一、定义： 遍历二叉树：是指如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 简言之，以一定规则将二叉树中结点排列成一个线性序列。 一般情况下，树以二叉链表的形式存储，其结点类型中定义如下： typedef struct node2 char data; struct node2 *lchild; struct node2 *rchild; TNODE2;,5.3.1 二叉树遍历的
8、方法,现将二叉树的前序遍历，中序遍历和后序遍历方法列出如下（递归定义方法） 1.前序遍历： 访问要结点； 按前序遍历根结点的左子树； 按前序遍历根结点的右子树；,2.中序遍历： 按中序遍历根结点的左子树； 访问根结点； 按中序遍历根结点的右子树； 3.后序遍历： 按后序遍历根结点的左子树； 按后序遍历根结点的右子树； 访问根结点；,例54,用三种不同方法遍历图5-9所示的二叉树得： 前序遍历结果为：124753689 中序遍历结果为：742513869 后序遍历结果为：745289631,具体的遍历函数(递归算法 ),前序遍历： void re_preorder(t node2 *t) if
9、(t!=null) printf(“%c”,t-data); re_preorder(t-lchild); re_preorder(t-rchild); ,2、中序遍历 void re_midorder(tnode2 *t) if(t!=null) re_midorder(-lchild); printf(“%c”,t-data); re_midorder(t-rchild); ,3、后序遍历 void re_posorder(tnode2 *t) if (t!=null) re_posorder(t -lchild); re_posorder(t-rchild); printf(“%c”,t
10、-data); ,具体的遍历函数(非递归算法),如不用递归方法编写，可引入栈，以中序遍列为例，使用链接栈编写的中序遍历函数定义如下： typedef struct snode tnode2 * tnodept;/*栈结点为指向二叉树结点的指针*/ struct snode *link;/*栈结点链接指针*/ void st_midorder(tnode2 *t) snode top=null,/*栈顶指针*/ *p;/*工作变量*/ while(t!=null| top!=null) while(t!=null)/*一棵二叉树还未访问完，循环*/ /*根结点进栈*/ p=(snode *)ma
11、lloc(sizeof(snode); p-tnodept=t; p-link=top;,top=p; /*沿着左子树前进，将经过的结点依次进栈*/ t=t-lchild; if(top!=null) /*如栈非空*/ t=top-tnodept; /*栈顶结点出栈*/ p=top; top=top-link; free(p); /*释放栈顶结点的空间*/ printf (“%c”,t-data); /*访问根结点*/ t=t-rchild; /*向右子树前进*/ ,5.4 线索二叉树,5.4.1、建立线索二叉树 遍历二叉树是得到一线性序列，使每结点（除第一和最后一个外）有且仅有一个直接前驱和
12、直接后继。 以如下结点构成的二叉链表作为二叉树的存储结构叫线索链表,线索：指向结点前驱和后继的指针叫线索。 线索二叉树：加上线索的二叉树 线索化：对二叉树以某种次序遍历使其为线索二叉树的过程。,0 lchild域指示结点的左孩子 ltag= 1 lchild域指示结点的前驱 0 rchild域指示结点的右孩子 rtag= 1 rchild域指示结点的后继,构造线索二叉树的步骤,构造线索二叉树的步骤为： 第一步：根据中序遍历得二叉树遍历序列为：a+b*c-d-e/f 第二步：以“孩子优先”的原则，结合中序遍历序列构造线索链表，有左（或右）孩子的结点对应标志位ltag(或rtag)置0，相应指针l
13、child(或rchild)指向左（或右）孩子；否则ltag(或rtag)置1，lchild(或rchild)指向前驱（或后继）, ,如图5-12，算法对应于图5-13。 第三步：根据线索链表构造线索二叉树，如图5-11。,例 5-10,例5.5：以中序遍历为例构造线索二叉树和线索链表。,5.5 树和森林,5.5.1、树的存储结构 三种常用的链表结构 双亲表示法 假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置，其形式说明如下： #define MAX 500 struct node int data , parent; ; typedef struc
14、t node NODE; NODE tMAX;,双亲表示法示例,孩子表示法：,把每个结点的孩子结点排列起来，看成一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空表），而n个头指针又组成一个线性表。图5-5-1中树的孩子表示法有两种一是孩子链表表示法（如图5-15），另一种是带双亲的孩子链表表示法（如图5-16）,孩子链表表示法,带双亲的孩子链表表示法,孩子兄弟表示法,又称二叉树表示法，或二叉链表表示法，即以二叉链表作树的存储结构。链表中的结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。,树与二叉树的转换（通过二叉链表存储联系）,示图,A,E,C,B,
15、D,A,B,C,D,E,A,B,C,E,D,森林转换成二叉树,如果F=T1，T2，Tm是森林，按如下原则换成一棵二叉树B (1)若F为空，即m=0,则B为空二叉树； (2)若F非空，即m0，则B的根root即为森林中第一棵T的根；B的左子树是从T1中根结点的子树森林F1=T11，T12，T1m转换成的二叉树；其右子树是以森林F=T2，T3，Tm转换成的二叉树。,二叉树转换成森林,如B是一棵二叉树，则可按如下原则转换成森林F (1)若B为空，则F为空； (2)若B非空，则F中第一棵T1的根为二叉树B的根；T1为根结点的子树森林F1是B的左子树转换而成的森林；F中除T1之外其余树组成的森林F=T2
16、，T3，Tm是由B的右子树转换而成的森林。F中除T1之外其余树组成的森林F=T2，T3，Tm是由B的右子树转换而成的森林。,举例 P70,71,5.6 树应用,一、二叉排序树 1、什么是二叉排序树？ 二叉排序树是一棵空树或具有下列性质的二叉树。 (1)若它的左子树不空，则左子树上所有结点的值均小于（或大于）它的根结点的值。 (2)若它的右子树不空，则右子树上的所有结点的值均大于等于（或小于等于）它的根结点的值。 (3)它的左、右子树也分别为二叉排序树。 2、二叉排序树（又称二叉查找树）的构造：根据二叉排序树的性质，每次都按结点大小从根结点查找到对应的插入位置插入。,例 5-6,例5.6：有一组结点的关键字大小分别为：45、
