数据结构（c++版）二叉搜索树全解析：从入门到精通

Jeff-Nolan

970人浏览 · 2025-10-22 11:00:18

Jeff-Nolan · 2025-10-22 11:00:18 发布

二叉搜索树（Binary Search Tree，BST）是数据结构领域的一颗明珠，它像一棵智能的"数字分拣树"，能够自动将数据按照特定规则组织起来。本文将带你从零开始，全方位理解二叉搜索树的原理和实现，通过大量生动的比喻和详细的代码注释，让你彻底掌握这一重要数据结构。

1. 二叉搜索树的概念与特点

1.1 什么是二叉搜索树？

想象你正在整理一个图书馆。如果所有书都随意堆放在一起，找一本书会很困难。但如果你按照书名的字母顺序排列，左边放字母顺序靠前的书，右边放字母顺序靠后的书，查找效率就会大大提高。二叉搜索树就是基于这种思想的数据结构。

二叉搜索树是一种特殊的二叉树，它具有以下性质：

有序性：对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值
唯一性：树中通常不允许有重复的值（某些实现可能允许）
递归结构：每个子树本身也是一棵二叉搜索树

1.2 二叉搜索树的节点结构

让我们先看看二叉搜索树的基本组成单元——节点的定义：

template<typename T>
struct TreeNode
{
    T data;                // 节点存储的核心数据（可以是任意类型）
    TreeNode<T>* left;     // 指向左子节点的指针，相当于"左边的书架"
    TreeNode<T>* right;    // 指向右子节点的指针，相当于"右边的书架"
    TreeNode():data(0), left(NULL), right(NULL) {};  // 默认构造函数，创建一个空节点
    TreeNode(T d) :data(d), left(NULL), right(NULL) {}; // 带参数的构造函数，创建包含数据的节点
};

这个结构体就像一个"图书分类卡"，包含：

data：这本书的关键信息（如书名）
left：指向字母顺序在这本书之前的所有书的分类卡
right：指向字母顺序在这本书之后的所有书的分类卡

2. 二叉搜索树的类框架

我们用一个类来封装二叉搜索树的所有操作：

template<typename T>
class BinarserchTree
{
private:
    TreeNode<T>* root;  // 树的根节点，就像图书馆的总目录
    
    // 内部递归方法
    TreeNode<T>* InsetNode(TreeNode<T>* node, T data);
    TreeNode<T>* DeleteNode(TreeNode<T>* node, T data);
    bool SerchNode(TreeNode<T>* node, T data);
    void inOrder(TreeNode<T>* root);
    bool updatanode(TreeNode<T>* node, T data1, T data2);
    
public:
    BinarserchTree() :root(NULL) {};  // 构造函数，初始化空树
    ~BinarserchTree();               // 析构函数，清理整棵树
    
    // 对外公开的API
    void Insert(T data) { root = InsetNode(root, data); }
    void Delete(T data) { root = DeleteNode(root,data); }
    bool Serch(T data) { return SerchNode(root, data); }
    void Order() { inOrder(root); cout << endl; }
    bool updatanode(T data1, T data2) { return updatanode(root, data1, data2); }
};

这个类就像是一个"图书馆管理系统"，提供了：

Insert()：添加新书
Delete()：下架旧书
Serch()：查找书籍
Order()：按顺序列出所有书籍
updatanode()：更新书籍信息

3. 核心操作详解

3.1 插入操作（Insert）

插入新节点的过程就像在图书馆中添加新书：

从根节点（图书馆入口）开始
比较新书与当前节点的值
- 如果小于当前节点，去左边"书架"继续查找插入位置
- 如果大于当前节点，去右边"书架"继续查找插入位置
直到找到一个空位置（NULL），就在那里插入新节点

template<typename T>
TreeNode<T>* BinarserchTree<T>::InsetNode(TreeNode<T>* node, T data)
{
    if (node == NULL)  // 找到合适的空位置了
    {
        // 创建新节点，相当于为新书制作一张分类卡
        return new TreeNode<T>(data);
    }
    
    // 决定新书应该放在左边还是右边的书架
    if (data < node->data)  // 新书字母顺序在当前书之前
    {
        node->left = InsetNode(node->left, data); // 去左边书架继续找位置
    }
    else if (data > node->data)  // 新书字母顺序在当前书之后
    {
        node->right = InsetNode(node->right, data); // 去右边书架继续找位置
    }
    
    // 如果data == node->data，这里不做处理（不允许重复值）
    return node; // 返回当前节点（可能已经更新了子节点）
}

