第十章树和二叉树.ppt

《第十章树和二叉树.ppt》由会员分享，可在线阅读，更多相关《第十章树和二叉树.ppt（113页珍藏版）》请在三一文库上搜索。

1、族谱,树是以分支关系定义的层次结构。,第十章 树,树型结构是一类重要的非线性结构。,学习重点:,树的基本概念,二叉树的基本概念、相关操作,树和森林与二叉树之间的相互转换,二叉树的应用,第十章 树,树的定义和基本术语,树(Tree) : 是具有层次结构的 n(n0) 个结点的有限集。,第十章 树,树(Tree) : 是 n(n0) 个结点的有限集。,n0 ，有且仅有一个称为根的结点。,n1 ，除根结点外，其余结点可分为 m(m0) 个互不相交的有限子集 T1 ,T2 ,Tm ，其中每个子集都称为根结点的子树 。,第十章 树和二叉树,基本术语 结点(node)表示树中的元素，包括数据项及若干指向其

2、子树的分支 结点的度(degree)结点拥有的子树数 叶子(leaf)度为0的结点 孩子(child)结点子树的根称为该结点的孩子 双亲(parents)孩子结点的上层结点叫该结点的 兄弟(sibling)同一双亲的孩子 树的度一棵树中最大的结点度数 深度(depth)树中结点的最大层次数,第十章 树和二叉树,结点A的度：3 结点B的度：2 结点M的度：0,叶子：K，L，F，G，M，I，J,结点A的孩子：B，C，D 结点B的孩子：E，F,结点I的双亲：D 结点L的双亲：E,结点B，C，D为兄弟 结点K，L为兄弟,树的度：3,结点A的层次：1 结点M的层次：4,树的深度：4,结点F，G为堂兄弟

3、结点A是结点F，G的祖先,第十章 树和二叉树,树的其它表示方法,a. 嵌套集合,大集合表示树，小集合表示子树，相互嵌套。,第六章 树,b. 层次表示法,类似书的编目,第六章 树,二叉树,二叉树的定义,二叉树是 n(n0) 个结点的有限集，它或者是空集，或者是由一个根和称为左、右子树的两个互不相交的二叉树组成。,二叉树是一个递归定义。,树的子树次序不作规定，二叉树的两个子树有左、右之分。,树中结点的度没有限制，二叉树中结点的度只能取 0、1、2。,根,第十章 树和二叉树,根据定义，二叉树通常具有 5 种基本形态:,关于树的基本术语也都适用于二叉树。,二叉树与树的区别 树：1、树最少有一个根结点（

4、n0） 2、树的度 0 3、树不要求子树顺序 二叉树： 1、二叉树可以为空(n 0) 2、二叉树的度2 3、二叉树是有序树，有左、右子树之分。 例10-1：试写出具有3个结点的所有不同形态的树和二叉树。,二叉树的性质,性质1 : 在二叉树的第 i 层上至多有 2i-1 个结点(i1)。,归纳法证明:,(1) i = 1，只有一个根结点，2i-1 = 20 = 1，正确；,(2) 假设 i-1 成立，即第 i-1 层上至多有 2i-2 个结点；,(3) 由于二叉树的结点的度至多为 2 ，故在第 i 层上的最大结点数为第 i-1 层上的最大结点数的 2 倍，即2 2i-2 = 2i-1 。,性质2

5、 : 深度为 k 的二叉树至多有 2k 1 个结点(k1) 。,练习: 归纳法证明。,引论: 一棵树有 n 个结点，则必有 n 1 条分支。,证明:,除根结点外，其它结点都有一个分支进入，,设 B 为分支总数，故 n = B + 1 ，,故 B = n - 1,得证。,性质3 : 对任何一棵二叉树 T ，如果其终端结点数为 n0，度为 2 的结点数为 n2 ，则 n0 = n2 + 1 。,证明:,(1),已知，终端结点数为 n0 ，度为 2 的结点数为 n2 ，,设度为 1 的结点数为 n1 ，,由于二叉树中的所有结点的度只能为 0、1、2 ，,故二叉树的结点总数为 n = n0 + n1

