C 语言二叉树

C语言二叉树

二叉树（Binary Tree）是C语言中一种重要的非线性数据结构，由节点（Node）和边（Edge）组成，每个节点最多有两个子节点（左子节点和右子节点）。它在算法设计、数据库索引、编译器实现等领域有广泛应用。

基本概念

二叉树具有以下特性：

• 每个节点包含：数据域、左子节点指针、右子节点指针
• 根节点（Root）是树的起始节点
• 叶子节点（Leaf）是没有子节点的节点
• 深度（Depth）指从根到某节点的最长路径长度
• 高度（Height）是树中节点的最大深度

graph TD A((根节点)) --> B((左子节点)) A --> C((右子节点)) B --> D((左子节点)) B --> E((右子节点)) C --> F((左子节点)) D --> G((叶子节点)) E --> H((叶子节点)) F --> I((叶子节点))

二叉树节点结构

在C语言中，二叉树节点通常用结构体表示：

struct TreeNode {
    int data;               // 数据域
    struct TreeNode* left;  // 左子节点指针
    struct TreeNode* right; // 右子节点指针
};

二叉树操作

创建节点

struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode != NULL) {
        newNode->data = value;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    return newNode;
}

插入节点

以下是一个简单的二叉搜索树插入示例：

void insertNode(struct TreeNode** root, int value) {
    if (*root == NULL) {
        *root = createNode(value);
        return;
    }
    
    if (value < (*root)->data) {
        insertNode(&(*root)->left, value);
    } else {
        insertNode(&(*root)->right, value);
    }
}

遍历二叉树

二叉树有三种基本遍历方式：

遍历方式比较

遍历类型	顺序	应用场景
前序遍历	根→左→右	复制树结构
中序遍历	左→根→右	获取有序序列
后序遍历	左→右→根	删除树结构

前序遍历示例：

void preOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);  // 访问根节点
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }
}

特殊二叉树类型

完全二叉树

除最后一层外，其他层节点都达到最大值，且最后一层节点从左向右填充。

数学性质：对于深度为$k$的完全二叉树：

• 节点总数范围：$2^{k-1}\le n\le 2^k-1$
• 第$i$个节点的子节点位置：左子节点=$2i+1$，右子节点=$2i+2$

二叉搜索树（BST）

满足以下条件：

• 左子树所有节点值 < 根节点值
• 右子树所有节点值 > 根节点值
• 左右子树也都是BST

查找时间复杂度：平均$O(\log n)$，最坏$O(n)$（退化为链表时）

实际应用案例

案例1：文件系统目录结构 操作系统常用二叉树组织文件目录，每个节点代表一个目录或文件：

• 数据域：文件名/目录名
• 左指针：第一个子目录/文件
• 右指针：同级下一个目录/文件

案例2：表达式树 编译器将算术表达式转换为二叉树：

• 叶子节点：操作数
• 内部节点：运算符
• 中序遍历得到中缀表达式
• 后序遍历可用于计算表达式值

graph TD *((*)) --> +((+)) * --> /((/)) + --> a((a)) + --> b((b)) / --> c((c)) / --> d((d))

对应表达式：

$(a+b)*(c/d)$

常见问题与解决方案

问题1：内存泄漏 忘记释放二叉树节点会导致内存泄漏。解决方案：

void freeTree(struct TreeNode* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

问题2：平衡性问题 二叉搜索树可能退化为链表。解决方案：使用AVL树或红黑树等自平衡二叉树。

进阶练习

1. 实现计算二叉树高度的函数 2. 编写检查二叉树是否为BST的函数 3. 实现二叉树的层序遍历（使用队列）

通过系统学习二叉树，您将掌握处理层次化数据的重要技能，为学习更复杂的树结构（如B树、堆等）奠定基础。