3.2 查找操作（Search）

查找过程就像在图书馆中找一本特定的书：

从根节点开始
比较目标值与当前节点的值
- 如果相等，找到了！
- 如果小于当前值，去左边继续找
- 如果大于当前值，去右边继续找
如果遇到NULL指针，说明书不在图书馆中

template<typename T>
bool BinarserchTree<T>::SerchNode(TreeNode<T>* node, T data)
{
    if (node == NULL)  // 到达空书架，书没找到
    {
        return false;
    }

    if (data < node->data)  // 目标书在当前书的左边书架
    {
        return SerchNode(node->left, data); // 去左边继续找
    }
    else if(data > node->data)  // 目标书在当前书的右边书架
    {
        return SerchNode(node->right, data); // 去右边继续找
    }
    
    return true;  // 找到了！
}

3.3 删除操作（Delete）

删除是最复杂的操作，需要考虑三种情况：

情况1：删除叶子节点（没有子节点）

就像从树梢摘下一片叶子，直接移除即可。

情况2：删除有一个子节点的节点

就像修剪树枝的一个分叉，把剩下的枝条接上去。

情况3：删除有两个子节点的节点

需要找到右子树中的最小节点来替代被删除节点。

template<typename T>
TreeNode<T>* BinarserchTree<T>::DeleteNode(TreeNode<T>* node, T data)
{
    if (node == NULL)  // 空树或没找到要删除的节点
    {
        return NULL;
    }

    // 先找到要删除的节点
    if (data < node->data)  // 目标在左边
    {
        node->left = DeleteNode(node->left, data); // 去左边删除
    }
    else if (data > node->data)  // 目标在右边
    {
        node->right = DeleteNode(node->right, data); // 去右边删除
    }
    else {  // 找到了要删除的节点
        // 情况1：叶子节点（没有子节点）
        if (node->left == NULL && node->right == NULL)
        {
            delete node; // 直接删除
            return NULL; // 返回空指针给父节点
        }
        // 情况2：只有一个右子节点
        else if (node->left == NULL)
        {
            TreeNode<T>* noderight = node->right; // 保存右子树
            delete node; // 删除当前节点
            return noderight; // 用右子树替代当前节点
        }
        // 情况2：只有一个左子节点
        else if (node->right == NULL)
        {
            TreeNode<T>* nodeleft = node->left; // 保存左子树
            delete node; // 删除当前节点
            return nodeleft; // 用左子树替代当前节点
        }
        // 情况3：有两个子节点
        else {
            // 找到右子树中最小的节点（最左边的节点）
            TreeNode<T>* replace = node->right;
            while (replace->left)
            {
                replace = replace->left;
            }
            // 用右子树的最小值替换当前节点的值
            node->data = replace->data;
            // 删除右子树中的那个最小节点
            node->right = DeleteNode(node->right, replace->data);
        }
    }

    return node; // 返回处理后的节点
}

3.4 中序遍历（InOrder Traversal）

中序遍历会按照从小到大的顺序访问所有节点，就像按字母顺序列出图书馆中的所有书籍。

template<typename T>
void BinarserchTree<T>::inOrder(TreeNode<T> *node)
{
    if(node)  // 如果当前节点不为空
    {
        inOrder(node->left);  // 先遍历左子树（左边书架）
        cout << node->data << ","; // 输出当前节点的值（当前书）
        inOrder(node->right); // 再遍历右子树（右边书架）
    }
}

3.5 更新节点（Update）

更新操作实际上是先删除旧节点再插入新节点的组合操作：

template<typename T>
bool BinarserchTree<T>::updatanode(TreeNode<T>* node, T data1, T data2)
{
    if (SerchNode(node, data1))  // 先检查要更新的节点是否存在
    {
        node = DeleteNode(node, data1);  // 删除旧节点
        node = InsetNode(node, data2);   // 插入新节点
        return true;  // 更新成功
    }
    else {
        return false; // 更新失败（没有找到要更新的节点）
    }
}

4. 内存管理与析构函数

为了避免内存泄漏，我们需要在析构函数中正确释放所有节点：

template<typename T>
BinarserchTree<T>::~BinarserchTree()
{
    while (root)  // 只要树不为空
    {
        Delete(root->data);  // 不断删除根节点
    }
}

这个过程就像拆毁一座图书馆：

每次拆除最顶层的书架（根节点）
将其中的书（数据）移除
将剩下的书架重新组织
重复直到所有书架都被拆除

5. 完整测试代码分析