6、+ n2 ；,(2),除根结点外，其它结点都有一个分支进入，,设 B 为分支总数，故 n = B + 1 ，,由于这些分支均是由度为 1 或 2 的结点引出的，,所以有 B = n1 + 2n2 ，故 n = n1 + 2n2 + 1 ，,由 (1) 和 (2) ，可得 n0 + n1 + n2 = n1 + 2n2 + 1 ，,故有 n0 = n2 + 1 。,两种特殊形态二叉树: 满二叉树、完全二叉树。,一棵深度为 k 且有 2k-1 个结点的二叉树称为满二叉树。,特点:,(1) 每一层的结点数都达到最大结点数。,(2) 叶子结点在最大层。,(3) 任一结点，其左、右分支下的子孙的最大层次

7、相等。,对满二叉树的结点进行连续编号，从根结点起，自上而下，自左至右，1、2、3、 、2k-1 。,深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称为完全二叉树。,非完全二叉树,完全二叉树(1),特点:,(1) 叶子结点只可能在层次最大的两层上出现。,(2) 对任一结点，若其右分支的子孙的最大层次为 l ，则其左分支下的子孙的最大层次必为 l 或 l+1。,完全二叉树(2),满二叉树和完全二叉树的区别： 1、满二叉树一定是完全二叉树，它是完全二叉树的特例。 2、完全二叉树不一定是满二叉树。 3、满二叉树中n1=0，

8、完全二叉树中n1=0或1.,证明:,设 n 结点完全二叉树的深度为 k ，,因为，,故 2k-1-1 n 2k-1,有 2k-1 n 2k,又 k-1 log2n k,(2) 如果 2i n，则结点 i 的左儿子 LChild(i) 是结点 2i ；否则无左儿子。 /求左儿子,(3) 如果 2i+1 n，则结点 i 的右儿子 RChild(i) 是结点 2i+1 ；否则无右儿子。 /求右儿子,证明 (1) : 如果 (2)、(3) 成立，则 (1) 成立。,证明 (2) 和 (3) :,归纳法,若有左儿子，应为 2i = 2；,i = 1: 根结点,若有右儿子，应为 2i + 1 = 3；,设

9、对结点 i 成立，即结点 i 的左儿子为结点 2i，右儿子为结点 2i+1；,求证对结点 i+1 也成立:,完全二叉树中，结点 i 和结点 i+1 之间的关系通常有两种情况，或在同一层上，或分别在相邻两层上，且最左和最右。,情况 2,结点 i+1 的儿子的序号一定紧挨在结点 i 的儿子的序号的后面，,根据归纳假设，结点 i 的儿子的序号为 2i 和2i+1，,则结点 i+1 的左、右儿子的序号应为2i+2=2(i+1)、2i+3=2(i+1)+1。,若 2(i+1)+1n 则无右儿子，若 2(i+1)n 则无左儿子。 得证。,二叉树的存储结构 (顺序、链式),1. 顺序存储结构,用一组地址连续

10、的存储单元依次自上而下、自左至右存储二叉树上的结点元素。,# define MAX_TREE_SIZE 100 typedef TElemType SqBiTreeMAX_TREE_SIZE,完全二叉树: 编号为 i 的元素存储在数组下标为 i-1 的分量中；,一般二叉树: 对照完全二叉树，存储在数组的相应分量中；,在最坏情况下，深度为 k 的右单支二叉树需要 2k-1 个存储空间。,结论: 顺序存储结构适用于存储完全二叉树。,空间浪费,1,2,3,4,5,0,0,0 表示不存在此结点,0 1 2 3 4 5 6 7,0 1 2 3 4 5 6 7,例10-3 一个深度为K且只有K个结点的二叉

