C语言数据结构之满二叉树、完全二叉树的节点数计算详解

目录

• 一、基本概念
• 1.1 满二叉树
• 1.2 完全二叉树
• 1.3 两种二叉树对比
• 二、代码详解
• 2.1 满二叉树计算
• 2.2 完全二叉树计算
• 2.3 主函数main
• 三、总结

一、基本概念

1.1 满二叉树

定义：高度为 h 的二叉树，如果它有最大的节点数（2-1个），则称为满二叉树。

特征：

• 每一层都达到最大节点数

• 所有叶子都在最后一层

• 每个非叶子节点都有两个子节点

• 没有度为1的节点（要么0个子，要么2个子）

1.2 完全二叉树

定义：高度为 h 的二叉树，除第 h 层外，其他各层都达到最大节点数，且第 h 层的节点都连续集中在最左边。

特征：

• 叶子节点只在最后两层

• 最后一层的叶子都靠左排列

• 度为1的节点最多只有1个

• 适合用数组存储（没有空洞）

1.3 两种二叉树对比

二、代码详解

2.1 满二叉树计算

• 先检查边界：高度必须>0，否则直接返回

• 套用公式计算

• 按顺序输出：先总节点，再叶子，然后度2，最后度1（总是0）

void fullBinaryTree(int he编程客栈编程ight) {
    if (height <= 0) return;  // 第1步：参数检查
    
    // 第2步：核心计算
    int total_nodes = pow(2, height) - 1;      // 公式1：总节点数 = 2^h - 1
    int leaf_nodes = pow(2, height - 1);       // 公式2：叶子数 = 2^(h-1)
    int degree2_nodes = leaf_nodes - 1;        // 公式3：度2节点 = 叶子数 - 1
    
    // 第3步：输出结果
    printf("\n高度为 %d 的满二叉树:\n", height);
    printf("总节点数: %d\n", total_nodes);
    printf("叶子节点数: %d\n", leaf_nodes);
    printf("度2节点: %d\n", degree2_nodes);
    printf("度1节点: 0\n");  // 第4步：满二叉树特性（无度1节点）
}

2.2 完全二叉树计算

• 边界检查：节点数必须>0

• 依次计算：高度 → 叶子数 → 度1节点 → 度2节点（用减法）

• 简洁输出：直接显示所有结果

void completeBinaryTree(int n) {
    if (n <= 0) return;  // 第1步：参数检查
    
    // 第2javascript步：计算三个关键值
    int h = (int)(log2(n)) + 1;          // 公式1：高度 = ⌊log₂n⌋ + 1编程客栈
    int leaves = (n + 1) / 2;            // 公式2：叶子数 = ⌈n/2⌉
    int degree1 = (n % 2 == 0) ? 1 : 0;  // 公式3：度1节点（偶数1，奇数0）
    int degree2 = n - leaves - degree1;  // 公式4：度2节点 = 总数 - 叶子 - 度1
    
    // 第3步：输出结果
    printf("\n%d个节点的完全二叉树:\n", n);
    printf("高度: %d\n", h);
    printf("叶子数: %d\n", leaves);
    printf("度1节点: %d\n", degree1);
    printf("度2节点: %d\n", degree2);
}

2.3 主函数main

int main() {
    // 1. 演示满二叉树
    printf("== 满二叉树示例 ==");
    fullBinaryTree(3);  // 高度为3的满二叉树
    
    // 2. 演示完全二叉树
    printf("\n== 完全二叉树示例 ==");
    completeBinaryTree(9);  // 9个节点的完全二叉树
    
    return 0;
}

三、总结

这段二叉树节点关系计算代码体现了清晰的设计思路和实现逻辑。代码采用模块化设计，将满二叉树和完全二叉树的计算分别封装为独立函数，每个函数功能单一、接口明确。

实现上直接应用数学公式：满编程二叉树部分基于高度h推导所有节点数，完全二叉树部分基于节点总数n计算各项数值。关键算法包括高度计算中的对数运算和类型转换，叶子数计算中的整数除法技巧，以及度1节点数的奇偶判断逻辑。

到此这篇关于C语言数据结构之满二叉树、完全二叉树的节点数计算的文章就介绍到这了,更多相关C语言满二叉树、完全二叉树节点数计算内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！