贵阳培训网站建设,有哪些官方网站做的比较好,wordpress采集 爬虫,深圳龙岗区住房和建设局网站官网目录前言一、二叉搜索树的概念二、二叉搜素树的模拟实现#xff08;增删查非递归实现#xff09;1. 二叉搜素树的结点2. 二叉搜索树的实现#xff08;1#xff09;. 二叉搜索树的基本结构#xff08;2#xff09;构造函数#xff08;3#xff09;查找函数#xff08;4…
目录前言一、二叉搜索树的概念二、二叉搜素树的模拟实现增删查非递归实现1. 二叉搜素树的结点2. 二叉搜索树的实现1. 二叉搜索树的基本结构2构造函数3查找函数4插入函数5 删除函数6中序遍历7析构函数8拷贝构造函数9赋值运算符重载现代写法三、二叉搜索树的模拟实现增删查递归实现1. 查找函数2. 插入函数3. 删除函数前言 在数据结构初阶我们学习了二叉树的相关知识普通的二叉树的作用只是用来存储数据并没有任何的性质所以在任何方面都没有什么优势今天学习的二叉搜索树是在普通的二叉树的基础上加上了一些性质使整体的搜索效率大大提升。 一、二叉搜索树的概念
二叉搜索树可能是一棵空树也可能是一棵具有以下性质的二叉树
如果左子树存在则左子树所有结点的值都比根节点的值小如果右子树存在则右子树所有结点的值都比根节点的值大树是递归创建的所以二叉搜索树中的每一棵子树都要满足以上性质
二、二叉搜素树的模拟实现增删查非递归实现
1. 二叉搜素树的结点
// 二叉搜索树的结点
template class K
struct BSTreeNode
{// 成员函数//成员变量BSTreeNodeK* _left;// 指向左孩子的指针指针域BSTreeNodeK* _right;// 指向右孩子的指针指针域K _key;// 存储数据的地方数据域
};二叉搜索树的结点中需要包含三个内容
_left:指向左孩子的结点的指针通过这个指针找到左孩子如果这个指针为空指针说明当前这棵树不存在左子树_right:指向右孩子的结点的指针通过这个指针找到右孩子如果这个指针为空指针说明当前这棵树不存在右子树_key:数据域存放结点的数据的一般也称为是二叉搜索树的关键字二叉搜索树的性质就是以这个关键字为准的
2. 二叉搜索树的实现
1. 二叉搜索树的基本结构
// 二叉搜素树的基本结构
template class K
class BSTree
{// 需要使用结点类型typedef BSTreeNodeT Node;public:// 成员函数private:// 成员变量Node* _root nullptr;
};二叉搜索树的底层本质上就是一个根节点然后通过这个根节点无限去创建其左右子树在树中需要使用树的结点类型所以为了方便表示可以在树中对树的结点类型进行重定义这个技巧在list的实现中也用到过。刚开始_root的值默认为nullptr。
2构造函数
树不需要实现构造函数只需要给_root一个缺省值即可。
3查找函数
// 查找函数bool find(const K key){Node* cur _root;while (cur){if (key cur-_key){cur cur-_key;}else if(keycur-_key){cur cur-_right;}else{// 找到了return true;}}// 找不到return false;}上面这个代码中是不需要单独判断树为空树的情况的因为当树为空树的时候那么_root nullptr此时cur nullptr所以循环压根不会进去直接返回false。
4插入函数
// 插入函数bool insert(const K key){if (_root nullptr){// 空树_root new Node(key);return true;}// 非空树// 找到插入的地方Node* cur _root;// 找插入的位置Node* parent nullptr;// 记录cur的父亲while (cur){if (key cur-_key){// 左子树找parent cur;cur cur-_left;}else if (key cur-_key){// 右子树找parent cur;cur cur-_right;}else{// 找到相等的值不允许插入return false;}}// 当cur为空的时候跳出循环找到插入的位置cur new Node(key);if (key parent-_key){// 插在左子树parent-_left cur;}else{parent-_right cur;}return true;}思路 主题判断空树的情况如果是空树将结点直接插入在根其他情况先找到插入的位置使用一个cur结点指针去标识找插入的位置parent结点指针去记录cur的父亲结点所以在cur找到了插入的位置之后那么parent就是插入位置的父亲查找的过程中如果key的值比cur的值小那么就是插入在左子树如果key的值比cur的值大那么就是插入在右子树如果出现key的值和cur的值是相等的则说明树中存在该值不允许插入。最终当cur走到空的时候则找到插入的位置此时需要判断cur应该插入在parent的左边还是右边可以通过插入的值和parent的值进行对比如果插入的值比parent的值小则插入在左子树否则插入在右边。 测试查找和插入函数 代码
void test_BSTree1()
{BSTreeint t;t.insert(1);t.insert(3);t.insert(2);t.insert(6);t.insert(5);t.insert(9);// 查找cout 1: t.find(1) endl;cout 2: t.find(2) endl;cout 3: t.find(3) endl;cout 4: t.find(4) endl;cout 5: t.find(5) endl;cout 6: t.find(6) endl;}运行结果
5 删除函数
// 删除函数bool erase(const K key){Node* cur _root;Node* parent nullptr;while (cur){// 找删除的值if (key cur-_key){// 左子树找parent cur;cur cur-_left;}else if (key cur-_key){// 右子树找parent cur;cur cur-_right;}else{// 找到了// 分类讨论// 1. 左孩子空包含叶子节点// 2. 右孩子为空不包含叶子节点// 3. 左右孩子都不为空if (cur-_left nullptr){// 左子树为空右子树不一定为空if (cur _root){// cur就是根结点_root cur-_right;}else{// cur不是根,cur的父亲结点是parentif (cur parent-_left){parent-_left cur-_right;}else{parent-_right cur-_right;}}delete cur;}else if (cur-_right nullptr){// 右子树为空左子树一定不为空if (cur _root){// cur是根节点_root cur-_left;}else{// cur不是根节点cur的父亲就是parentif (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}}delete cur;}else{// 左子树和右子树都不为空// 找到删除结点所在树的右子树中的最小值Node* minRight cur-_right;Node* minparent cur;while (minRight-_left){minparent minRight;minRight minRight-_left;}swap(cur-_key, minRight-_key);if (minparent-_left minRight){minparent-_left minRight-_right;}else{minparent-_right minRight-_right;}delete minRight;}return true;}}// cur走到空说明树中不存在这个值所以删除是被失败return false;}思路 找到删除的值的结点如果找不到则删除失败空树也是属于找不到的一种情况如果找到了需要对删除的结点进行分类讨论 左孩子为空不存在左子树右子树是否存在不一定可能存在也可能不存在当右子树不存在的时候此时该结点的左右子树均不存在属于叶子结点右孩子为空此时左孩子一定不为空因为左孩子为空的情况属于上面的请情况所以这种情况的结点只存在右子树左右孩子均不为空同时存在左右子树的结点需要采取替换法然后转化为第一或者第二种情况进行删除。 细节 在第一种情况和第二种情况中删除的可能是根节点当根节点没有左子树的时候就属于第一种情况当根节点没有右子树的时候就属于第二种情况如果删除的是根节点该结点左子树为空时则需要更新根节点到删除结点的右子树该结点的右子树为空的时候需要更新根节点到该节点的左子树。第三种情况采取替换法先找到删除的结点的左子树的最大值结点或者右子树的最小值结点找这两种结点的原因是这个结点和删除的结点交换后可以保证该值比左子树的所有结点值都大比右子树所有结点值都小。迭代的过程中一定要记录minRight的父亲最终才能让该父亲去托管minRight的右子树这个minparent一定是从删除的结点开始因为minRight可能就是删除结点的右子树的根节点这种情况就是删除结点的右子树的根节点没有左孩子的此时循环是不会进去的这种情况的minRight就是删除结点的右子树的根节点那么其父亲就是删除的结点所以在交换删除结点的值和minRight的值之后问题就转化为删除minRight此时minRight的左子树一定是空的所以就算删除情况的第一种情况。 6中序遍历
// 中序遍历void InOrder(){// 因为在类外的对象不方便使用根节点所以需要套一层进行递归_InOrder(_root);cout endl;}// 中序遍历的子函数void _InOrder(Node* root){if (root nullptr){return;}// 先遍历左子树_InOrder(root-_left);// 再访问根节点cout root-_key ;// 最后遍历右子树_InOrder(root-_right);}思路在我们之前学习的二叉树的中序遍历中是直接进行递归的因为C语言实现的二叉树并不是封装的也就是对象可以直接访问树中的任何成员但是C不同C采用类对象进行封装的结构类外的对象是不能访问类中的私有成员的所以在类外不能访问到树的根节点所以我们采取的方法就算套一层进行递归。递归的思路和之前一样中序遍历就算先递归左子树再访问根节点的值再递归右子树。 7析构函数
二叉树中的结点都需要析构函数进行释放所以析构函数需要我们自己实现编译器形成析构函数无法完成这项工作。析构函数的实现思想同样采用递归的思路而且采用的是后序递归就是先将树的左子树递归再递归右子树最后将根节点释放。还有代码中的析构函数是public的DestroyTree函数是私有的析构函数是要给类外的对象进行使用的
public:
// 析构函数~BSTree(){DestroyTree(_root);}private:
void DestroyTree(Node* root){if (root nullptr){// 空树return;}// 通过后序递归的方法将树中的每一个结点释放DestroyTree(root-_left);DestroyTree(root-_right);delete root;}8拷贝构造函数
编译器默认生成的拷贝构造函数完成浅拷贝如果采用拷贝会导致两棵树中的根节点指针指向同一个根节点也就是最终的两棵树是同一棵树但是有两个对象所以最终两个对象在生命周期到的时候都会调用析构函数清理资源所以会出现同一棵树被清理两次从而使程序崩溃。
void test_BSTree4()
{int a[] { 2,3,7,1,5,9 };BSTreeint t;for (auto e : a){t.insert(e);}t.InOrder();cout endl;BSTreeint t1 t;t1.InOrder();
}运行结果
深拷贝 代码
// 拷贝构造函数
public:BSTree(const BSTreeK t){_root copyTree(t._root);}private:
// copy函数Node* copyTree(const Node* root){if (root nullptr){return nullptr;}Node* newnode new Node(root-_key);newnode-_left copyTree(root-_left);newnode-_right copyTree(root-_right);return newnode;}
// 测试代码
void test_BSTree4()
{int a[] { 2,3,7,1,5,9 };BSTreeint t;for (auto e : a){t.insert(e);}t.InOrder();cout endl;BSTreeint t1 t;// 调用拷贝构造函数t1.InOrder();
}运行结果
9赋值运算符重载现代写法
// 赋值运算符重载BSTreeK operator(BSTreeK t){swap(_root, t._root);return *this;}void test_BSTree5()
{int a[] { 2,3,7,1,5,9 };BSTreeint t;for (auto e : a){t.insert(e);}t.InOrder();cout endl;BSTreeint t1;t1 t;// 调用赋值运算符重载t1.InOrder();
}运行结果
三、二叉搜索树的模拟实现增删查递归实现
1. 查找函数
public:// 递归版本bool FindR(const K key){return _FindR(_root,key);}
private:// 查找函数的子函数递归版本bool _FindR(Node* root,const K key){if (root nullptr){// 空树return false;}// 非空树if (key root-_key){// 左子树找return _FindR(root-_left, key);}else if (key root-_key){// 右子树找return _FindR(root-_right, key);}else{// 找到了return true;}}
//测试代码
void test_BSTree6()
{// 测试树的非递归查找函数int a[] { 2,3,7,1,5,9 };BSTreeint t;for (auto e : a){t.insert(e);}t.InOrder();for (auto e : a){cout t.FindR(e) ;}
}
运行结果
2. 插入函数
public:
// 插入函数递归版本bool InsertR(const K key){return _InsertR(_root, key);}
private:// 插入函数递归版本的子函数bool _InsertR(Node* root, const K key){if (root nullptr){root new Node(key);return true;}// 查找插入的位置if (key root-_key){// 插入在当前树的左子树return _InsertR(root-_left, key);}else if (key root-_key){// 插入在当前树的右子树return _InsertR(root-_right, key);}else{// 该值在树中已经存在插入失败return false;}}
// 测试代码
void test_BSTree7()
{// 测试插入函数的递归版本int a[] { 2,3,7,1,5,9 };BSTreeint t;for (auto e : a){t.InsertR(e);}t.InOrder();}
运行结果
3. 删除函数
public:
// 删除函数的递归版本bool EraseR(const K key){return _EraseR(_root, key);}
private:// 删除函数递归版本的子函数bool _EraseR(Node* root, const K key){if (root nullptr){// 空树return false;}// 非空树找删除的结点if (key root-_key){// 到左子树找return _EraseR(root-_left, key);}else if (key root-_key){// 到右子树找return _EraseR(root-_right, key);}else{// 找到了// 分类讨论Node* del root;if (root-_left nullptr){// 左子树为空root root-_right;}else if (root-_right nullptr){// 右子树为空root root-_left;}else{// 左右子树均不为空// 替换法Node* minRight root-_right;while (minRight-_left){minRight minRight-_left;}swap(minRight-_key, root-_key);// 转化为第一种情况return _EraseR(root-_right, key);}delete del;return true;}}
// 测试代码void test_BSTree8()
{// 测试插入函数的递归版本int a[] { 2,3,7,1,5,9 };BSTreeint t;for (auto e : a){t.InsertR(e);}t.InOrder();t.EraseR(7);t.InOrder();t.EraseR(1);t.InOrder();for (auto e : a){t.EraseR(e);}t.InOrder();
}
运行结果
