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

大家好，欢迎来到IT知识分享网。

二叉搜索树（Binary Search Tree, BST）又称有序二叉树（Ordered Binary Tree），是一种特殊的二叉树，其中每个节点满足以下性质：

• 左子树的所有节点的值小于根节点的值。
• 右子树的所有节点的值大于根节点的值。
• 左右子树也分别是二叉搜索树。

二叉搜索树的主要优点是支持高效的查找、插入和删除操作，平均时间复杂度为 O(log⁡n)。

二叉搜索树的特点

1. 性质：

• 中序遍历二叉搜索树，可以得到一个升序的序列。
• 查找、插入和删除操作的时间复杂度为 O(log⁡n)（在平衡的情况下）。

2. 优点：

• 支持动态集合操作（查找、插入、删除）。
• 可以高效地实现范围查询。

3. 缺点：

• 如果树不平衡（例如退化为链表），时间复杂度会退化为 O(n)。
• 需要额外的平衡操作（如 AVL 树、红黑树）来保持平衡。

二叉搜索树的操作

1. 查找：

• 从根节点开始，比较目标值与当前节点的值：
• 如果目标值等于当前节点的值，返回当前节点。
• 如果目标值小于当前节点的值，递归查找左子树。
• 如果目标值大于当前节点的值，递归查找右子树。

2. 插入：

• 从根节点开始，找到合适的位置插入新节点：
• 如果树为空，新节点成为根节点。
• 如果目标值小于当前节点的值，递归插入左子树。
• 如果目标值大于当前节点的值，递归插入右子树。

3. 删除：

• 删除节点分为三种情况：
• 叶子节点：直接删除。
• 只有一个子节点：用子节点替换当前节点。
• 有两个子节点：找到右子树的最小节点（或左子树的最大节点），用其值替换当前节点的值，然后删除该最小节点。

二叉搜索树的实现

以下是C语言实现二叉搜索树的代码，包括插入、查找、删除和遍历操作：

#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; } // 插入节点 Node *insertNode(Node *root, int data) { if (root == NULL) { return createNode(data); // 如果树为空，创建新节点 } if (data < root->data) { root->left = insertNode(root->left, data); // 递归插入左子树 } else if (data > root->data) { root->right = insertNode(root->right, data); // 递归插入右子树 } return root; } // 查找节点 Node *searchNode(Node *root, int data) { if (root == NULL || root->data == data) { return root; // 找到目标节点或树为空 } if (data < root->data) { return searchNode(root->left, data); // 递归查找左子树 } else { return searchNode(root->right, data); // 递归查找右子树 } } // 找到右子树的最小节点 Node *findMin(Node *root) { while (root->left != NULL) { root = root->left; } return root; } // 删除节点 Node *deleteNode(Node *root, int data) { if (root == NULL) { return root; // 树为空，直接返回 } if (data < root->data) { root->left = deleteNode(root->left, data); // 递归删除左子树 } else if (data > root->data) { root->right = deleteNode(root->right, data); // 递归删除右子树 } else { // 找到目标节点 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; } else { // 有两个子节点 Node *temp = findMin(root->right); // 找到右子树的最小节点 root->data = temp->data; // 用最小节点的值替换当前节点的值 root->right = deleteNode(root->right, temp->data); // 删除右子树的最小节点 } } return root; } // 中序遍历 void inorderTraversal(Node *root) { if (root == NULL) { return; } inorderTraversal(root->left); // 遍历左子树 printf("%d ", root->data); // 访问根节点 inorderTraversal(root->right); // 遍历右子树 } // 释放二叉树内存 void freeTree(Node *root) { if (root == NULL) { return; } freeTree(root->left); // 释放左子树 freeTree(root->right); // 释放右子树 free(root); // 释放当前节点 } int main() { Node *root = NULL; // 插入节点 root = insertNode(root, 50); root = insertNode(root, 30); root = insertNode(root, 20); root = insertNode(root, 40); root = insertNode(root, 70); root = insertNode(root, 60); root = insertNode(root, 80); // 中序遍历 printf("中序遍历："); inorderTraversal(root); printf("\n"); // 查找节点 int target = 40; Node *result = searchNode(root, target); if (result != NULL) { printf("找到节点：%d\n", result->data); } else { printf("未找到节点：%d\n", target); } // 删除节点 printf("删除节点：40\n"); root = deleteNode(root, 40); printf("中序遍历："); inorderTraversal(root); printf("\n"); // 释放二叉树内存 freeTree(root); return 0; }

代码说明

1. createNode 函数：

• 创建一个新节点并返回。

2. insertNode 函数：

• 在二叉搜索树中插入新节点。

3. searchNode 函数：

• 在二叉搜索树中查找目标节点。

4. findMin 函数：

• 找到右子树的最小节点（用于删除操作）。

5. deleteNode 函数：

• 删除二叉搜索树中的目标节点。

6. inorderTraversal 函数：

• 中序遍历二叉搜索树，输出升序序列。

7. freeTree 函数：

• 递归释放二叉搜索树的内存。

8. 主函数：

• 创建二叉搜索树并插入节点。
• 查找节点并输出结果。
• 删除节点并输出中序遍历结果。
• 释放二叉搜索树内存。

示例输出

中序遍历：20 30 40 50 60 70 80 找到节点：40 删除节点：40 中序遍历：20 30 50 60 70 80 

总结

• 二叉搜索树是一种高效的数据结构，支持动态集合操作。
• 通过中序遍历可以得到有序的序列。
• 如果树不平衡，性能会下降，因此在实际应用中通常使用平衡二叉搜索树（如 AVL 树、红黑树）。