第6章树 要点 1、掌握树和二叉树的逻辑结构和基本概念 2、掌握二叉树的性质、二叉链存储、遍历及其相关算法 3、二叉树与树、森林的转换 教材习题参考解答 6.1树有2种,二叉树有5种 6.3n-1=n1+2n2+3n3+……+knk n+nn+n2+…+nk k 6.599 6.6(1)均只有右子结点;(2)均只有左子结点;(3)仅有根结点 k H D A E 6.8 6.10可以不用递归,二叉树后序序列中的第一个结点是根结点的最左子结点的最右子结点 (如果最左子结点没有右子树,则该结点就是后序序列的第一个结点)。 练习 1、假定有如图的树,则该树的度为 ,树的深度为 终 端结点的个数为,单分支结点的个数为 双分支结点的 个数为 ,C结点的双亲结点为 其孩子结点 设是一个休,是由转换得到的三,F中有m个单终端⑥回 点,则B中右指针域为空的结点有 个 3、对于一个具有n个结点的二叉树,当它为一棵 一又树时具有(E 最小高度,即为 当它为一棵单支树(除终端结点外,所有的结点都为单分支结 点)时具有最大高度,即为 4、对于一棵具有n个结点的二叉树,当采用二叉链进行存储时,其二叉链表中的指针域的 总数为 个,其中 个用于链接孩子结点 个空闲着 5、一棵深度为k的满二叉树的结点总数为 棵 深度为k的完全二叉树的结点总数的最小值为 最大值 6、由a,b,c三个结点构成的二叉树,共有 种不 同的结构 7、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数 组R[1.n]中,结点R[i]若有左子女,则左子女是 E 若有右子女,则右子女为
第 6 章 树 要点： 1、掌握树和二叉树的逻辑结构和基本概念； 2、掌握二叉树的性质、二叉链存储、遍历及其相关算法； 3、二叉树与树、森林的转换。 教材习题参考解答： 6.1 树有 2 种，二叉树有 5 种 6.3 n-1 = n1+2n2+3n3+……+knk n +n1+n2+……+nk n0 =1+n2+2n3+……+(k-1)nk 6.5 99 6.6 (1)均只有右子结点；(2)均只有左子结点；(3)仅有根结点。 6.7 n * k – n +1 6.8 6.10 可以不用递归，二叉树后序序列中的第一个结点是根结点的最左子结点的最右子结点 （如果最左子结点没有右子树，则该结点就是后序序列的第一个结点）。 练习： 1、假定有如图的树，则该树的度为 ，树的深度为 ，终 端结点的个数为 ，单分支结点的个数为 ，双分支结点的 个数为 ，C 结点的双亲结点为 ，其孩子结点 为 。 2、设 F 是一个森林，B 是由 F 转换得到的二叉树，F 中有 n 个非终端结 点，则 B 中右指针域为空的结点有 个。 3、对于一个具有 n 个结点的二叉树，当它为一棵 二叉树时具有 最小高度，即为 ，当它为一棵单支树（除终端结点外，所有的结点都为单分支结 点）时具有最大高度，即为 。 4、对于一棵具有 n 个结点的二叉树，当采用二叉链进行存储时，其二叉链表中的指针域的 总数为 个，其中 个用于链接孩子结点， 个空闲着。 5、一棵深度为 k 的满二叉树的结点总数为 ，一棵 深度为 k 的完全二叉树的结点总数的最小值为 ，最大值 为 。 6、由 a，b，c 三个结点构成的二叉树，共有 种不 同的结构。 7、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数 组 R[1..n]中，结点 R[i]若有左子女，则左子女是 ， 若有右子女，则右子女为
8、一棵二叉树如右 (1)写出对此二叉树进行先序、中序、后序和层序遍历时得到的结点序列 (2)画出其中序线索二叉树。 9、已知一棵二叉树的中序遍历序列为 CDBAEGF,先序遍历序列为 ABCDEFG,试问能不能确定 唯一一棵二叉树,若能请画出该二叉树 10、给定一棵用二叉链表示的二叉树,其根结点指针为t,试写出求二叉树叶子结点数目的 算法: int leaf( BiTree t) 11、将以下森林转化为相应的二叉树。 A (HI B 3)(①() 参考解答: 1、34611AF,G 2、n+1 3、满,log2(n+1)最大n 4、 5、2-1,21,2-1 7、R[2i] R[2i+1] 8 (1) ABDFHCEG DFHBACGE HFDBGECA ABCDEFGH (2)如右 H 10、 int leaf( Bitree t) BiTree a[1o], p=t A ti=0,n=0 while(p) I if(p)i a[i++]=p; p=p->lchild else p=aL if(p->lchild==NULL&&p->rchild==NULL)n++ p=p->rchild 4、如右
8、一棵二叉树如右。 （1）写出对此二叉树进行先序、中序、后序和层序遍历时得到的结点序列。 （2）画出其中序线索二叉树。 9、已知一棵二叉树的中序遍历序列为 CDBAEGF，先序遍历序列为 ABCDEFG，试问能不能确定 唯一一棵二叉树，若能请画出该二叉树。 10、给定一棵用二叉链表示的二叉树，其根结点指针为 t，试写出求二叉树叶子结点数目的 算法：int leaf(BiTree t); 11、将以下森林转化为相应的二叉树。 参考解答： 1、3 4 6 1 1 A F，G 2、n+1 3、满， log2(n+1) 最大 n 4、2n n-1 n+1 5、2 k -1, 2k-1 , 2k -1 6、30 7、R[2i] R[2i+1] 8、（1）ABDFHCEG DFHBACGE HFDBGECA ABCDEFGH （2）如右。 9、 10、int leaf(BiTree t) { BiTree a[10],p=t; int i=0,n=0; while(p) { if(p){ a[i++]=p; p=p->lchild;} else { p=a[--i]; if(p->lchild==NULL&&p->rchild==NULL)n++; p=p->rchild; } } return n; } 4、如右：