工学
问答题一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次自上至下，从左到右顺序从1开始对全部结点编号，回答下列问题：各层的结点数目是多少？
题目
参考答案和解析
相似问题和答案
第1题：
若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为n，则左、右子树皆非空的结点个数是 ______。
n-1 解析：除了叶子结点左右子树皆非空的二叉树其左右子树皆非空的结点度都为2，假设左右子树皆非空的结点数为x，则树的度的总数为n+x-1，并且所有度都是这些左右子树皆非空的结点引出的，为2x，所以n+x-1=2x，得到x=n-1。
第2题：
● 满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为 h(h>1)的满二叉树，其结点总数为 （36） 。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从 1、2、3、…依次编号，则对于树中编号为 i 的非叶子结点，其右子树的编号为 （37） （高度为 3 的满二叉树如下图所示） 。
第3题：
若一棵二叉树中只有叶结点和左右子树皆非空的结点，设叶结点的个数为k，则左右子树皆非空的结点个数是( )。
A．2k
B．k-1
C．2k-1
D．2k-1
第4题：
树是n（n≥0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m（m＞0）个（）的集合，每个集合都是根结点的子树。
正确答案:有且仅有一个；互不相交
第5题：
若一棵二叉中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为k，则左、右子树皆非空的结点个数是【 】。
根据题意可知该二叉树只有度为2的结点(左、右子树皆非空的结点)和度为0的结点，设度为2的结点数为n2，则由树的性质(3)可得n2=k-1。
第6题：
关于二叉树，下列说法不正确的是( )。
A．在第i层上最多有2i-1个结点
B．深度为k的二叉树最多有2k-1个结点
C．相同层次的满二叉树结点数比完全二叉树结点多
D．深度为k的满二叉树结点数一定为2k-1个
第7题：
满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为h(h＞1)的满二叉树，其结点总数为(36)。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从1、2、3、…依次编号，则对于树中编号为i的非叶子结点，其右子树的编号为(37)(高度为3的满二叉树如下图所示)。
A．2h
B．2h-1
C．2h-1
D．2h-1+1
第8题：
●二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行 （42)遍历，可得到一个结点元素的递增序列
（42）
A. 先序（根、左、右）
B. 中序（左、根、右）
C. 后序（左、右、根）
D. 层序（从树根开始，按层次）
第9题：
满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为h(h＞1)的满二叉树，其结点总数为(1)。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从1、2、3、…依次编号，则对于树中编号为i的非叶子结点，其右子树的编号为(2)(高度为3的满二叉树如图8-17所示)。
A．2h
B．2h-1
C．2h-1
D．2h-1+1
第10题：
一棵深度为h的满二叉树具有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，试计算：编号为i的结点的第j个孩子结点（若有）的编号
正确答案:编号为i的结点的第j个孩子结点(若有)的编号为i*m+(j-(m-1))