数据结构之二叉树详解：从原理到实现

1. 什么是二叉树？

二叉树（Binary Tree）是一种树形数据结构，其中每个节点最多有两个子节点，分别被称为左子节点和右子节点。二叉树可以用来表示层次关系，如文件目录、组织结构，或用于快速查找、排序和决策问题。其结构如下：

2. 二叉树的基本术语

在了解二叉树之前，我们需要掌握一些关键术语：

节点（Node）：二叉树的基本单元，包含数据和指向子节点的指针。
根节点（Root）：二叉树的最顶端节点。
叶子节点（Leaf）：没有子节点的节点。
高度（Height）：从某节点到叶子节点的最长路径上的边数。
深度（Depth）：从根节点到某节点所经过的边数。
子树（Subtree）：由某节点及其子节点组成的部分树。

3. 二叉树的分类

根据节点的分布特点，二叉树有多种类型：

满二叉树：每个节点都有两个子节点，且所有叶子节点在同一层。
完全二叉树：除了最后一层外，其他层的节点都被填满，最后一层的叶子节点从左到右连续排列。
二叉搜索树（BST）：对于任意一个节点，左子树中的所有节点值都小于该节点值，右子树中的所有节点值都大于该节点值。
平衡二叉树：左右子树的高度差不超过1。

4. 二叉树的存储结构

二叉树可以通过两种方式存储：

链式存储：用链表表示，每个节点包含数据和左右子节点的指针。
顺序存储：用数组表示，通常用于完全二叉树或满二叉树。

链式存储

在C语言中，链式存储通常使用结构体来定义二叉树节点：


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

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

// 创建新节点
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

顺序存储

顺序存储常用数组表示，用于完整或接近完整的二叉树。节点的存储规则如下：

根节点存储在索引1（或0）。
索引为i的节点的左子节点在2*i位置，右子节点在2*i+1位置。
父节点在索引i/2位置。

5. 二叉树的基本操作

1. 插入节点

插入节点的方式取决于二叉树的类型。在二叉搜索树（BST）中，插入节点时需要保持左小右大的规则。


struct TreeNode* insert(struct TreeNode* root, int data) {
    if (root == NULL) {
        return createNode(data);  // 如果当前节点为空，创建新节点
    }
    if (data < root->data) {
        root->left = insert(root->left, data);  // 插入左子树
    } else if (data > root->data) {
        root->right = insert(root->right, data); // 插入右子树
    }
    return root;
}

2. 查找节点

在二叉搜索树中查找节点时，可以利用其有序性快速定位目标节点。


struct TreeNode* search(struct TreeNode* root, int key) {
    if (root == NULL || root->data == key) {
        return root;  // 找到节点或到达空节点
    }
    if (key < root->data) {
        return search(root->left, key);  // 在左子树中查找
    } else {
        return search(root->right, key); // 在右子树中查找
    }
}

3. 遍历二叉树

二叉树的遍历方式分为以下几种：

前序遍历（Pre-order）：根节点 -> 左子树 -> 右子树
中序遍历（In-order）：左子树 -> 根节点 -> 右子树
后序遍历（Post-order）：左子树 -> 右子树 -> 根节点
层序遍历（Level-order）：按层次从上到下逐层遍历

前序遍历


void preOrder(struct TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

中序遍历


void inOrder(struct TreeNode* root) {
    if (root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

后序遍历


void postOrder(struct TreeNode* root) {
    if (root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}

4. 删除节点

在二叉搜索树中删除节点我们需要考虑三种情况：

被删除节点是叶子节点。
被删除节点有一个子节点。
被删除节点有两个子节点。


struct TreeNode* deleteNode(struct TreeNode* root, int key) {
    if (root == NULL) return root;

    if (key < root->data) {
        root->left = deleteNode(root->left, key);  // 在左子树中删除
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key); // 在右子树中删除
    } else {
        // 找到要删除的节点
        if (root->left == NULL) {
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        // 有两个子节点，找右子树的最小节点
        struct TreeNode* temp = root->right;
        while (temp->left != NULL) {
            temp = temp->left;
        }
        root->data = temp->data; // 用最小值替换当前节点
        root->right = deleteNode(root->right, temp->data); // 删除最小节点
    }
    return root;
}