让我们通过测试代码看看二叉搜索树的实际表现：

int main()
{
    // 创建一个空的二叉搜索树（新建一个空图书馆）
    BinarserchTree<int> bst;
    
    // 插入一系列节点（入库新书）
    bst.Insert(20);  // 第一本书编号20
    bst.Insert(25);  // 第二本书编号25
    bst.Insert(29);
    bst.Insert(62);
    bst.Insert(31);
    bst.Insert(74);
    bst.Insert(98);
    bst.Insert(44);
    
    // 查找编号62的书是否存在
    cout << bst.Serch(62) << endl; // 输出1（true）
    
    // 按顺序列出所有书籍
    bst.Order(); // 输出：20,25,29,31,44,62,74,98,
    
    // 下架编号62的书
    bst.Delete(62);
    bst.Order(); // 输出：20,25,29,31,44,74,98,
    
    // 再次查找编号62的书
    cout << bst.Serch(62) << endl; // 输出0（false）
    
    // 更新操作
    cout << bst.updatanode(44, 5) << endl;  // 将44改为5，输出1（成功）
    bst.updatanode(15, 5);  // 尝试更新不存在的15，返回false
    bst.updatanode(31, 99); // 将31改为99
    bst.Order(); // 输出：5,20,25,29,74,98,99,
    
    return 0;
}

6. 二叉搜索树的性能分析

二叉搜索树的性能高度依赖于树的形状：

最佳情况（平衡树）：
- 查找、插入、删除的时间复杂度：O(log n)
- 树的高度最小，效率最高
最坏情况（退化为链表）：
- 时间复杂度退化为O(n)
- 例如连续插入已排序的数据：1,2,3,4,5,...

为了提高性能，可以使用更高级的平衡二叉搜索树，如：

AVL树
红黑树
B树/B+树（用于数据库系统）

7. 实际应用场景

二叉搜索树在计算机科学中有广泛应用：

数据库系统：用于索引实现快速查找
文件系统：目录结构的管理
网络路由：路由表查找
内存管理：内存分配器
游戏开发：场景管理、碰撞检测

8. 总结

通过本文的学习，你应该已经掌握了：

二叉搜索树的基本概念和特性
如何实现插入、查找、删除等核心操作
中序遍历的输出特性
如何更新树中的节点
二叉搜索树的性能特点和应用场景

记住，二叉搜索树是许多高级数据结构的基础。理解它的原理将为你学习更复杂的数据结构（如平衡树、哈希表等）打下坚实基础。

9.源码及运行：

#include<iostream>
using namespace std;

template<typename T>
struct TreeNode
{
	T data;
	TreeNode<T>* left;
	TreeNode<T>* right;
	TreeNode():data(0), left(NULL), right(NULL) {};
	TreeNode(T d) :data(d), left(NULL), right(NULL) {};

};
template<typename T>
class BinarserchTree
{
private:
	TreeNode<T>* root;
	
	TreeNode<T>* InsetNode(TreeNode<T>* node, T data);
	TreeNode<T>* DeleteNode(TreeNode<T>* node, T data);
	bool SerchNode(TreeNode<T>* node, T data);
	void inOrder(TreeNode<T>* root);//中序遍历
	bool updatanode(TreeNode<T>* node, T data1, T data2);
public:
BinarserchTree() :root(NULL) {};
	~BinarserchTree();
	void Insert(T data)
	{
		root = InsetNode(root, data);//根节点可能会发生改变所以要更新根节点
	}
	void Delete(T data)
	{
		root = DeleteNode(root,data);
	}
	bool Serch(T data)
	{
		return SerchNode(root, data);
	}
	void Order()
	{
		inOrder(root);//root是私有变量，中序遍历在外部调用不用传参数
		cout << endl;
	}
	bool updatanode(T data1,T data2)
	{
	  return updatanode(root, data1, data2);
	}

}; 
template<typename T>
bool BinarserchTree<T>::updatanode(TreeNode<T>* node, T data1, T data2)
{
	if (SerchNode(node, data1))
	{
		node=DeleteNode(node, data1);
		node=InsetNode(node, data2);
		return true;

	}
	else {
		return false;
	}
	
	
}
template<typename T>
BinarserchTree<T>::~BinarserchTree()
{
	while (root)
	{

		Delete(root->data);
	}

}
template<typename T>
TreeNode<T>* BinarserchTree<T>::InsetNode(TreeNode<T>* node, T data)
{
	if (node == NULL)
	{
		//判断是否是空树，是空树就新建节点来添加未添加的节点
		
		return  new TreeNode<T>(data);//该返回值需要有节点接受 根据具体大小来判断是左还是右子树承接
}
	if (data < node->data)
	{
		node->left=InsetNode(node->left, data);
	}
	else if (data > node->data)
	{
		node->right=InsetNode(node->right, data);
	}
	
	return node;

}