11、树顺序存储最多需要多少个存储空间？最少需要多少个？ 例10-4 一个完全二叉树结点个数为1000，则n0、n1、n2和高度h各为多少？,2. 链式存储结构,D ( root，DL，DR )。,链表结点包含 3 个域 : 数据域、左指针域、右指针域,由这种结点结构得到的二叉树存储结构称为二叉链表。,二叉链表存储表示,TElemType data ；,struct BitNode * lchild ，* rchild ；,有时还可以在结点结构中增加一个指向父亲的指针。,data,lchild,rchild,采用何种存储结构，依赖于进行何种操作,基本操作 P:,InitBiTree ( &T ),D

12、estroyBiTree ( &T ),CreateBiTree ( &T),BiTreeEmpty ( T ),InsertChild ( T ，A，X ),操作: 二叉树 T 存在，向 T 中插入一个信息域为 A 的结点，作为 T 中信息域为 X 的结点的左儿子，而其原来的左子树为新结点的左子树 。,DeleteChild ( T ，p，LR ),操作: 根据 LR 为 0 或 1 ，删除 T 中 p 所指结点的左或右子树。,PreOrderTraverse ( T ，visit() ),操作: 先序遍历二叉树 T 。,InOrderTraverse ( T ，visit() ),操作:

13、中序遍历二叉树 T 。,PostOrderTraverse ( T ，visit() ),操作: 后序遍历二叉树 T 。,LevelOrderTraverse ( T ，visit() ),操作: 层次遍历二叉树 T 。,二叉树的基本操作,遍历二叉树,遍历二叉树 : 如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。,D ( root，DL，DR )。,如果能依次遍历这三部分，就可以遍历整个二叉树；,设以 D、L、R 分别表示访问根结点、遍历左子树、遍历右子树，则可以存在 6 种遍历方案: DLR、DRL、 LDR、LRD、RDL、RLD；,若限定先左后右的原则，

14、则只有 3 种情况: 先(根)序遍历、中(根)序遍历、后(根)序遍历。,LDR、LRD、DLR RDL、RLD、DRL,先(根)序遍历:,若二叉树为空，则返回；否则,(1) 访问根结点；,(2) 先(根)序遍历左子树；,(3) 先(根)序遍历右子树；,A B C,D L R,先序遍历序列：A B D C,先序遍历:,printf(T-data) ;,PreOrderTraverse ( T-lchild) ;,PreOrderTraverse ( T-rchild) ;,Status PreOrderTraverse ( BiTree T),算法 10.1 先序遍历递归算法,else retu

15、rn OK ;,算法的C语言实现： void PreOrderTraverse ( BiTree T) if(T!=NULL) printf(“%dt“,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); ,先序遍历,begin,end,先序遍历顺序:,A,B,D,F,G,C,E,H,中(根)序遍历:,若二叉树为空，则返回；否则,(2) 访问根结点；,(1) 中(根)序遍历左子树；,(3) 中(根)序遍历右子树；,B A C,L D R,中序遍历序列：B D A C,中序遍历:,printf(T-data) ;,In

16、OrderTraverse ( T-lchild) ;,InOrderTraverse ( T-rchild) ;,算法 10.2 中序遍历递归算法,中序遍历,begin,end,中序遍历顺序:,A,B,D,F,G,C,E,H,后(根)序遍历:,若二叉树为空，则返回；否则,(3) 访问根结点；,(1) 后(根)序遍历左子树；,(2) 后(根)序遍历右子树；,B C A,L R D,后序遍历序列： D B C A,后序遍历:,printf(T-data) ;,PostOrderTraverse ( T-lchild) ;,PostOrderTraverse ( T-rchild) ;,算法 10

17、.3 后序遍历递归算法,后序遍历,begin,end,后序遍历顺序:,F,G,D,B,H,E,C,A,例，表达式 a + b * c d / e,先序遍历:, + a * b c / d e,前缀式，波兰式,中序遍历:,a + b * c d / e,中缀式，算术表达式,后序遍历:,a b c * + d e / -,后缀式，逆波兰式,中缀表示: 适于人的思维,后缀表示: 适于计算机的思维,a + b * c d / e,a b c * + d e / -,begin,end,中序遍历顺序:,A,B,D,F,G,C,E,H,用栈实现中序遍历的非递归算法,栈用来打印结点信息及访问右子树,Init

