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

数据结构 | 树的秘密

news 2025/8/6 10:06:09

个人主页-爱因斯晨

文章专栏-数据结构

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

树是数据结构中一种重要的非线性结构，它以分层的方式存储数据，广泛应用于数据库索引、文件系统、编译器设计等领域。本文将通过 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函数负责为新节点分配内存并初始化。
插入操作：按照二叉搜索树的规则插入节点，即左子树的值小于根节点，右子树的值大于根节点。
遍历操作：
- 前序遍历：先访问根节点，再遍历左子树，最后遍历右子树
- 中序遍历：先遍历左子树，再访问根节点，最后遍历右子树（对二叉搜索树，中序遍历结果是有序的）
- 后序遍历：先遍历左子树，再遍历右子树，最后访问根节点
删除操作：删除节点需要考虑三种情况：
- 叶子节点：直接删除
- 只有一个子节点：用子节点替代当前节点
- 有两个子节点：用中序后继（右子树的最小值节点）替代当前节点
其他操作：实现了查找、计算树高、统计节点总数和释放内存等辅助功能。