template<typename T>
TreeNode<T>* BinarserchTree<T>::DeleteNode(TreeNode<T>* node, T data)
{
	if (node == NULL)
	{
		return NULL;
	}

	if (data < node->data)
	{
		node->left = DeleteNode(node->left, data);//往左子树去寻找要删除的值并返回到左节点
	}
	else if (data > node->data)
	{
		node->right = DeleteNode(node->right, data);//跟左同理
	}
	else {
		if (node->left == NULL && node->right == NULL)//找到了 同时为叶子节点
		{
			delete node;
			return NULL;
		}
		else if (node->left == NULL)
		{
			TreeNode<T>* noderight = node->right;//保存该节点的右子树
			delete node;//删除该节点
			return noderight;//返回该节点的右子树

		}
		else if (node->right == NULL)
		{
			TreeNode<T>* nodeleft = node->left;//保存该节点的左子树
			delete node;//删除该节点
			return nodeleft;//返回该节点的左子树

		}
		else {
			TreeNode<T>* replace = node->right;
			while (replace->left)
			{
				replace = replace->left;//找到右子树最左边的节点
			}
			node->data = replace->data;//把要删除的节点变成右子树最小值节点来替代
			node->right = DeleteNode(node->right, replace->data);//递归调用删除函数把右边的最小值删除掉
		}
		
	}

	return node;//删除完毕后返回节点；
}

template<typename T>
bool BinarserchTree<T>::SerchNode(TreeNode<T>* node, T data)
{
	if (node == NULL)
	{
		return false;
	}

	if (data < node->data)
	{
		return SerchNode(node->left, data);
	}
	else if(data>node->data){
	return 	SerchNode(node->right, data);

		}
	
	return true;

}
template<typename T>
void BinarserchTree<T>::inOrder(TreeNode<T> *node)
{
     if(node)
	{
		inOrder(node->left);
		cout << node->data<<",";
		inOrder(node->right);
	}


 }

int main()
{
	BinarserchTree<int> bst;
	bst.Insert(20);
	bst.Insert(25);
	bst.Insert(29);
	bst.Insert(62);
	bst.Insert(31);
	bst.Insert(74);
	bst.Insert(98);
	bst.Insert(44);
	cout<<bst.Serch(62)<<endl;
	bst.Order();
	bst.Delete(62);
	bst.Order();
	cout<<bst.Serch(62)<<endl;
	cout<<bst.updatanode(44, 5)<<endl;
	bst.updatanode(15, 5);
	bst.updatanode(31, 99);
	bst.Order();
	return 0;
}

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

SeedVR2终极指南：如何用单步扩散模型实现专业级视频修复

还在为老旧视频的模糊画质而烦恼吗？面对抖动严重的监控录像或褪色的家庭影像，你是否曾希望有一种简单高效的修复方案？SeedVR2正是为解决这些痛点而生的一站式视频修复工具。作为字节跳动推出的先进视频修复模型，它能够在单步推理中实现专业级的视频质量提升，彻底改变了传统视频修复的工作流程。## 核心价值：为什么选择SeedVR2进行视频修复？**传统视频修复的三大瓶颈**：1. **计算成本高

AI Agent技术社区

深度解析Amlogic S9xxx电视盒子Armbian系统：从闲置设备到Linux服务器的终极实战指南

你是否拥有一台闲置的Amlogic S9xxx系列电视盒子？想让它摆脱单一的视频播放功能，变身为功能强大的Linux服务器、开发平台或家庭媒体中心？本指南将为你详细解析如何通过Armbian系统实现这一转变，让你的电视盒子重获新生，成为高性能的Linux设备。Armbian系统基于Debian/Ubuntu构建，专为ARM芯片优化，提供了完整的Linux生态支持。## 🎯 核心价值与独特优势

AI Agent技术社区

CANN/runtime Event管理API

本章节描述 CANN Runtime 的 Event 管理接口，用于事件的创建、记录、同步、计时及 IPC 跨进程共享。- [`aclError aclrtCreateEvent(aclrtEvent *event)`](#aclrtCreateEvent)：创建Event，创建出来的Event可用于统计两个Event之间的耗时、多Stream之间的任务同步等场景。- [`aclError