18、Stack (S) ; p=T ;,pop (S, p) ;,p=p-rchild ; /遍历右子树,Return OK;,printf (p-data) ; /打印根结点,用C语言实现中序遍历的非递归算法 void InOrderTraverse ( BiTree T ) int i=0; BiTree p,sM; p=T; while(p!=NULL|i0) if(p) /如果当前结点非空 si+=p; /则当前结点入栈 p=p-lchild; /然后将p的左子树作为新的当前结点(遍历左子树) else p=s-i; /否则弹出当前栈顶元素 printf(“%dt”,p-data); /输

19、出元素的值 p=p-rchild; /然后将p的右子树作为新的当前结点(遍历右子树) ,begin,end,中序遍历顺序:,A,B,D,F,G,C,E,H,例，,对二叉树除可以进行先序、中序、后序的遍历外，还可以进行层次遍历。,层次遍历: H , C , D , F , E , A,过程:,打印 H；,打印 H 的左儿子 C；,打印 C 的左、右儿子 F、E；,打印 D 的左、右儿子 A；,打印 H 的右儿子 D；,队列实现层次遍历,H,H,C,D,C,F,E,D,A,F,E,A,EnQueue(Q , T) ;,While ( ! QueueEmpty(Q) ) ,Return OK;,pr

20、intf (p-data) ; /打印结点,DeQueue(Q , p) ;,EnQueue(Q , p-lchild ) ;,EnQueue(Q , p-rchild ) ;,H,A,占用了六个空间,H,A,二叉树插入操作,利用遍历可以实现二叉树的插入、删除操作。,InsertChild ( T ，A，X ),操作: 二叉树 T 存在，向 T 中插入一个数据域为 X 的结点，作为 T 中数据域为 A 的结点的左儿子，而其原来的左子树为新结点的左子树 。,思想:,1. 首先找到数据域为 A 的结点 p 。,2. 建立数据域为 X 的新结点 q 。,3. q-lchild = p-lchild

21、。,4. p-lchild = q 。,/找到信息域为 A 的结点 p 。,q-lchild = p-lchild ；,p-lchild = q ；,InitStack (S) ; p=T ;,Pop (S, p) ;,p=p-rchild ; /遍历右子树,Return ERROR;,if ( p-data = A ) return OK; /找到结点,/用中序遍历的方法，找到信息域为 A 的结点 p 。,性质: 含有 n 个结点的二叉链表中有 n+1 个空链域。,证明:,(1),设，终端结点数为 n0 ，,度为 1 的结点数为 n1 ，,故二叉树的结点总数为 n = n0 + n1 + n

22、2 ；,度为 2 的结点数为 n2 ，,(2),空链域个数为 2n0 + n1 ，,已知，n0 = n2 + 1 ，,故， 2n0 + n1,= n0 + n1 + n2 + 1,= n + 1,树和森林,树的存储结构,父亲表示法,儿子表示法,链式存储,顺序存储,父亲儿子表示法,二叉树表示法,一. 父亲表示法,用一组地址连续空间存储树的结点，每个结点由两个域组成。,数据域,指示器，指向其父结点,R -1,A 0,B 0,C 0,D 1,E 1,F 3,G 6,H 6,K 6,无父结点,父结点为R,父结点为A,TElemType data ； /数据域,int father ； /指示器，指向其

