二叉搜索树入门指南：高效查找的数据结构实现

19339201706

一、简介和应用

二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树数据结构，其中每个节点的值大于其左子树所有节点的值，小于其右子树所有节点的值。这种特性使得BST在查找、插入和删除操作上具有很高的效率。

‌应用场景‌：

• 数据库索引实现
• 文件系统目录管理
• 字典和电话簿实现
• 游戏中的高分排行榜
• 网络路由表
• 内存分配管理
  
  

BST的平均时间复杂度为O(log n)，在数据有序性要求高且需要频繁查找的场景中表现优异。

二、注意事项

• 平衡问题：不平衡的BST会退化为链表，效率降低
• 重复值：标准BST不支持重复值(需要特殊处理)
• 删除策略：删除节点有多种情况需要考虑
• 内存管理：需要手动释放删除的节点
• 递归深度：大量数据可能导致栈溢出
  
  

三、实现步骤解析

• ‌定义节点结构‌：创建包含数据、左指针和右指针的结构体
• ‌初始化BST‌：创建根节点并维护节点计数器
• ‌实现核心操作‌：
  
  
  • 插入节点：递归找到合适位置插入新节点
  • 查找节点：利用BST特性快速定位
  • 删除节点：处理三种情况(无子节点、单子节点、双子节点)
    
    
• ‌辅助功能‌：
  
  
  • 查找前驱节点：用于删除操作
  • 查找最小值：用于删除双子节点情况
    
    
• ‌实现遍历‌：
  
  
  • 前序遍历：根-左-右顺序
  • 中序遍历：左-根-右顺序(得到有序序列)
    
    

四、完整代码和注释

1. #include<iostream>
   
2. using namespACe std;
   
3. 
   
4. // 定义二叉搜索树节点结构
   
5. struct treenode{
   
6.     int data=0;            // 节点存储的数据，默认为0
   
7.     treenode* left=nullptr;  // 左子节点指针，默认为空
   
8.     treenode* right=nullptr; // 右子节点指针，默认为空
   
9. };
   
10. 
    
11. // 定义二叉搜索树类
    
