9、&R3=&R1+(i*(i-1)/2+j1)*=1+4=5 第6章树 要点: 1、掌握树和二叉树的逻辑结构和基本概念 2、掌握二叉树的性质、二叉链存储、遍历及其相关算法 B)(C)(D 、二叉树与树、森林的转换。 练习: (E(R (G 1、假定有如图的树,则该树的度为 树的深度为,终端结点 的个数为 ,单分支结点的个数为 双分支结点的个数O 为 ,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 eaf(BiTree t) 11、将以下森林转化为相应的二叉树 F G 参考解答: l、34611AF,G 2、n+1 3、满,log2(n+1)最大 4、2nn-1n+1 7、R[2i] R[2i+1]10 9、&Rij=&R11+(i*(i-1)/2+j-1)*L=1+4=5 第 6 章 树 要点： 1、掌握树和二叉树的逻辑结构和基本概念； 2、掌握二叉树的性质、二叉链存储、遍历及其相关算法； 3、二叉树与树、森林的转换。 练习： 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、将以下森林转化为相应的二叉树。 参考解答： 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]