23、父结点,# define MAX_TREE_SIZE 100 /定义最大结点数,PTNode nodesMAX_TREE_SIZE ； /顺序结构存储,int r ，n ； /根的位置和结点总数,树的父亲表示法存储表示,结构特点:,优: 获取祖先结点(根结点)比较方便,缺: 获取某个结点的儿子结点需要遍历整个结构,二. 儿子表示法,1. 多叉树表示法链式存储,链表中的结点存在两种格式:,每个结点均采用定长格式，n 为树的度。,每个结点采用变长格式，degree = n 为该结点的度。,定长操作方便，变长操作不方便,结构分析,定长浪费空间，变长节省空间,采用定长存储格式，链表中存在很多空链域，造

24、成空间浪费。,定义: 在一棵有 n 个结点，度为 k 的树中必有 (k-1)n+1 个空链域。,证明:,(1),设树中空链域总数为 X,(2),另外除根结点外，其它结点都有一个分支进入，,设 B 为分支总数，故 n = B + 1 ，,= kn - B,= kn (n-1),= (k1)n+1,得证,2. 顺序存储,把每个结点的儿子结点以单链表的结构存储 ；,则 n 个结点就构成了 n 条儿子单链表 ；,将 n 条单链表头指针以顺序线性表存储 ；,int child ；,struct CTNode * next ；,TElemType data ；,ChildPtr firstchild ；,

25、CTBox nodesMAX_TREE_SIZE ；,int r ，n ； /根的位置和结点总数,优点: 方便搜索儿子结点,缺点: 查找父结点需要从头遍历整个顺序表,三. 父亲儿子表示法,如何既能方便搜索儿子结点，又能方便查找父结点？,四. 二叉树表示法,将树以二叉树的形式表示。,令结点的两个链域分别指向该结点的第一个儿子和右边的兄弟。,TElemType data ；,struct CSNode * firstchild ；,struct CSNode * nextsibling ；,查找结点的儿子:,沿结点的 firstchild 域可找到第一个儿子，,然后再沿 nextsibling 域

26、可找到其它儿子。,查找结点的兄弟:,沿结点的 nextsibling 域可找到所有兄弟。,查找结点的父亲:,为每个结点增加一个 father 域指向父结点。,性质:,1. 树可以表示成二叉树的形式,启示: 树与二叉树的转换,2. 树转换成一棵只有左子树的二叉树,森林与二叉树的转换,(1). 任何一棵树都可以转换为一棵没有右子树的二叉树。,(2). 森林是由若干棵树构成的集合，若把森林中第二棵树的根结点看成是第一棵树的根结点兄弟，就可以导出森林与二叉树的转换。,1. 森林转换成二叉树,(1) 增加一个根结点，作为原森林中各树根结点的父结点。,(2) 将新树转换成二叉树。,(3) 删除二叉树的根结

27、点。,2. 二叉树转换成森林,(1) 增加一个新根结点，原二叉树根结点做为新根结点的左儿子。,(2) 将新二叉树转换成树。,(3) 删除树的根结点变为森林。,2. 二叉树转换成森林,(1) 增加一个新根结点，原二叉树根结点做为新根结点的左儿子。,(2) 将新二叉树转换成树。,(3) 删除树的根结点变为森林。,森林和树的遍历,1. 分割,从结构上，可以把任意的森林分成三部分:,1) 第一棵树的根结点。,2) 第一棵树根结点的子树构成的森林。,3) 其余的树构成的森林。,按这三部分的不同排列次序可把森林的遍历次序分为前序、中序、后序。,2) 访问第一棵树的根结点。,3) 按前序遍历根结点的子树构成

28、的森林。,4) 按前序遍历其余的树构成的森林。,森林的前序遍历,1) 如果森林中树的个数为 0 ，则返回。,A,B,C,D,E,F,G,H,I,J,3) 访问第一棵树的根结点。,2) 按中序遍历第一棵树根结点的子树构成的森林。,4) 按中序遍历其余的树构成的森林。,森林的中序遍历,1) 如果森林中树的个数为 0 ，则返回。,B,C,D,A,F,E,H,J,I,G,4) 访问第一棵树的根结点。,2) 按后序遍历第一棵树根结点的子树构成的森林。,3) 按后序遍历其余的树构成的森林。,森林的后序遍历,1) 如果森林中树的个数为 0 ，则返回。,B,C,D,F,H,J,I,G,E,A,森林的前、中、后

