1、树和二叉树.doc

第五章 树和二叉树 5.1树的概念 树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树 　　　　　　　　　 ??? 1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。　　2.树的深度——组成该树各结点的最大层次，如上图，其深度为4；　　3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；　　4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。??? 5.树的表示　　树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：　　　　(A(B(E(K,L),F),C(G),D(H(M),I,J)))5. 2 二叉树　　1.二叉树的基本形态：　　二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：　　　　　 　　(1)空二叉树——(a)；　　(2)只有一个根结点的二叉树——(b)；　　(3)右子树为空的二叉树——(c)；　　(4)左子树为空的二叉树——(d)；　　(5)完全二叉树——(e)注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。　　 2.两个重要的概念：　　(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；　　(2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树。　　如下图：　　　　　　　　　　　　　　　完全二叉树 　 满二叉树3.二叉树的性质　　 (1) 在二叉树中，第i层的结点总数不超过2^(i-1)； ???? (2) 深度为h的二叉树最多有2h-1个结点(h=1)，最少有h个结点；　　 (3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2， ?????????? 则N0=N2+1； (4) 具有n个结点的完全二叉树的深度为int（log2n）+1?　　(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：　　若I为结点编号则 如果I1，则其父结点的编号为I/2；　　　　如果2*I=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*IN，则无左儿子；　　　　如果2*I+1=N，则其右儿子的结点编号为2*I+1；若2*I+1N，则无右儿子。.二叉树的遍历运算（递归定义）　　　(1)先序遍历　　　　　　访问根；按先序遍历左子树；按先序遍历右子树　　　(2)中序遍历　　　　　　按中序遍历左子树；访问根；按中序遍历右子树　　　(3)后序遍历　　　　　　按后序遍历左子树；按后序遍历右子树；访问根. 一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（?? ）。 A．0???????? B.???? 2???????? C.???? 4???????? D.???? 6 . 已知7 个结点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为结点的编号，以下同），后根遍历是4 6 5 2 7 3 1，则该二叉树的可能的中根遍历是（ ） A. 4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7 C. 4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3 4. 表达式a*(b+c)-d的后缀表达式是： A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd 5、一个包含n个分支结点（非叶结点）的非空满k叉树，k=1，它的叶结点数目为： A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+1 6．完全二叉树共有2*N-1个结点，则它的叶节点数是（ ）。 A. N-1 B. 2*N C. N D. 2N-1 E. N/2 2