数据结构——树

时间：2025-02-10 08:15:53

一、引言

在计算机科学中，数据结构是组织和存储数据的一种方式，而树是一种非常重要的数据结构。它在很多领域都有广泛的应用，比如文件系统、数据库索引、算法设计等。理解树的基本概念和操作对于编程人员来说至关重要。本文将详细介绍树的基本概念、常见的树类型以及一些基本操作，希望能帮助大家更好地掌握这一数据结构。

二、树的基本概念

（一）定义

树是一种非线性数据结构，它由若干个节点（或顶点）和边组成。树具有以下特点：

  1. 有一个特殊的节点称为根节点，它是树的起点，没有父节点。

  2. 除了根节点外，每个节点有且仅有一个父节点。

  3. 从根节点到任何其他节点的路径是唯一的。

  4. 树中的节点可以有多个子节点。

二）基本术语

  1. 节点（Node）：树中的一个元素，包含数据部分和指向子节点的链接。

  2. 边（Edge）：连接两个节点的线段，表示节点之间的关系。

  3. 根节点（Root）：树的顶层节点，没有父节点。

  4. 父节点（Parent）：一个节点的上层节点称为它的父节点。

  5. 子节点（Child）：一个节点的下层节点称为它的子节点。

  6. 兄弟节点（Sibling）：具有相同父节点的节点互为兄弟节点。

  7. 叶子节点（Leaf）：没有子节点的节点。

  8. 节点的度（Degree）：一个节点拥有的子树个数。

  9. 树的度：树中所有节点的度的最大值。

  10. 路径和路径长度：从一个节点到另一个节点的边的序列称为路径，路径长度是路径上边的数目。

  11. 深度（Depth）：从根节点到某个节点的最长路径长度加 1。根节点的深度为 1。

  12. 高度（Height）：从某个节点到叶子节点的最长路径长度加 1。对于空树，高度为 0；对于只有一个节点的树，高度为 1。

三、常见的树类型

（一）二叉树（Binary Tree）

  1. 定义：每个节点最多有两个子节点的树。二叉树的特点是每个节点的子节点有左右之分，且顺序不能颠倒。

  2. 性质：

    • 第 i 层上最多有 2(i−1) 个节点（i≥1）。

    • 深度为 k 的二叉树最多有 2k−1 个节点（k≥1）。

    • 对于任何非空二叉树，如果其叶子节点数为 n0​，度为 2 的节点数为 n2​，则 n0​=n2​+1。

  3. 遍历方式：

    • 前序遍历（Pre - order Traversal）：访问根节点 - 遍历左子树 - 遍历右子树。

    • 中序遍历（In - order Traversal）：遍历左子树 - 访问根节点 - 遍历右子树。

    • 后序遍历（Post - order Traversal）：遍历左子树 - 遍历右子树 - 访问根节点。

    • 层次遍历（Level - order Traversal）：从上到下、从左到右依次访问树中的每个节点。

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

  1. 定义：一棵深度为 k 且有 2k−1 个节点的二叉树。在这种树中，每一层的节点数都达到最大值。

  2. 特点：所有叶子节点都在同一层，且每个非叶子节点都有两个子节点。

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

  1. 定义：如果一棵二叉树的深度为 k，且从第 1 层到第 k - 1 层的节点数都达到最大值，第 k 层的节点从左到右连续紧密排列，这就是完全二叉树。

  2. 特点：完全二叉树的节点数在 2(k−1) 到 2k−1 之间。它既可以是满二叉树，也可以不是满二叉树。在实际应用中，完全二叉树的性质使得它可以通过数组来高效地存储和操作，例如在堆数据结构中。

