设只包含根结点的二叉树高度为0，则高度为k的二叉树最小结点数为k+1。这个说法对么

这个说法是正确的。对于一棵高度为k的二叉树，它的最小结点数是k+1。

可以通过数学归纳法来证明。当k=0时，只有一个根结点，结点数为1，成立。当k=n时，假设高度为n的二叉树最小结点数为n+1，即含有n+1个结点。对于高度为n+1的二叉树，它必须包含一棵高度为n的左子树和一棵高度为n或n-1的右子树（因为左子树高度和右子树高度的差不超过1）。因此，高度为n+1的二叉树的最小结点数为高度为n的左子树的最小结点数加上高度为n或n-1的右子树的最小结点数再加上根结点，即为(n+1)+n+1=n+2+1=n+3。因此，对于任意高度为k的二叉树，它的最小结点数为k+1。

相关问题

一棵结点数为4068 的二叉树最少有( )个叶子结点；二叉树的根节点高度为 1，一棵结点数为2048的二叉树最小的高度值是( )。

一棵二叉树最少有的叶子节点数可以通过以下公式计算：n - (n-1)/2，其中n为二叉树的节点数。所以，一棵节点数为4068的二叉树最少有(4068 - (4068-1)/2) = 2034个叶子节点。

对于一棵二叉树，最小的高度值为log2(n+1)，其中n为二叉树的节点数。所以，一棵节点数为2048的二叉树最小的高度值是log2(2048+1) ≈ 11。

任务1：1）设计二叉树的二叉链表结构；2）基于该结构设计算法：求二叉树的叶子结点数。 任务2：1）设计树的孩子链表法存储结构；2）基于该结构设计算法：求下标为i的结点的双亲。 任务3：(不需要写代码)对于给定的一组权值 W＝{1, 5, 7, 8, 14, 20, 28} ，画出哈夫曼树并求其WPL。

任务1：
1）二叉树的二叉链表结构定义如下：

typedef struct BiTNode{
char data; // 数据域
struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;

2）求二叉树的叶子结点数的算法如下：

int countLeaf(BiTree root){
if(root == NULL){
return 0; // 空树没有叶子结点
}else if(root->lchild == NULL && root->rchild == NULL){
return 1; // 叶子结点
}else{
return countLeaf(root->lchild) + countLeaf(root->rchild); // 递归求左右子树的叶子结点数之和
}
}

任务2：
1）树的孩子链表法存储结构定义如下：

typedef struct CTNode{
int child; // 孩子结点在数组中的下标
struct CTNode *next; // 下一个孩子结点指针
}*ChildPtr;

typedef struct{
char data; // 数据域
ChildPtr firstchild; // 第一个孩子结点指针
}CTBox;

typedef struct{
CTBox nodes[MAXSIZE]; // 结点数组
int n, r; // 结点数和根结点在数组中的下标
}CTree;

2）求下标为i的结点的双亲的算法如下：

int getParent(CTree tree, int i){
for(int j = 0; j < tree.n; j++){
ChildPtr p = tree.nodes[j].firstchild;
while(p != NULL){
if(p->child == i){
return j; // 找到双亲结点
}
p = p->next;
}
}
return -1; // 没有找到双亲结点
}

任务3：
哈夫曼树的构建过程如下：
1）将权值从小到大排序，得到序列{1, 5, 7, 8, 14, 20, 28}。
2）将权值最小的两个结点合并，得到新的结点15，其权值为1+5=6，将其插入到序列中，得到{6, 7, 8, 14, 15, 20, 28}。
3）重复步骤2，得到{13, 14, 15, 20, 28}。
4）重复步骤2，得到{27, 28}。
5）最后剩下的两个结点合并，得到新的根结点55，其权值为27+28=55。

哈夫曼树如下所示：

55
/ \
27 28
/ \
13 14
/ \
1 5

WPL = 1*2 + 5*2 + 7*2 + 8*2 + 14*2 + 20*2 + 28*2 = 196。