嵌入式开发学习：数据结构-＞二叉树
二叉树
·
一、简述
在C语言中，二叉树是各种高级数据结构（如红黑树、AVL树）和算法（如搜索、排序）的基础。
我们将从最基础的概念开始，详细讲解二叉树的定义、C语言实现、核心算法（遍历、插入、搜索、删除），并提供一个完整的、可运行的C语言示例。
为了让插入和删除算法有意义，我们通常会使用一种特殊的二叉树——二叉搜索树（Binary Search Tree, BST）作为例子。
二、正文
1、什么是二叉树？
二叉树（Binary Tree） 是一种树形数据结构，它的特点是每个节点最多有两个子节点，分别称为“左子节点”（left child）和“右子节点”（right child）。
-
根节点（Root）： 树的顶层节点。
-
叶节点（Leaf）： 没有任何子节点的节点。
-
父节点（Parent）： 拥有子节点的节点。
-
子节点（Child）： 节点的下一层节点。
二叉搜索树（BST） 是一种特殊的二叉树，它具有以下性质：
-
对于任意节点，其左子树中所有节点的值都小于该节点的值。
-
对于任意节点，其右子树中所有节点的值都大于该节点的值。
-
左右子树也分别是二叉搜索树。
BST的这个特性使得搜索、插入和删除操作非常高效（平均时间复杂度为 O(log n)）。
2、C语言中的二叉树表示
在C语言中，我们使用结构体（struct）和指针（pointer）来表示二叉树。每个节点都是一个结构体，它包含：
-
节点存储的数据（例如一个整数）。
-
一个指向其左子节点的指针。
-
一个指向其右子节点的指针。
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
struct Node {
int data; // 节点存储的数据
struct Node* left; // 指向左子节点的指针
struct Node* right; // 指向右子节点的指针
};
// 辅助函数：创建一个新节点
// Malloc动态分配内存，并初始化
struct Node* createNode(int data) {
// 为新节点分配内存
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// 检查内存是否分配成功
if (newNode == NULL) {
printf("内存分配失败!\n");
exit(1); // 退出程序
}
newNode->data = data;
newNode->left = NULL; // 初始时没有左右子节点
newNode->right = NULL;
return newNode; // 返回新创建的节点指针
}3. 核心算法详解
我们将以递归的方式实现二叉树的大多数算法，因为二叉树本身就是递归定义的（一个节点和它的左右两个子树）。
3.1 算法一：插入节点 (Insert)
在BST中插入一个新节点，我们必须遵循BST的规则：
-
如果树为空，新节点成为根节点。
-
如果新节点的值小于当前节点，则递归地在左子树中插入。
-
如果新节点的值大于当前节点，则递归地在右子树中插入。
/*
* 插入一个新节点到BST中
* @param node: 当前子树的根节点
* @param data: 要插入的数据
* @return: 返回（可能已修改的）子树的根节点指针
*/
struct Node* insertNode(struct Node* node, int data) {
// 1. 基本情况：如果树（或子树）为空，则创建新节点并返回
if (node == NULL) {
return createNode(data);
}
// 2. 递归步骤：
if (data < node->data) {
// 如果数据较小，插入到左子树
node->left = insertNode(node->left, data);
} else if (data > node->data) {
// 如果数据较大，插入到右子树
node->right = insertNode(node->right, data);
}
// (如果 data == node->data，我们这里选择不做任何事，不允许重复值)
// 3. 返回当前节点指针（这对于递归连接至关重要）
return node;
}3.2 算法二：遍历 (Traversal)
遍历是访问树中所有节点的过程。二叉树主要有三种深度优先遍历方式，它们的区别在于访问根节点（R）、左子树（L）和右子树（R）的顺序。
①前序遍历 (Pre-order: R -> L -> R)
顺序：根节点 -> 左子树 -> 右子树
void preOrderTraversal(struct Node* root) {
if (root != NULL) {
printf("%d ", root->data); // 1. 访问根节点
preOrderTraversal(root->left); // 2. 递归遍历左子树
preOrderTraversal(root->right); // 3. 递归遍历右子树
}
}②b. 中序遍历 (In-order: L -> R -> R)
顺序：左子树 -> 根节点 -> 右子树
重要特性： 对BST进行中序遍历，将得到一个升序排列的序列。
void inOrderTraversal(struct Node* root) {
if (root != NULL) {
inOrderTraversal(root->left); // 1. 递归遍历左子树
printf("%d ", root->data); // 2. 访问根节点
inOrderTraversal(root->right); // 3. 递归遍历右子树
}
}③后序遍历 (Post-order: L -> R -> R)
顺序：左子树 -> 右子树 -> 根节点
应用场景： 释放（free）整个树的内存时，必须使用后序遍历，确保在释放父节点之前，其子节点已被释放。
void postOrderTraversal(struct Node* root) {
if (root != NULL) {
postOrderTraversal(root->left); // 1. 递归遍历左子树
postOrderTraversal(root->right); // 2. 递归遍历右子树
printf("%d ", root->data); // 3. 访问根节点
}
}3.3 算法三：搜索 (Search)
在BST中搜索一个值，利用其特性可以快速定位：
-
如果树为空，没找到（返回NULL）。
-
如果当前节点的值等于目标值，找到了（返回当前节点）。
-
如果目标值小于当前节点，递归地在左子树搜索。
-
如果目标值大于当前节点，递归地在右子树搜索。
/*
* 在BST中搜索一个值
* @param root: 树的根节点
* @param data: 要搜索的数据
* @return: 如果找到，返回该节点的指针；否则返回NULL
*/
struct Node* searchNode(struct Node* root, int data) {
// 1. 基本情况：树为空 或 找到
if (root == NULL || root->data == data) {
return root;
}
// 2. 递归步骤：
if (data < root->data) {
// 目标值较小，向左搜索
return searchNode(root->left, data);
} else {
// 目标值较大，向右搜索
return searchNode(root->right, data);
}
}3.4 算法四：删除 (Delete)
删除是二叉树算法中最复杂的操作。我们需要先找到要删除的节点，然后根据它有多少个子节点来分情况讨论：
-
情况1：要删除的节点是叶节点（没有子节点）。
-
直接释放该节点，并将其父节点的指针设为NULL。
-
-
情况2：要删除的节点只有一个子节点（左或右）。
-
将其父节点直接指向它的那个子节点，然后释放该节点。
-
-
情况3：要删除的节点有两个子节点（最复杂）。
-
为了维持BST的性质，我们不能简单删除它。
-
策略：
-
找到该节点的中序后继（In-order Successor）。（中序后继是指：该节点右子树中的最小节点）。
-
将这个“中序后继”节点的值，复制到要删除的节点上。
-
递归地删除那个“中序后继”节点（此时问题被转化为情况1或情况2，因为中序后继节点最多只有一个右孩子）。
-
-
// 辅助函数：查找子树中的最小节点（即最左边的节点）
struct Node* findMinNode(struct Node* node) {
struct Node* current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
/*
* 从BST中删除一个节点
* @param root: 当前子树的根节点
* @param data: 要删除的数据
* @return: 返回（可能已修改的）子树的根节点指针
*/
struct Node* deleteNode(struct Node* root, int data) {
// 1. 基本情况：树为空
if (root == NULL) {
return root;
}
// 2. 递归查找要删除的节点
if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
// 找到了要删除的节点 (root->data == data)
// 情况1：没有子节点 或 只有一个子节点
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp; // 返回右子节点（或NULL）
} else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp; // 返回左子节点
}
// 情况3：有两个子节点
// 找到中序后继（右子树中的最小值）
struct Node* temp = findMinNode(root->right);
// 将中序后继的值复制到当前节点
root->data = temp->data;
// 递归地删除那个中序后继节点
root->right = deleteNode(root->right, temp->data);
}
return root;
}3.5 算法五：释放树内存 (Free Tree)
当程序结束时，必须释放所有malloc分配的内存，否则会造成内存泄漏。我们使用后序遍历（L -> R -> R）来确保安全释放。
void freeTree(struct Node* root) {
if (root == NULL) {
return;
}
// 1. 释放左子树
freeTree(root->left);
// 2. 释放右子树
freeTree(root->right);
// 3. 释放根节点
// printf("释放节点: %d\n", root->data); // (用于调试)
free(root);
}4. 完整的C语言示例代码
下面是一个将所有算法组合在一起的完整示例：
#include <stdio.h>
#include <stdlib.h>
// ----------------------------------------
// 1. 结构体定义 和 创建节点
// ----------------------------------------
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("内存分配失败!\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// ----------------------------------------
// 2. 插入 (BST Insert)
// ----------------------------------------
struct Node* insertNode(struct Node* node, int data) {
if (node == NULL) {
return createNode(data);
}
if (data < node->data) {
node->left = insertNode(node->left, data);
} else if (data > node->data) {
node->right = insertNode(node->right, data);
}
return node;
}
// ----------------------------------------
// 3. 遍历 (Traversals)
// ----------------------------------------
// 中序 (L-R-R)
void inOrderTraversal(struct Node* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
// 前序 (R-L-R)
void preOrderTraversal(struct Node* root) {
if (root != NULL) {
printf("%d ", root->data);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
// 后序 (L-R-R)
void postOrderTraversal(struct Node* root) {
if (root != NULL) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->data);
}
}
// ----------------------------------------
// 4. 搜索 (Search)
// ----------------------------------------
struct Node* searchNode(struct Node* root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return searchNode(root->left, data);
} else {
return searchNode(root->right, data);
}
}
// ----------------------------------------
// 5. 删除 (Delete)
// ----------------------------------------
// 辅助函数：查找子树中的最小节点
struct Node* findMinNode(struct Node* node) {
struct Node* current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
struct Node* deleteNode(struct Node* root, int data) {
if (root == NULL) return root;
if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
// 找到节点
// 情况1: 0个或1个子节点
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}
// 情况3: 2个子节点
struct Node* temp = findMinNode(root->right); // 找到中序后继
root->data = temp->data; // 复制数据
root->right = deleteNode(root->right, temp->data); // 删除后继节点
}
return root;
}
// ----------------------------------------
// 6. 释放内存
// ----------------------------------------
void freeTree(struct Node* root) {
if (root == NULL) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
// ----------------------------------------
// 7. 主函数 (Main) - 测试
// ----------------------------------------
int main() {
struct Node* root = NULL; // 初始化一个空树
// 插入节点
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
/*
构建的树结构如下:
50
/ \
30 70
/ \ / \
20 40 60 80
*/
// --- 测试遍历 ---
printf("中序遍历 (应为升序): ");
inOrderTraversal(root);
printf("\n");
printf("前序遍历: ");
preOrderTraversal(root);
printf("\n");
printf("后序遍历: ");
postOrderTraversal(root);
printf("\n\n");
// --- 测试搜索 ---
int val_to_find = 40;
if (searchNode(root, val_to_find) != NULL) {
printf("在树中找到了值: %d\n", val_to_find);
} else {
printf("未找到值: %d\n", val_to_find);
}
val_to_find = 99;
if (searchNode(root, val_to_find) != NULL) {
printf("在树中找到了值: %d\n", val_to_find);
} else {
printf("未找到值: %d\n", val_to_find);
}
printf("\n");
// --- 测试删除 ---
// 1. 删除叶节点 (20)
printf("删除 20 (叶节点) 后，中序遍历: ");
root = deleteNode(root, 20);
inOrderTraversal(root);
printf("\n");
// 2. 删除只有一个子节点的节点 (70)
printf("删除 70 (一个子节点) 后，中序遍历: ");
root = deleteNode(root, 70);
inOrderTraversal(root);
printf("\n");
// 3. 删除有两个子节点的节点 (50, 根节点)
printf("删除 50 (两个子节点) 后，中序遍历: ");
root = deleteNode(root, 50);
inOrderTraversal(root);
printf("\n\n");
// --- 释放所有内存 ---
freeTree(root);
printf("树内存已释放。\n");
return 0;
}
智能硬件社区聚焦AI智能硬件技术生态，汇聚嵌入式AI、物联网硬件开发者，打造交流分享平台，同步全国赛事资讯、开展 OPC 核心人才招募，助力技术落地与开发者成长。
更多推荐
17
0- 0
已为社区贡献12条内容
所有评论(0)