数据结构 | 树的秘密-EW帮帮网

个人主页-爱因斯晨

文章专栏-数据结构

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

在这里插入图片描述

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

一、树的基本概念

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

二、二叉树的实现

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

1. 节点结构定义

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

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

// 二叉树节点结构
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;
}

三、代码解析

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

四、树的应用场景

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

五、总结

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

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

数据结构 | 树的秘密