数据结构 - 树

树（Tree）是一种典型的非线性数据结构，由节点和连接节点的边构成，用于表示元素之间"一对多"的层级关系。

树的基本术语

树的术语图解

A根节点
深度0

B深度1

C深度1

D叶节点
深度2

E叶节点

F叶节点

根节点无父节点，唯一

子节点直接下级

叶节点无子节点

深度根到该节点的边数

高度该节点到最深叶的边数

二叉树每节点最多2子

理解树结构需要先掌握几个基本术语：

术语	含义
根节点 (Root)	树的起始节点，没有父节点
子节点 (Child)	某个节点直接连接的下一层节点
父节点 (Parent)	某个节点直接连接的上一层节点
叶节点 (Leaf)	没有子节点的节点，即树的末端
深度 (Depth)	从根节点到该节点的边数，根的深度为 0
高度 (Height)	从该节点到最深叶节点的边数

二叉树的遍历

二叉树四种遍历方式 — 以同一棵树为例

前序 (根→左→右)

1 2 4 5 3

中序 (左→根→右)

4 2 5 1 3

后序 (左→右→根)

4 5 2 3 1

层序 (逐层)

1 2 3 4 5

常见的四种遍历方式如下：

遍历方式	访问顺序	典型应用
前序遍历	根 → 左 → 右	复制树、前缀表达式生成
中序遍历	左 → 根 → 右	BST 输出有序序列
后序遍历	左 → 右 → 根	删除树、后缀表达式生成
层序遍历	逐层从左到右	BFS、按层打印

实例

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

struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};

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

/* 前序遍历：根 → 左 → 右 */
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); /* 最后访问根 */
}

int main() {
/* 构建如下二叉树:
1
/ \
2 3
/ \
4 5 */
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);

printf("前序: "); preOrder(root); printf("\n"); /* 1 2 4 5 3 */
printf("中序: "); inOrder(root); printf("\n"); /* 4 2 5 1 3 */
printf("后序: "); postOrder(root); printf("\n"); /* 4 5 2 3 1 */
return 0;
}

二叉搜索树（BST）

二叉搜索树 (BST) — 左小右大

BST 性质与操作

性质：左子树所有值 < 根 < 右子树所有值

插入/查找：小于走左子树，大于走右子树，平衡时 O(log n)

中序遍历输出升序序列：20 30 40 50 60 70 80

注意：按 1,2,3... 顺序插入会退化成链表 O(n)，AVL 树可解决

二叉搜索树（BST）要求：对于每个节点，左子树所有节点的值小于该节点，右子树所有节点的值大于该节点。

实例

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

struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};

/* BST 插入：根据值的大小递归定位到合适位置
时间复杂度：O(h)，h 为树高，平衡时为 O(log n) */
struct TreeNode* insert(struct TreeNode* root, int value) {
if (root == NULL) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = node->right = NULL;
return node;
}
if (value < root->data) {
root->left = insert(root->left, value); /* 小于根，插入左子树 */
} else if (value > root->data) {
root->right = insert(root->right, value); /* 大于根，插入右子树 */
}
return root; /* 相等则忽略（BST 通常不存重复值） */
}

/* BST 查找：与当前节点比较，决定向左或向右搜索 */
struct TreeNode* search(struct TreeNode* root, int target) {
if (root == NULL || root->data == target) {
return root; /* 找到目标或到达叶节点 */
}
if (target < root->data) {
return search(root->left, target); /* 目标更小，去左子树找 */
}
return search(root->right, target); /* 目标更大，去右子树找 */
}

/* 中序遍历（验证 BST 的有序性） */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}

int main() {
struct TreeNode* root = NULL;
int values[] = {50, 30, 70, 20, 40, 60, 80};

/* 依次插入构建 BST */
for (int i = 0; i < 7; i++) {
root = insert(root, values[i]);
}

printf("BST 中序遍历（升序）: ");
inOrder(root); /* 输出: 20 30 40 50 60 70 80 */
printf("\n");

/* 查找测试 */
int target = 40;
struct TreeNode* found = search(root, target);
printf("%d %s\n", target, found ? "找到了！" : "未找到");
/* 输出: 40 找到了！ */
return 0;
}

BST 在理想情况下（树保持平衡），插入、删除、查找都可达 O(log n)。但如果数据本身有序（如按 1, 2, 3, 4... 插入），BST 会退化为一条链表，效率降为 O(n)。为解决此问题，计算机科学中发展出了 AVL 树等自平衡二叉搜索树。

返回顶部

菜鸟教程