《计算计算法第8章》由会员分享，可在线阅读，更多相关《计算计算法第8章（23页珍藏版）》请在金锄头文库上搜索。
1、第八章 树、图和排序 第8章 树、图和排序 8.1 树8.2 图8.3 排序习题六 第八章 树、图和排序 8.1 树的基本概念和术语 8.1.1 树的定义树(tree)是由一个或多个结点组成的有限集合T。其中：(1) 一个特定的结点称为该树的根(root)结点；(2) 结点之外的其余结点可分为m(m0)个互不相交的有限集 合T1，T2，Tm，且其中每一个集合本身又是一棵树，称之 为根的子树(subtree)。这是一个递归的定义，即在定义中又用到了树这个术语。 它反应了树的固有特性。可以认为仅有一个根结点的树是最小 树，树中结点较多时，每个结点都是某一棵子树的根。 第八章 树、图和排序 图8.1
2、 树举例第八章 树、图和排序 8.1.2 二叉树的定义二叉树(binary tree)是n(n0)个结点的有限集合。它或为空树(n=0)，或为非空树。对于非空树有：(1) 有一个特定的称之为根的结点。(2) 除根结点以外的其余结点分为两个互不相交的称之为左子树和右子树的二叉树。这个定义是递归的。由于左、右子树 也是二叉树， 因此子树也可为空树。图8.3中展现了五种不同基本形态的二叉树。 第八章 树、图和排序 图8.2 二叉树的五种基本形态 其中(a)为空树，(b)为仅有一个结点的二叉树，(c)是仅有左子树而右子树为空的二叉树，(d)是仅有右子树而左子树为空的二叉树，(e)是左、右子树均非空的二
3、叉树。这里应特别注意的是，二叉树的左子树和右子树是严格区分并且不能随意颠倒的，图 8.2(c)与图8.2(d)就是两棵不同的二叉树。 第八章 树、图和排序 现在介绍两种特殊形态的二叉树，它们是满二叉树和完全二叉树。深度为k并且含有2k-1个结点的二叉树称为满二叉树，如图8.3(a)所示。对满二叉树的结点可以从根结点开始自上向下，自左至右顺序编号，图8.3(a)中每个结点斜上角的数字即是该结点的编号。深度为k，含有n个结点的二叉树，当且仅当每个结点的编号与相应满二叉树结点顺序编号从1到n相对应时，则称此二叉树为完全二叉树，如图8.3(b)所示。而图8.3(c)则不是完全二叉树。 第八章 树、图和
4、排序 图8.3 满二叉树和完全二叉树 (a) 满二叉树；(b) 完全二叉树；(c) 非完全二叉树 第八章 树、图和排序 8.1.3 二叉树树的链表存储结构用于二叉树存储的链表结构，常见的有二叉链表和三叉链表。二叉链表的每个结点有一个数据域和两个指针域，一个指针指向左孩子，另一个指针指向右孩子。结点结构描述如下：typedef struct node int data; /*数据域*/struct node *lch, *rch; /*左、右指针域*/Bnode; 第八章 树、图和排序 三叉链表的结点比前者多了一个指向双亲的指针域。结点结构描述如下：typedef struct node3 in
5、t data; /*数据域*/struct node3 *lch, *par， *rch; /*par是双亲指针域*/ Bnode3; 第八章 树、图和排序 图8.4 二叉树的链表存储结构 第八章 树、图和排序 8.3 遍历二叉树 遍历二叉树是指以一定的次序访问二叉树中的每个结点，并 且每个结点仅被访问一次。所谓访问结点是指对结点进行各种操 作的简称。例如，查询结点数据域的内容，或输出它的值，或找 出结点位置，或是执行对结点的其他操作。遍历二叉树的过程实 质是把二叉树的结点进行线性排列的过程。假设遍历二叉树时访 问结点的操作就是输出结点数据域的值，那么遍历的结果得到一 个线性序列。由于二叉树有
6、左、右子树，因此遍历的次序不同， 得到的结果就不同。令L代表遍历左子树，T代表访问根结点，R 代表遍历右子树，则对一棵二叉树的遍历可以有六种不同次序： LTR，LRT，TLR，TRL，RLT，RTL。然而经常用到的总是先左 (L)后右(R)，若再把访问根结点(T)的操作穿插于其中，则只有三 种不同的遍历次序：LTR、TLR 和 LRT。它们分别称作中根遍历 二叉树、先根遍历二叉树和后根遍历二叉树。 第八章 树、图和排序 二叉树选择不同的存储结构，遍历算法的程序代码会有所不同。这里确定用二叉链表作为存储结构，树中结点的结构定义如下：typedef struct node char data； /
7、*假设数据类型是char,根据需要也可为其他类型*/struct node *lch，*rch；Bnode;二叉树结点的类型名就是Bnode(Binary node)。 第八章 树、图和排序 8.3.1 先根遍历先根遍历可以递归的描述如下：如果根不空，则(1) 访问根结点；(2) 按先根次序遍历左子树；(3) 按先根次序遍历右子树；否则返回。在理解和认识遍历算法时，务必分辨清楚“访问”与“遍历”是两个不同的概念，“访问”操作是针对一个结点，“遍历”操作是针对一棵树。 第八章 树、图和排序 算法 8.1void preorder(Bnode *p) if (p!NULL) printf (“%6
8、c“，p-data)； /*访问根结点*/preorder(p-lch)； /*按先根次序遍历左子树*/preorder(p-rch)； /*按先根次序遍历右子树*/* preorder */ 第八章 树、图和排序 8.3.2 中根遍历中根遍历递归的思路与先根遍历十分相似，只是在根不空的情况下所应执行的三条操作稍做调整即可。具体来说，也 就是把第(1)条与第(2)进行条对换。中根遍历可以递归的描述如下：如果根不空，则(1) 按中根次序遍历左子树；(2) 访问根结点；(3) 按中根次序遍历右子树；否则返回。 第八章 树、图和排序 算法 8.2void inorder( Bnode *p) if
9、(p!NULL) inorder(p-lch)； /*中遍历左子树*/printf(“%6c“，P-data)； /*访问根结束*/inorder(p-rch)； /*中根遍历右子树*/* inorder */ 第八章 树、图和排序 8.3.3 后根遍历在搞清楚先根遍历，中根遍历递归方法之后，可以看出，只要将访问根结点的语句移至遍历左子树、右子树的语言后面即可得出后根遍历递归算法。后根遍历可以递归的描述如下：如果根不空，则(1) 按后根次序遍历左子树；(2) 按后根次序遍历右子树；(3) 访问根结点；否则返回。 第八章 树、图和排序 算法 8.3Void postorder( Bnode *p
10、) if (p!NULL) postorder(p-lch)； /*后根遍历左子树*/postorder(p-rch)； /*后根遍历右子树*/printf(“%6c“，p-data)；/*访问根结点*/ /* postorder */ 第八章 树、图和排序 8.3.4 按层遍历二叉树算法 8.4viod levelorder(Bnode *p) Bnode *q20;front=0; rear=0;if( p!=NULL) rear+; qrear=p; /*根结点不空，进队*/while ( front!=rear) front +; p=qfront; printf(“%6c“,p-da
11、ta); /*出队并访问*/*若左孩子不空，进队*/if( p-lch!=NULL) rear+; qrear=p-lch;/*若右孩子不空，进队*/if( p-rch!=NULL) rear+; qrear=p-rch; /* levelorder */ 第八章 树、图和排序 习 题 六 1对于三个结点A，B，C，可组成多少种不同的二叉树？请画出。2如果一棵树有n1个度为1的结点，n2个度为2的结点nm个度为m的结点，则该树共有多少个叶子结点(n0?)。可参考二叉树性质(3)的证明方法来思考m叉树问题。 第八章 树、图和排序 3写出图8.25中所示的树的叶子结点，非终端结点，各结点的度和树深。 图8.5 树T 第八章 树、图和排序 4将图8.6二叉树按先根、中根、后根次序遍历的结点序列。 图8.6 二叉树 第八章 树、图和排序 5写一个算法求二叉树中结点总数6现有按后根遍历二叉树的结果为C，B，A，有几种不同的二叉树可以得到这一结果。7现有按先根和中根遍历某二叉树的结果，试画出这棵二叉树，形状惟一吗？为什么？先根遍历：ABCDEFGHI，中根遍历：BCAEDGHFI。