12. class binaryfindtree{
    
13.     treenode* root=new treenode; // 根节点
    
14.     int sum = 0;                 // 节点计数器
    
15.    
    
16.     // 内部递归插入方法
    
17.     void add(int data, treenode* root){
    
18.         if (sum==0){             // 如果是第一个节点
    
19.             root->data = data;   // 直接赋值给根节点
    
20.         }else{
    
21.             if(data<root->data){ // 如果数据小于当前节点
    
22.                 if(root->left)   // 如果左子节点存在
    
23.                     add(data, root->left); // 递归向左子树插入
    
24.                 else {           // 如果左子节点不存在
    
25.                     root->left = new treenode; // 创建新节点
    
26.                     root->left->data = data;   // 赋值
    
27.                 }
    
28.             }else{               // 如果数据大于等于当前节点
    
29.                 if(root->right)  // 如果右子节点存在
    
30.                     add(data, root->right); // 递归向右子树插入
    
31.                 else {           // 如果右子节点不存在
    
32.                     root->right = new treenode; // 创建新节点
    
33.                     root->right->data = data;   // 赋值
    
34.                 }
    
35.             }
    
36.         }
    
37.         sum++; // 节点计数增加
    
38.     }
    
39.    
    
40.     // 内部递归查找方法
    
41.     treenode* get(int data, treenode* root){
    
42.         if (!root)              // 如果节点为空
    
43.             return nullptr;      // 返回空指针
    
44.         if (root->data == data) // 如果找到数据
    
45.             return root;         // 返回当前节点
    
46.         if (data < root->data)  // 如果数据小于当前节点
    
47.             return get(data, root->left); // 递归左子树查找
    
48.         else                    // 如果数据大于当前节点
    
49.             return get(data, root->right); // 递归右子树查找
    
50.     }
    
51.    
    
52.     // 查找指定节点的父节点
    
53.     treenode* getpre(int data, treenode* root) {
    
54.         if (!root)              // 如果节点为空
    
55.             return nullptr;      // 返回空指针
    
56.         if (!root->left and !root->right) // 如果是叶子节点
    
57.             return nullptr;      // 返回空指针
    
58.             
    
59.         // 检查左子节点
    
60.         if (!root->left){       // 如果没有左子节点
    
61.             if (root->right->data == data) // 如果右子节点匹配
    
62.                 return root;     // 返回当前节点(父节点)
    
63.         }else{
    
64.             if (!root->right){  // 如果没有右子节点
    
65.                 if (root->left->data == data) // 如果左子节点匹配
    
66.                     return root; // 返回当前节点(父节点)
    
67.             }else{              // 如果有两个子节点
    
68.                 if (root->left->data == data or root->right->data == data) // 如果任一子节点匹配
    
69.                     return root; // 返回当前节点(父节点)
    
70.             }
    
71.         }
    
72.         
    
73.         // 递归查找左右子树
    
74.         if (getpre(data, root->left)) // 先在左子树查找
    
75.             return getpre(data, root->left);
    
76.         else                         // 再在右子树查找
    
77.             return getpre(data, root->right);
    
78.     }
    
79.    
    
80.     // 查找子树中的最小节点
    
81.     treenode* mindata(treenode* root) {
    
82.         if (!root->left)       // 如果没有左子节点
    
83.             return root;        // 当前节点就是最小节点
    
84.         return mindata(root->left); // 递归查找左子树
    
85.     }
    
86.    
    
87.     // 内部递归删除方法
    
88.     treenode* del(int data, treenode* root){
    
89.         if (!root or (!root->left and !root->right)) // 空树或只有根节点
    
90.             return nullptr;
    
91.             
    
92.         treenode* tmp = get(data, root); // 找到要删除的节点
    
93.         treenode* pre = getpre(data, root); // 找到父节点
    
94.         bool lr = pre->right == tmp;     // 判断是左子节点还是右子节点
    
95.         
    
96.         // 情况1: 要删除的节点是叶子节点
    
97.         if (!tmp->left and !tmp->right){
    
98.             !lr ? pre->left = nullptr : pre->right = nullptr; // 父节点对应指针置空
    
99.             return root;
    
100.         }
     
101.         
     
102.         // 情况2: 要删除的节点只有一个子节点
     
103.         if (!tmp->right)                // 只有左子节点
     
104.             !lr ? pre->left = tmp->left : pre->right = tmp->left; // 用左子节点替代
     
105.         else{
     
106.             if (!tmp->left)             // 只有右子节点
     
107.                 !lr ? pre->left = tmp->right : pre->right = tmp->right; // 用右子节点替代
     
108.             else{                       // 情况3: 有两个子节点
     
109.                 tmp->data = mindata(root->right)->data; // 用右子树最小节点值替换
     
110.                 tmp->right = del(tmp->data, mindata(root->right)); // 删除右子树最小节点
     
111.             }
     
112.         }
     
113.         sum--; // 节点计数减少
     
114.         return root;
     
115.     }
     
116.    
     
117.     // 前序遍历(根-左-右)
     
118.     void preorder(treenode* root)
     
119.     {
     
120.         if (!root)              // 如果节点为空
     
121.             return;             // 返回
     
122.         cout << root->data << " "; // 先访问根节点
     
123.         preorder(root->left);   // 再遍历左子树
     
124.         preorder(root->right);  // 最后遍历右子树
     
125.     }
     
126.    
     
127.     // 中序遍历(左-根-右)
     
128.     void inorder(treenode* root){
     
129.         if (!root)              // 如果节点为空
     
130.             return;             // 返回
     
131.         inorder(root->left);    // 先遍历左子树
     
132.         cout << root->data << " "; // 再访问根节点
     
133.         inorder(root->right);   // 最后遍历右子树
     
134.     }
     
135.    
     
136. public:
     
137.     // 公开插入接口
     
138.     void add(int data){
     
139.         add(data, root);
     
140.     }
     
141.    
     
142.     // 查找接口
     
143.     bool find(int data){
     
144.         return get(data, root) != nullptr; // 转换为bool值返回
     
145.     }
     
146.    
     
147.     // 删除接口
     
148.     void del(int data){
     
149.         root = del(data, root);
     
150.     }
     
151.    
     
152.     // 中序遍历接口
     
153.     void inorder(){
     
154.         inorder(root);
     
155.         cout << endl;
     
156.     }
     
157.    
     
158.     // 前序遍历接口
     
159.     void preorder()
     
160.     {
     
161.         preorder(root);
     
162.         cout << endl;
     
163.     }
     
164. };

复制代码

来源：大矩学习资料