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

1. 什么是二叉树？

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

2. 二叉树的基本术语

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

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

---

3. 二叉树的分类

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

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

4. 二叉树的存储结构

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

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

链式存储

在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. 删除节点

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

1. 被删除节点是叶子节点。
2. 被删除节点有一个子节点。
3. 被删除节点有两个子节点。

​
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;
}​

6. 二叉树的应用

1. 二叉搜索树（BST）：用于快速查找、插入和删除操作。
2. 堆（Heap）：用于优先队列和排序。
3. 表达式树：用于表示算术表达式。
4. Huffman树：用于数据压缩。
5. 平衡二叉树（AVL/红黑树）：用于高效的动态数据结构

表示文件系统的目录树结构