对一棵满二叉树，m个树叶，n个结点，深度为h，则（）。

对于一棵满二叉树，它的叶子节点数量为 $2^{h}$，而非叶子节点数量为 $2^{h}-1$，因此有以下三个等式成立：

1. $m=2^{h}$，即叶子节点数等于 $2$ 的深度次方；
2. $n=2m-1$，即总节点数等于叶子节点数的两倍减一；
3. $h=\log_{2}(m)$，即深度等于以 $2$ 为底 $m$ 的对数。

因此，对于一棵满二叉树，m个树叶，n个结点，深度为h，则上述三个等式都成立。

相关问题

c语言求该二叉树的叶结点个数、结点总个数和二叉树的深度。

假设二叉树结点的数据类型为 `struct TreeNode`，其中包括左子树和右子树指针，那么可以使用递归来求解二叉树的叶结点个数、结点总个数和深度。具体实现如下：

#include <stdio.h>
#include <stdlib.h>

// 二叉树结点定义
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 求二叉树叶结点个数
int countLeaves(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    } else if (root->left == NULL && root->right == NULL) {
        return 1;
    } else {
        return countLeaves(root->left) + countLeaves(root->right);
    }
}

// 求二叉树结点总个数
int countNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    } else {
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
}

// 求二叉树的深度
int maxDepth(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    } else {
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
    }
}

int main() {
    // 构建一个二叉树
    struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->data = 1;
    root->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->left->data = 2;
    root->left->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->left->left->data = 4;
    root->left->left->left = NULL;
    root->left->left->right = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->right->data = 3;
    root->right->left = NULL;
    root->right->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->right->right->data = 5;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    // 求解二叉树的叶结点个数、结点总个数和深度
    int leaves = countLeaves(root);
    int nodes = countNodes(root);
    int depth = maxDepth(root);

    // 输出结果
    printf("叶结点个数：%d\n", leaves);
    printf("结点总个数：%d\n", nodes);
    printf("二叉树深度：%d\n", depth);

    return 0;
}

输出结果为：

叶结点个数：3
结点总个数：5
二叉树深度：3

C语言编写代码：1．以二叉链表表示二叉树，建立一棵二叉树（算法 5.3）； 2．输出二叉树的中序遍历结果（算法 5.1）； 3．输出二叉树的前序遍历结果（见讲稿）； 4．输出二叉树的后序遍历结果（见讲稿）； 5．计算二叉树的深度（算法 5.5）； 6．统计二叉树的结点个数（算法 5.6）； 7．统计二叉树的叶结点个数； 8．统计二叉树的度为 1 的结点个数； 9．输出二叉树中从每个叶子结点到根结点的路径。10.交换二叉树每个结点的左孩子和右孩子； 11.设计二叉树的双序遍历(DblOrderTraverse)算法

以下是C语言代码实现：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结点结构体
typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建二叉树
TreeNode *create_tree() {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        return NULL;
    }
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->data = ch;
    node->left = create_tree();
    node->right = create_tree();
    return node;
}

// 中序遍历
void inorder_traverse(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorder_traverse(root->left);
    printf("%c ", root->data);
    inorder_traverse(root->right);
}

// 前序遍历
void preorder_traverse(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    preorder_traverse(root->left);
    preorder_traverse(root->right);
}

// 后序遍历
void postorder_traverse(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    postorder_traverse(root->left);
    postorder_traverse(root->right);
    printf("%c ", root->data);
}

// 计算二叉树深度
int get_depth(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int left_depth = get_depth(root->left);
    int right_depth = get_depth(root->right);
    return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}

// 统计二叉树结点个数
int count_nodes(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + count_nodes(root->left) + count_nodes(root->right);
}

// 统计二叉树叶结点个数
int count_leaf_nodes(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return count_leaf_nodes(root->left) + count_leaf_nodes(root->right);
}

// 统计二叉树度为 1 的结点个数
int count_degree_one_nodes(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int degree = 0;
    if (root->left != NULL) {
        degree++;
    }
    if (root->right != NULL) {
        degree++;
    }
    if (degree == 1) {
        return 1 + count_degree_one_nodes(root->left) + count_degree_one_nodes(root->right);
    } else {
        return count_degree_one_nodes(root->left) + count_degree_one_nodes(root->right);
    }
}

// 输出二叉树中从每个叶子结点到根结点的路径
void print_leaf_to_root_path(TreeNode *root, int path[], int path_len) {
    if (root == NULL) {
        return;
    }
    path[path_len] = root->data;
    path_len++;
    if (root->left == NULL && root->right == NULL) {
        printf("Path: ");
        for (int i = path_len - 1; i >= 0; i--) {
            printf("%c ", path[i]);
        }
        printf("\n");
    } else {
        print_leaf_to_root_path(root->left, path, path_len);
        print_leaf_to_root_path(root->right, path, path_len);
    }
}

// 交换二叉树每个结点的左孩子和右孩子
void swap_children(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    TreeNode *temp = root->left;
    root->left = root->right;
    root->right = temp;
    swap_children(root->left);
    swap_children(root->right);
}

// 双序遍历
void dbl_order_traverse(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    if (root->left != NULL) {
        dbl_order_traverse(root->left);
        printf("%c ", root->data);
    }
    if (root->right != NULL) {
        dbl_order_traverse(root->right);
        printf("%c ", root->data);
    }
}

int main() {
    // 创建二叉树
    printf("请输入二叉树，用 # 表示空结点：\n");
    TreeNode *root = create_tree();

    // 中序遍历
    printf("中序遍历结果：\n");
    inorder_traverse(root);
    printf("\n");

    // 前序遍历
    printf("前序遍历结果：\n");
    preorder_traverse(root);
    printf("\n");

    // 后序遍历
    printf("后序遍历结果：\n");
    postorder_traverse(root);
    printf("\n");

    // 计算二叉树深度
    printf("二叉树深度为：%d\n", get_depth(root));

    // 统计二叉树结点个数
    printf("二叉树结点个数为：%d\n", count_nodes(root));

    // 统计二叉树叶结点个数
    printf("二叉树叶结点个数为：%d\n", count_leaf_nodes(root));

    // 统计二叉树度为 1 的结点个数
    printf("二叉树度为 1 的结点个数为：%d\n", count_degree_one_nodes(root));

    // 输出二叉树中从每个叶子结点到根结点的路径
    int path[100];
    printf("从每个叶子结点到根结点的路径：\n");
    print_leaf_to_root_path(root, path, 0);

    // 交换二叉树每个结点的左孩子和右孩子
    swap_children(root);
    printf("交换左右孩子后的前序遍历结果：\n");
    preorder_traverse(root);
    printf("\n");

    // 双序遍历
    printf("双序遍历结果：\n");
    dbl_order_traverse(root);
    printf("\n");

    return 0;
}