个旧网站建设公司,哈尔滨百度推广代理,西安火车站建设,住房和城乡建设部网站评估目录 实现思路
插入操作
删除操作
完整代码
测试案例
总结 二叉搜索树#xff08;Binary Search Tree#xff0c;BST#xff09;是一种常用的数据结构#xff0c;它具有以下特点#xff1a;
左子树上所有节点的值均小于它的根节点的值右子树上所有节点的值均大于它的…目录 实现思路
插入操作
删除操作
完整代码
测试案例
总结 二叉搜索树Binary Search TreeBST是一种常用的数据结构它具有以下特点
左子树上所有节点的值均小于它的根节点的值右子树上所有节点的值均大于它的根节点的值左右子树也分别为二叉搜索树
在实际应用中BST被广泛使用例如在数据库中的索引、哈希表等。
本文将介绍如何使用递归的方式实现BST并提供完整代码和测试案例。
实现思路
BST的基本操作包括查找、插入和删除。这里我们只讲解递归方式实现BST的插入和删除操作。
插入操作
插入操作可以分为两种方式
版本一传入父节点通过比较key值大小递归向下寻找插入位置。版本二使用引用第一步传参时root是_root的别名递归过程中root是父节点指向它的指针的别名修改root就是修改了父节点的连接。
版本二的实现方式更加简洁因此我们选择使用版本二来实现插入操作。
删除操作
删除操作也可以分为两种方式
版本一传入父节点通过比较key值大小递归向下寻找删除节点。版本二使用引用第一步传参时root是_root的别名递归过程中root是父节点_left或·_right的别名修改root就是修改了父节点的连接。
版本二同样更加简洁因此我们选择使用版本二来实现删除操作。需要注意的是当删除节点有两个子节点时需要先找到其左子树中最大的节点或右子树中最小的节点将其值替换到要删除的节点上再删除左子树中最大的节点或右子树中最小的节点。 无论是查找、插入、删除如果使用递归都需要传参根节点通过根节点来递归处理子问题但是在类的实现中成员变量根节点_root是私有变量在类外无法访问针对这种问题C常见的处理方式就是套用一层接口函数定义对应功能的私有函数提供给接口函数调用用户直接调用接口函数和之前没有区别接口函数内再调用对应功能的私有函数私有函数只在类中使用自然就可以调用BST的私有成员_root。
完整代码
#includeiostream
using namespace std;template class K
class BSTreeNode
{
public:BSTreeNodeK* _left;BSTreeNodeK* _right;K _key;BSTreeNode(const K key):_left(nullptr), _right(nullptr), _key(key){ }
};templateclass K
class BSTree
{typedef BSTreeNodeK Node;
public:bool Find(const K key){return _Find(_root, key);}bool Insert(const K key){return _Insert2(_root, key);}void midOrder(){_midOrder(_root);}bool Erase(const K key){return _Erase(_root, key);}
private:Node* _root nullptr;bool _Find(Node* root, const K key){if (root nullptr)return false;if (key root-_key){return _Find(root-_left, key);}else if (key root-_key){return _Find(root-_right, key);}else{return true;}}void _midOrder(Node* root){if (root nullptr)return;_midOrder(root-_left);cout root-_key ;_midOrder(root-_right);}bool _Insert2(Node* root, const K key){if (root nullptr){root new Node(key);return true;}if (key root-_key)return _Insert2(root-_left, key);else if (key root-_key)return _Insert2(root-_right, key);elsereturn false;}bool _Erase(Node* root, const K key){if (root nullptr)return false;if (key root-_key)return _Erase(root-_left, key);else if (key root-_key)return _Erase(root-_right, key);else{if (root-_left nullptr){Node* del root;root root-_right;delete del;}else if (root-_right nullptr){Node* del root;root root-_left;delete del;}else{//要删除的节点有两个子节点替换法//先找到一个合适的替换节点然后把值替换//合适的替换节点绝对是上面的几种情况只有左子树、只有右子树、没有子节点Node* subRight root-_left;while (subRight-_right){subRight subRight-_right;}swap(root-_key, subRight-_key);//交换值后目前虽然整棵树不是搜索二叉树但是root的左右子树都还是BST递归去删除即可return _Erase(root-_left, key);}}return true;}
};int main()
{int a[] { 8,3,1,6,4,7,14,13 };BSTreeint bst;for (int x : a){bst.Insert(x);}bst.midOrder();//测试遍历删除for (int x : a){bst.midOrder();cout endl;bst.Erase(x);bst.midOrder();cout endl;cout endl;}cout 全部删除成功 endl;system(pause);return 0;
}测试案例
int a[] { 8,3,1,6,4,7,14,13 };
BSTreeint bst;
for (int x : a)
{bst.Insert(x);
}
bst.midOrder();//测试遍历删除
for (int x : a)
{bst.midOrder();cout endl;bst.Erase(x);bst.midOrder();cout endl;cout endl;
}cout 全部删除成功 endl;构建的二叉树如下 运行结果如下
1 3 4 6 7 8 13 14
1 3 4 6 7 8 13 14
1 3 4 6 7 8 13 14 1 3 4 6 7 13 14
1 3 4 6 7 13 14
1 3 4 6 7 13 14 1 3 4 6 13 14
1 3 4 6 13 14
1 3 4 6 13 14 1 3 4 6 13
1 3 4 6 13
1 3 4 6 13 1 3 4 6
1 3 4 6
1 3 4 6 1 3 4
1 3 4
1 3 4 1 3
1 3
1 3 1
1
1 全部删除成功总结
本文介绍了使用递归的方式实现BST的插入和删除操作并提供了完整代码和测试案例。递归虽然简洁但需要注意递归边界条件、参数传递方式等问题。在实际应用中也可以使用迭代的方式实现BST的基本操作。