29、序遍历与对应二叉树的前、中、后序遍历一致。,树的应用,1. 二叉分类树(二叉排序树),2. 判定树,3. 赫夫曼树(最优二叉树),赫夫曼树 Huffman (最优二叉树),基本概念:,从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。,路径上的分支数目称做路径长度。,X 到 Y 的路径,路径长度为 2,树的路径长度是从树根到每一个结点的路径长度之和。,在具有相同结点数的所有二叉树中， 的路径长度是最短的。,完全二叉树,推广：为结点加权 w 。,结点的带权路径长度为从根结点到该结点之间的路径长度与结点上权值的乘积。,wk 为叶子结点 vk 的权值,L(vk )为叶子结点 vk 的路径

30、长度,例，3 棵二叉树，都有 4 个叶子结点 a、b、c、d，分别带权7、5、2、4，求它们各自的带权路径长度。,(1) WPL =,72 + 52 + 22 + 42 = 36,(2) WPL =,73 + 53 + 21 + 42 = 46,(3) WPL =,71 + 52 + 23 + 43 = 35,假设有n个权值 w1,w2, wn ，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为 wi ，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。,如何构造赫夫曼树？,(1) 根据给定的 n 个权值 w1,w2, wn 构成 n 棵二叉树的集合 F = T1,T2, Tn

31、，其中每棵二叉树 Ti 中只有一个权值为 wi 的根结点。,(2) 在 F 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树根结点的权值之和。,(3) 在 F 中删除这两棵树，同时将新得到的二叉树加入集合 F 中。,(4) 重复 (2) 和 (3) ，直到 F 中只含一棵树为止。,例， 4 个叶子结点 a、b、c、d，分别带权7、5、2、4。,赫夫曼编码,1. 编码,例，传送 ABACCD，四种字符，可以分别编码为 00,01,10,11。,则原电文转换为 00 01 00 10 10 11。,对方接收后，采用二位一分进行译码。,电文,编码

32、,二进制,二进制,译码,电文,当然，为电文编码时，总是希望总长越短越好，,如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用较短的编码，则可以减短电文的总长。,则原电文转换为 0 00 0 1 1 01。 减短了。,问题:,如何译码？,前四个二进制字符就可以多种译法。,AAAA,BB,2. 前缀编码,若设计的长短不等的编码，满足任一个编码都不是另一个编码的前缀，则这样的编码称为前缀编码。,例， A , B , C , D 前缀编码可以为 0 , 110 , 10 , 111,利用二叉树设计二进制前缀编码。,叶子结点表示 A , B , C , D 这 4 个字符,左分支表示 0

33、，右分支表示 1,从根结点到叶子结点的路径上经过的二进制符号串作为该叶子结点字符的编码,A(0),B(110),C(10),D(111),路径长度为编码长度,如何得到最短的二进制前缀编码？,3. 赫夫曼编码,设每种字符在电文中出现的概率 wi 为，则依此 n 个字符出现的概率做权，可以设计一棵赫夫曼树，使,wi 为叶子结点的出现概率 ( 权),li 为根结点到叶子结点的路径长度,例，某通信可能出现 A B C D E F G H 8 个字符，其概率分别为 0.05 , 0.29 , 0.07 , 0.08 , 0.14 , 0.23 , 0.03 , 0.11 ，试设计赫夫曼编码,不妨设 w

34、= 5 , 29 , 7 , 8 , 14 , 23 , 3 , 11 ,排序后 w = 3 , 5 , 7 , 8 , 11 , 14 , 23 , 29 ,ACEA 编码为 0110 1110 110 0110,如何译码？,1. 从根结点出发，从左至右扫描编码，,2. 若为 0 则走左分支，若为1 则走右分支，直至叶结点为止，,3. 取叶结点字符为译码结果，返回重复执行 1,2,3 直至全部译完为止,A,C,E,A,作业: 假设用于通讯的电文由 8 个字母组成，A B C D E F G H ，字母在电文中的出现频率分别为 0.07，0.19，0.02，0.06，0.32，0.03，0.2

