当前位置：首页 > article >正文

【数据结构之树】

article 2025/3/19 10:19:04

文章目录

一、前言
二、树的基本概念
- 1. 什么是树？
- 2. 树的常见分类
- - （1）普通树
  - （2）二叉树（Binary Tree）
  - （3）满二叉树（Full Binary Tree）
  - （4）完全二叉树（Complete Binary Tree）
  - （5）二叉搜索树（Binary Search Tree, BST）
  - （6）平衡二叉树（AVL 树）
  - （7）红黑树（Red-Black Tree）
三、树的基本操作及代码示例
- 1. 二叉树的基本实现（C++）
- - 运行结果：
- 2. 二叉搜索树（BST）的插入操作
- - 运行结果：
四、树的应用场景
- - 1. 文件系统（普通树）
  - 2. 数据库索引（B-树、B+树）
  - 3. 表达式解析（语法树）
  - 4. 人工智能（决策树）
  - 5. 网络路由（Trie 树）
五、总结

一、前言

树（Tree）是一种重要的非线性数据结构，在计算机科学中广泛应用，如文件系统、数据库索引、解析表达式等。

二、树的基本概念

1. 什么是树？

树是一种层次结构的数据结构，由节点（Node） 组成，满足以下特点：

有且仅有一个根节点（Root），作为整个树的起点。
每个节点可以有多个子节点，但只有一个父节点（Parent）（根节点除外）。
没有子节点的节点称为叶子节点（Leaf）。
子节点的个数称为度（Degree），整棵树的最大度数为树的度。
从根节点到某个节点的路径长度称为深度（Depth），最长路径的长度称为树的高度（Height）。

示例树结构：

根节点：A
叶子节点：D、E、F
B 的父节点是 A，B 的子节点是 D 和 E

2. 树的常见分类

（1）普通树

普通树的每个节点可以有任意多个子节点，例如文件系统中的目录结构。

（2）二叉树（Binary Tree）

每个节点最多有两个子节点，分别是左子节点（Left Child） 和 右子节点（Right Child）。

（3）满二叉树（Full Binary Tree）

每个非叶子节点都有两个子节点，并且所有叶子节点在同一层。

（4）完全二叉树（Complete Binary Tree）

除最后一层外，所有层的节点都填满，且最后一层的节点必须从左到右连续排列。

（5）二叉搜索树（Binary Search Tree, BST）

满足以下性质：

若左子树不为空，则左子树所有节点的值都小于根节点。
若右子树不为空，则右子树所有节点的值都大于根节点。
左右子树均为二叉搜索树。

示例：

        10
       /  \
      5    15
     / \     \
    2   7    20

满足二叉搜索树的性质。

（6）平衡二叉树（AVL 树）

对二叉搜索树进行平衡，使任意节点的左、右子树的高度差不超过 1。

（7）红黑树（Red-Black Tree）

一种自平衡二叉搜索树，广泛应用于 STL 中的 map、set 以及数据库索引。

三、树的基本操作及代码示例

1. 二叉树的基本实现（C++）

#include <iostream>
using namespace std;

// 二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 先序遍历（根 -> 左 -> 右）
void preOrder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

// 中序遍历（左 -> 根 -> 右）
void inOrder(TreeNode* root) {
    if (root == nullptr) return;
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

// 后序遍历（左 -> 右 -> 根）
void postOrder(TreeNode* root) {
    if (root == nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

int main() {
    // 构造一个简单的二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    cout << "先序遍历: ";
    preOrder(root);
    cout << "\n中序遍历: ";
    inOrder(root);
    cout << "\n后序遍历: ";
    postOrder(root);

    return 0;
}

运行结果：

先序遍历: 1 2 4 5 3
中序遍历: 4 2 5 1 3
后序遍历: 4 5 2 3 1

2. 二叉搜索树（BST）的插入操作

// 插入节点
TreeNode* insert(TreeNode* root, int key) {
    if (root == nullptr) return new TreeNode(key);
    if (key < root->val)
        root->left = insert(root->left, key);
    else
        root->right = insert(root->right, key);
    return root;
}

// 查找节点
bool search(TreeNode* root, int key) {
    if (root == nullptr) return false;
    if (root->val == key) return true;
    return key < root->val ? search(root->left, key) : search(root->right, key);
}

int main() {
    TreeNode* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    
    cout << (search(root, 5) ? "找到 5" : "未找到 5") << endl;
    cout << (search(root, 7) ? "找到 7" : "未找到 7") << endl;

    return 0;
}