一个深度为 h 的满 m 叉树有如下性质：第 h 层上的结点都是叶结点，其各层上每个结点有 m 棵非空子树。问：
（1）第 k 层最多有多少个结点？（k≤h )
（2）整棵树最多有多少个结点？
（3）若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，编号为 i 的结汽的双亲结点的编号是什么？编号为 i 的结点的第 j 个孩子结点（若存在）的编号是什么？
-
关注优题吧，注册平台账号.
题吧，智能辅助学习中心
问答题（1996年北京航空航天大学）
答案解析
（1）第 k 层上最多有 mk-1个结点。（2）整棵树最多有 1 + m + m2 + mn-1=(mn-1)个结点。（3）① 将编号为 i 的结点视为完全 m 叉树的最后一个结点，设它的父结点的编号为 x , 因此此完全 m 叉树中至少有x-1 个度为 m 的结点，而x号结点的度 d∈[1,m]，其余的结点均为叶子结点，而编号 i ...
查看完整答案讨论
已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为【 】
一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 __________。
已知一棵二叉树的树形如图，若其后序遍历为 f、d、b、e、c、a，则其先序列为【 】
某二叉树中度为2的结点有18个，则该二叉树中有__________个叶子结点。
某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）【 】
某二叉树的先序遍历(根、左、右)序列为 EFHIGJK、中序遍历(左、根、右)序列为HFIEJKG，则该二叉树根结点的左孩子结点和右孩子结点分别是【 】
一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有结点个数为【 】。
对于二叉树T 的两个结点 n1 和 n2 ，我们应该选择树 T 结点的前序、中序和后序中哪两个序列来判断结点 n1 必定是结点 n2的祖先，并给出判断的方法。不需证明判断方法的正确性。
证明一棵二叉树无论进行先序、中序、后序遍历，其叶子结点的相对次序不发生改变。
对二叉排序树进行【 】遍历，可以得到该二叉树所有结点构成的排序序列。
若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用【 】遍历方法最合适。
已知一棵二叉树，如果先序遍历的顺序是ADCEFGHB，中序遍历的顺序是CDFEGHAB，则后序遍历的结果为【 】。
在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应念是一个【 】结构。
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为【 】。（1≤i≤n+1）
中缀表达式 A-(B + c/d) * E的后缀形式是【 】
利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素35要进行【 】次元素间的比较。
若杂凑表（Hash）的地址范围为[0,9]，杂凑函数为H(key)=(key2+2) MOD 9，并采用链地址法处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入杂凑表的状态。