网站导航
> 技术文档 > 数据结构 | 树的秘密

数据结构 | 树的秘密

网友: 技术文档 2025-08-08 12:44:33

个人主页-爱因斯晨

文章专栏-数据结构

最近学习人工智能时遇到一个好用的网站分享给大家：
人工智能学习

数据结构 | 树的秘密

树是数据结构中一种重要的非线性结构，它以分层的方式存储数据，广泛应用于数据库索引、文件系统、编译器设计等地方。本文将通过 C 语言实现，带你深入了解树的基本概念与操作。

一、树的基本概念

  1. 定义：树是由 n (n≥0) 个节点组成的有限集合，当 n=0 时称为空树；当 n>0 时，有且仅有一个根节点，其余节点分为若干个互不相交的子集，每个子集本身也是一棵树。
  2. 基本术语：
    • 节点：树的基本组成单位
    • 根节点：没有父节点的节点
    • 叶子节点：没有子节点的节点
    • 深度：从根节点到当前节点的路径长度
    • 高度：从当前节点到最远叶子节点的路径长度
  3. 树的特点：
    • 每个节点有零个或多个子节点
    • 有且仅有一个根节点
    • 除根节点外，每个节点有且仅有一个父节点

二、二叉树的实现

二叉树是最常用的树结构，每个节点最多有两个子节点（左子树和右子树）。

1. 节点结构定义

首先，我们需要定义二叉树节点的结构。每个节点包含数据域和两个指针域，分别指向左子节点和右子节点。

#include #include // 二叉树节点结构typedef struct Node { int data; struct Node* left; // 左子树 struct Node* right; // 右子树} Node;// 创建新节点Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); if (newNode == NULL) { printf(\"内存分配失败\\n\"); exit(1); } newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode;}

2. 二叉树的基本操作

下面实现二叉树的常用操作，包括插入、遍历、查找、删除等功能。

// 插入节点（按照二叉搜索树规则）Node* insert(Node* 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;}// 前序遍历：根->左->右void preorderTraversal(Node* root) { if (root != NULL) { printf(\"%d \", root->data); preorderTraversal(root->left); preorderTraversal(root->right); }}// 中序遍历：左->根->右void inorderTraversal(Node* root) { if (root != NULL) { inorderTraversal(root->left); printf(\"%d \", root->data); inorderTraversal(root->right); }}// 后序遍历：左->右->根void postorderTraversal(Node* root) { if (root != NULL) { postorderTraversal(root->left); postorderTraversal(root->right); printf(\"%d \", root->data); }}// 查找节点Node* search(Node* root, int key) { // 树为空或找到节点 if (root == NULL || root->data == key) { return root; } // 关键字小于根节点值，在左子树中查找 if (key < root->data) { return search(root->left, key); } // 否则在右子树中查找 return search(root->right, key);}// 找到最小值节点（最左节点）Node* findMin(Node* root) { while (root->left != NULL) { root = root->left; } return root;}// 删除节点Node* deleteNode(Node* 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 { // 找到要删除的节点 // 情况1：叶子节点或只有一个子节点 if (root->left == NULL) { Node* temp = root->right; free(root); return temp; } else if (root->right == NULL) { Node* temp = root->left; free(root); return temp; } // 情况2：有两个子节点 // 找到中序后继（右子树中的最小值） Node* temp = findMin(root->right); // 复制后继节点的值到当前节点 root->data = temp->data; // 删除后继节点 root->right = deleteNode(root->right, temp->data); } return root;}// 计算树的高度int treeHeight(Node* root) { if (root == NULL) { return -1; // 空树高度为-1 } int leftHeight = treeHeight(root->left); int rightHeight = treeHeight(root->right); return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;}// 计算节点总数int countNodes(Node* root) { if (root == NULL) { return 0; } return 1 + countNodes(root->left) + countNodes(root->right);}// 释放树的内存void freeTree(Node* root) { if (root != NULL) { freeTree(root->left); freeTree(root->right); free(root); }}

3. 测试代码

下面编写一个测试程序，验证上述实现的功能：

int main() { Node* root = NULL; // 插入节点 root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); printf(\"二叉树的节点总数: %d\\n\", countNodes(root)); printf(\"二叉树的高度: %d\\n\", treeHeight(root)); printf(\"\\n前序遍历: \"); preorderTraversal(root); printf(\"\\n中序遍历: \"); inorderTraversal(root); printf(\"\\n后序遍历: \"); postorderTraversal(root); // 查找节点 int key = 40; Node* found = search(root, key); if (found != NULL) { printf(\"\\n\\n找到节点: %d\", found->data); } else { printf(\"\\n\\n未找到节点: %d\", key); } // 删除节点 key = 30; root = deleteNode(root, key); printf(\"\\n\\n删除节点 %d 后中序遍历: \", key); inorderTraversal(root); printf(\"\\n删除节点后树的节点总数: %d\", countNodes(root)); // 释放内存 freeTree(root); return 0;}

三、代码解析

  1. 节点结构：使用结构体Node定义二叉树节点，包含数据域data和两个指针域left、right。
  2. 创建节点：createNode函数负责为新节点分配内存并初始化。
  3. 插入操作：按照二叉搜索树的规则插入节点，即左子树的值小于根节点，右子树的值大于根节点。
  4. 遍历操作：
    • 前序遍历：先访问根节点，再遍历左子树，最后遍历右子树
    • 中序遍历：先遍历左子树，再访问根节点，最后遍历右子树（对二叉搜索树，中序遍历结果是有序的）
    • 后序遍历：先遍历左子树，再遍历右子树，最后访问根节点
  5. 删除操作：删除节点需要考虑三种情况：
    • 叶子节点：直接删除
    • 只有一个子节点：用子节点替代当前节点
    • 有两个子节点：用中序后继（右子树的最小值节点）替代当前节点
  6. 其他操作：实现了查找、计算树高、统计节点总数和释放内存等辅助功能。

四、树的应用场景

  1. 二叉搜索树：用于快速查找、插入和删除操作，时间复杂度为 O (log n)
  2. 堆：用于实现优先队列，高效获取最大值或最小值
  3. 红黑树：一种自平衡二叉搜索树，用于 C++ 的 map、set 等容器
  4. B 树 / B + 树：用于数据库索引，优化磁盘 IO 操作
  5. 哈夫曼树：用于数据压缩算法
  6. 决策树：用于机器学习中的分类和回归问题

五、总结

树结构是计算机科学中非常重要的数据结构，通过本文的学习，你应该掌握了二叉树的基本概念和 C 语言实现方法。二叉树作为树结构中最简单也最常用的一种，是学习更复杂树结构（如 AVL 树、红黑树、B 树等）的基础。

在实际开发中，选择合适的树结构可以显著提高程序的性能。例如，在需要频繁插入和查找的场景中，二叉搜索树是不错的选择；而在需要保持平衡以避免极端情况的场景中，自平衡二叉树更为适合。

网络标签：

相关问题