数据结构树及叉树.pptVIP

9.子孙: 以某结点为根的子树中的所有结点都被称为是该结点的子孙。 10.祖先: 从根到该结点所经分支上的所有结点。 11.结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层。 树中结点的最大层次称为树的深度或高度。 12.森林:是m(m=0)棵互不相交的树的集合。 森林与树概念相近,相互很容易转换。 13 .有序树：树中各结点的子树是按一定次序从左向右排列，且相对次序是不能随意变化的。 14.无序树:树中各结点的子树是无一定次序排列，且相对次序是可以随意变化的。 树的示意图： 树的表示方法 性质1:树中的结点数等于所有结点的度加1。 证明：根据树的定义，在一棵树中，除根结点外，每个结点有且仅有一个前驱结点， 即每个结点与指向它的一个分支一一对应，所以除树根结点之外的结点数等于所有结点的分支数（度数），从而可得树中结点数等于所有结点的度数加1。 性质3 深度为h的k叉树至多有k h-1/k-1个结点。 证明：当深度为h的k叉树上每一层均达到最多结点数时，所有结点的总和才能最大，即整个k叉树具有最多结点数。 即：k0+k1+k2+…..+k h-1= k h-1/k-1。 满二叉树：一棵深度为k 且有2k -1个结点的二叉树。 （特点：每层都“充满”了结点） 性质3 二叉树中,终端结点数n0与度为2的结点数n2有如下关系: n0=n2+1 。（实际意义：叶子数＝2度结点数＋1） 证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有： N＝n0＋n1＋n2 (6-1) 再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数， 则有：N＝B＋1。 由于这些分支都是由度为1和2的结点射出的，所以有： B＝n1+2*n2 N＝B＋1＝n1＋2×n2＋1 （6-2) 由式（6－1）和（6－2）得到：n0+n1+n2=n1+2*n2+1 n0＝n2＋1 对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质： 性质4 结点数为n的完全二叉树，其深度为 ?log2n? + l 或?log2(n+1)? 证明:设所求完全二叉树的深度为k,由完全二叉树的定义知,其前k-1层均为满的,最后一层可满,也可不满,由此可以得出如下不等式: 2k-1－1 n= 2k-1 2k-1n+1=2k 两边取对数,得:k-1log2(n+1)=k 即:log2(n+1)=klog2(n+1)+1 即:k只能取整数 所以k= ? log2(n+1) ? 性质5 在按层序编号的n个结点的完全二叉树中，任意一结点i(1≤i≤n)有： ⑴ i=1时，结点i是树的根；否则，结点i的双亲为结点 ? i/2 ? (i1) 。 ⑵ 2i＞n时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。 ⑶ 2i+1＞n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。 课堂讨论： 6.2.2 二叉树的存储结构同线性表一样，二叉树的存储结构也有顺序和链表两种结构。 讨论：不是完全二叉树怎么办？ 例2： (2) 输出二叉树disptree(Btree *root) 给定一棵二叉树，输出其嵌套括号表示 思路：首先输出根结点，然后再依次输出其左子树和右子树，不过在输出左子树之前，要输出左括号，在输出右子树之后要输出右括号；另外，依次输出的左右子树要至少有一个不为空，若均为空，就不必输出了。 void disptree(Btree *root) { if (root!=NULL) { printf(“%d”,root-data); if (root-lchild!=NULL||root-right!=NULL) { printf(“(”); disptree(root-lchild); if (root-rchild!=NULL) printf(“,”); disptree(root-right); printf(“)”); } } } 【例】:已知二叉树的先序和中序序列，构造出相应的二叉树 先序：A B C D E F G H I J 中序：C D B F E A