35、1，0.10，试设计赫夫曼编码。,本章重点 1 二叉树的存储结构及其各种操作，遍历二叉树 2 树和森林与二叉树的转换关系，树的遍历 3. 哈夫曼树和哈夫曼编码 本章难点 1 遍历二叉树的算法 2 树和森林与二叉树的转换关系，哈夫曼树及编码,典型例题： 一、选择题 1、 在树中，互为堂兄弟的结点拥有相同的( )。 A、双亲 B、祖先 C、层次 D、孩子 2、 树最适合用来表示 （）。 A、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据,3、 在一棵高度为h的满四叉树中，结点总数为( )。 A、(4h-1)/3 B、(4h-1)/2 C、(4h-1)/

36、4 D、4h 4、 若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是( )。 A. 9 B. 11 C. 12 D. 不确定 5、 按二叉树的定义，具有3个结点的二叉树有( ) 种。 A、3 B、4 C、5 D、6,二、填空 1、 在树中，度为( )的结点称为叶子。 2、 在树中，除根结点外，其他结点都有且只有一个( )结点。 3、 有100个结点的树有( )条边。 4、 若将树中的每个结点的各子树看成从左到右有次序，则该树为( )树。 5、 一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有( )个。 6、深度为K的完全二叉树至少有2(k-1

37、)个结点，至多有2(k-1)+1个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是( )。,三、问答题： 1 、若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 (1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。 (2)已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。 (3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉

38、树。,2 、一棵度为2的有序树与一棵二叉树有何区别? 答：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。,3 、试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 三个结点的树如下：只有两种形态 / | | 三个结点的二叉树如下所示：有五种形态： (1) (2) (3) (4) (5) / / / / / ,4 、已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，

39、.nm个度为m的结点，问该树中有多少片叶子? 解：设该树中的叶子数为n0个。该树中的总结点数为n个，则有： n=n0+n1+n2+nm (1) 又树的结点个数也可以由分枝数得到，即 结点个数树中的分支数1，所以， n=0*n0+1*n1+2*n2+m*nm1 (2) 联立(1)(2)方程组可得： 叶子数为：n0=1+0*n1+1*n2+2*n3+.+(m-1)*nm,5 、一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： (1)各层的结点数目是多少? (2)编号为i的结点的双亲结点(若存

40、在)的编号是多少? (3)编号为i的结点的第j个孩子结点(若存在)的编号是多少? (4)编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?,解：(1) 层号为h的结点数目为kh-1 (2) 编号为i的结点的双亲结点的编号是：|_ (i-2)/k _|+1(不大于(i-2)/k的最大整数。也 就是(i-2)与k整除的结果.以下/表示整除。 (3) 编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j; (4) 编号为i的结点有右兄弟的条件是(i-1)能不被k整除右兄弟的编号是i+1.,6、高度为h的完全二叉树至少有多少个结点?至多有多少个结点? 7、在具有n个结点的k叉树(k

41、=2)的k叉链表表示中，有多少个空指针? 8、假设二叉树包含的结点数据为1，3，7，12。 (1)画出两棵高度最大的二叉树； (2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。,6、解：高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。 7、解：n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1（树中分枝数即为指针的个数）,所以空指针的个数为：n(k-1)+1,8解：(1)高度最大的两棵二叉树如图： 1 1 / 3 3 / 7 7 / 2 2 / 12 12 (2)两棵完全二叉树如下： 12 12 / / 7 3 7 3 / / 1 2 2 1,9、以知一组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插入生成的一棵二叉排序树。 10、假设用于通讯的电文由 8 个字母组成，A B C D E F G H ，字母在电文中的出现频率分别为 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10，试设计赫夫曼编码。,