（四）平衡二叉树（Balanced Binary Tree）

  1. 定义：一棵二叉树，其中每个节点的左子树和右子树的高度差（平衡因子）的绝对值不超过 1。

  2. 特点：平衡二叉树能够保证查找、插入和删除操作的时间复杂度为 O(log n)，其中 n 是树中节点的数量。常见的平衡二叉树有 AVL 树和红黑树。

    • AVL 树：它是最先被发明的自平衡二叉查找树。在 AVL 树中，任何节点的两个子树的高度最大差别为 1。如果在插入或删除节点后，树的平衡性被破坏，就需要通过旋转操作来恢复平衡。

    • 红黑树：它是一种自平衡二叉查找树，每个节点都有一个颜色属性，红色或黑色。在红黑树中，除了满足二叉查找树的性质外，还需要满足以下规则：

      • 每个节点要么是红色，要么是黑色。

      • 根节点是黑色。

      • 所有叶子节点（空节点）都是黑色。

      • 如果一个节点是红色，则它的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）。

      • 从任意节点到其每个叶子的所有路径都包含相同数量的黑色节点。

（五）B - 树

  1. 定义：B - 树是一种平衡的多路查找树，它主要用于数据库和文件系统中。B - 树的每个节点可以有多个子节点，其目的是减少磁盘 I/O 操作。

  2. 性质：

    • 每个节点最多有 M 个子节点（M 是 B - 树的阶）。

    • 每个节点（除了根节点和叶子节点）至少有 M/2 个子节点。

    • 根节点至少有两个子节点（如果根节点不是叶子节点）。

    • 所有叶子节点都在同一层，并且叶子节点不包含关键字信息。

    • 一个有 k 个子节点的节点包含 k - 1 个关键字，关键字在节点内有序排列。

四、树的基本操作

（一）创建树

创建树的方式因树的类型和应用场景而异。对于二叉树，可以通过递归或队列来构建。例如，给定一个数组表示的二叉树的层次遍历序列，可以使用队列来逐层构建二叉树。

（二）遍历树

  1. 二叉树的遍历：

    • 前序遍历：递归实现时，先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

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

// 定义二叉树节点结构
typedef struct TreeNode {
    int value;                // 节点存储的数据
    struct TreeNode* left;    // 指向左子节点
    struct TreeNode* right;   // 指向右子节点
} TreeNode;

// 创建一个新节点
TreeNode* create_node(int value) {
    TreeNode* new_node = (TreeNode*)malloc(sizeof(TreeNode));
    if (new_node == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    new_node->value = value;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

// 示例：创建一个简单的二叉树
TreeNode* create_sample_tree() {
    TreeNode* root = create_node(1);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(4);
    root->left->right = create_node(5);
    return root;
}

 

（二）遍历树

  1. 二叉树的遍历：

    • 前序遍历：递归实现时，先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

void preorder_traversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->value);
    preorder_traversal(root->left);
    preorder_traversal(root->right);
}

中序遍历：递归实现时，先递归遍历左子树，然后访问根节点，最后递归遍历右子树。 

void inorder_traversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorder_traversal(root->left);
    printf("%d ", root->value);
    inorder_traversal(root->right);
}

后序遍历：递归实现时，先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

void postorder_traversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorder_traversal(root->left);
    postorder_traversal(root->right);
    printf("%d ", root->value);
}

层次遍历：使用队列实现。从根节点开始，逐层访问节点。

#include <queue.h> // 假设有一个简单的队列库

void level_order_traversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Queue* queue = create_queue();
    enqueue(queue, root);
    while (!is_queue_empty(queue)) {
        TreeNode* node = dequeue(queue);
        printf("%d ", node->value);
        if (node->left != NULL) {
            enqueue(queue, node->left);
        }
        if (node->right != NULL) {
            enqueue(queue, node->right);
        }
    }
    free_queue(queue);
}

（三）释放树的内存

在C语言中，需要手动释放动态分配的内存。以下是一个释放二叉树内存的代码示例：

void free_tree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

五、总结

树是一种非常重要的数据结构，它在计算机科学的许多领域都有广泛的应用。本文介绍了树的基本概念、常见的树类型以及一些基本操作。通过这些内容，读者可以对树有一个初步的了解，并能够在实际编程中应用这些知识。希望本文能够帮助大家更好地掌握树这一数据结构。

 

相关文章