p2p金融网站建设,获取当前分类的父级wordpress,怎么做拍卖网站吗,十大网站免费二叉搜索树是一个很重要的数据结构#xff0c;它的特殊结构可以在很短的时间复杂度找到我们想要的数据。最坏情况下的时间复杂度是O(n)#xff0c;最好是O(logn)。接下来看一看它的接口函数的实现。 为了使用方便#xff0c;这里采用模版的方式#xff1a;
一、节点
temp… 二叉搜索树是一个很重要的数据结构它的特殊结构可以在很短的时间复杂度找到我们想要的数据。最坏情况下的时间复杂度是O(n)最好是O(logn)。接下来看一看它的接口函数的实现。 为了使用方便这里采用模版的方式
一、节点
template class K
struct BSnode
{BSnode(K key):_key(key){}K _key;BSnode* _left nullptr;BSnode* _right nullptr;
};_key用来储存数据_left和_right用来储存左子树和右子树的节点。
二、搜索树的类的定义
template class K
class BSTree
{
private:using Node BSnodeK;Node* _root nullptr;
}; 这里typedef了BSnodeK为Node的类型方便使用。并创建了根节点缺省值为空指针。
三、搜索树的插入 搜索树的结构是左子树所有节点的值小于等于根结点的值右子树所有节点的值大于等于根节点的值。在这里我不考虑等于的情况即一棵树中不允许出现相同的值。代码如下 //搜索树的插入bool Insert(K key){Node* cur _root;Node* parent nullptr;if (cur nullptr){_root new Node(key);}else{while (cur){if (cur-_key key){parent cur;cur cur-_right;}else if (cur-_key key){parent cur;cur cur-_left;}else{return false;}}if (key parent-_key)//插入的值大于父亲节点那么就需要在父亲节点的右边插入{parent-_right new Node(key);}else//插入的值小于父亲节点那么就需要在父亲节点的左边插入{parent-_left new Node(key);}}return true;} 代码大体情况如下 1.第一次插入数据的时候根节点指向空需要单独讨论。 2.根节点不为空那么就根据搜索树的特点找到最后插入的位置申请新节点连接新节点。 3.找不到插入的位置即插入的数据已经存在返回false。
四、搜索树的查找 //搜索树的查找Node* Find(const K key){assert(_root);Node* cur _root;while (cur){if (cur-_key key){cur cur-_left;}else if (cur-_key key){cur cur-_right;}else{return cur;}}return nullptr;}这段代码是根据搜索树的特点进行查找搜索的值大于根那么去右子树查找小于则去左子树查找倘若找到返回该节点指针找不到返回空指针。
五、搜索树的删除 搜索树的删除偏向复杂在我写出的代码中大致分为以下几点 1.删除的数据在叶子节点上。 2.删除的节点不在叶子节点上但是它的左右节点至少有一个是空。 3.删除的节点不在叶子节点上且左右子树都不为空。 4.删除的节点在根节点根节点至少有一个为空。
通过总结可以精简以上条件 1.删除的节点的左右节点至少有一个为空。 2.删除的节点的左右节点都不为空。
代码如下 //搜索二叉树的删除bool Erase(const K key){assert(_root);//先找到要删除的节点Node* cur _root;Node* parent nullptr;while (cur){if (cur-_key key){parent cur;cur cur-_left;}else if (cur-_key key){parent cur;cur cur-_right;}else{break;}}//找不到要删除的数据返回falseif (cur nullptr)return false;//找到了//处理“该节点的左孩子或者右孩子为空,或者左右孩子均为空”if (cur-_left nullptr || cur-_right nullptr){//该节点是根且且根节点至少一个子树为空if (parent nullptr)//parent为空证明输入的是根节点且根节点至少一个子树为空 {_root-_left nullptr ? _root _root-_right : _root _root-_left;delete cur;}//该节点是左孩子else if (cur parent-_left){//左节点为空if (cur-_left nullptr cur-_right ! nullptr){parent-_left cur-_right;}//右节点为空else if(cur-_left ! nullptr cur-_right nullptr){parent-_left cur-_left;}//左右节点均为空else{parent-_left nullptr;}//释放资源delete cur;}//该节点是右孩子else if (cur parent-_right){//左节点为空if (cur-_left nullptr cur-_right ! nullptr){parent-_right cur-_right;}//右节点为空else if (cur-_left ! nullptr cur-_right nullptr){parent-_right cur-_left;}//左右节点均为空else{parent-_right nullptr;}//释放资源delete cur;}}
//处理“该节点的左右孩子均不为空”else{//找到左节点的最大值Node* Fparent cur;Node* Fcur cur-_left;while (Fcur -_right){Fparent Fcur;Fcur Fcur-_right;}//交换节点的值cur-_key Fcur-_key;//Fcur的左边有数据if (Fcur-_left){Fparent-_right Fcur-_left;delete Fcur;}//Fcur的左边没有数据else{if(Fcur Fparent-_left){Fparent-_left nullptr;}else{Fparent-_right nullptr;}delete Fcur;}}return true;}首先是先要找到删除的数据若找不到返回false若找到那么进行下一步
找到后还有如下情况 1.删除的节点的左右节点至少有一个为空。 对应代码
//处理“该节点的左孩子或者右孩子为空,或者左右孩子均为空”if (cur-_left nullptr || cur-_right nullptr){//该节点是根且且根节点至少一个子树为空if (parent nullptr)//parent为空证明输入的是根节点且根节点至少一个子树为空 {_root-_left nullptr ? _root _root-_right : _root _root-_left;delete cur;}//该节点是左孩子else if (cur parent-_left){//左节点为空if (cur-_left nullptr cur-_right ! nullptr){parent-_left cur-_right;}//右节点为空else if(cur-_left ! nullptr cur-_right nullptr){parent-_left cur-_left;}//左右节点均为空else{parent-_left nullptr;}//释放资源delete cur;}//该节点是右孩子else if (cur parent-_right){//左节点为空if (cur-_left nullptr cur-_right ! nullptr){parent-_right cur-_right;}//右节点为空else if (cur-_left ! nullptr cur-_right nullptr){parent-_right cur-_left;}//左右节点均为空else{parent-_right nullptr;}//释放资源delete cur;}}原理由于删除的节点左右子树至少有一个为空那么就可以让父节点继承被删除节点的非空节点。继承后删除该节点。如果被删除的节点的左右子树都为空即被删除的节点是叶子节点那么就可以直接删除叶子节点然后将父节点指向空。 以上代码分别对删除的节点是左子树还是右子树的情况下删除的节点是否有左子树是否有右子树还是左右子树都没有进行讨论涵盖所有情况。值得注意的是当搜索树呈现链状的时候如果删除的是根节点此时的父节点是空不能进行访问那么需要在这里单独讨论。将根节点移动到有数据的那个子节点。 2.删除的节点的左右节点都不为空。 对应代码
//处理“该节点的左右孩子均不为空”else{//找到左节点的最大值Node* Fparent cur;Node* Fcur cur-_left;while (Fcur -_right){Fparent Fcur;Fcur Fcur-_right;}//交换节点的值cur-_key Fcur-_key;//Fcur的左边有数据if (Fcur-_left){Fparent-_right Fcur-_left;delete Fcur;}//Fcur的左边没有数据else{if(Fcur Fparent-_left){Fparent-_left nullptr;}else{Fparent-_right nullptr;}delete Fcur;}}第二种情况就不能直接进行交换。因为父节点没有多余的指针指向被删除节点的左右节点。那么在这里的思想是找到一个比被删除的节点的左孩子大右孩子小。符合条件的是左子树的最大值或者右子树的最小值。找到之后交换节点值。但是还是需要注意的是找到最大值以后分为两种情况 a.最大值的左边为空。 b.最大值的左边不为空。
那么进行讨论比如删除的数据是8。
a.最大值的左边为空 这个条件下可以直接交换删除
b.最大值的左边不为空 这种情况下就需要将父节点的右节点最大值的位置指向最大值的左节点。
在这段代码中 //找到左节点的最大值Node* Fparent cur;Node* Fcur cur-_left;while (Fcur -_right){Fparent Fcur;Fcur Fcur-_right;}Node* Fparent cur;的目的是避免这种情况下空指针解引用的问题删除的数据是3
倘若Fparent 为空 此时Fcur已经为叶子节点已经为3的左子树的最大值while循环不会进而以下代码会对Fparent解引用造成访问空指针的错误。如果将Fparent复制为cur那么从一开始Fparent就是Fcur的父节点既不违反逻辑也解决了问题。 因为此时1在父节点的左边所以综上所述再删除节点的同时也是需要判断被删除的节点是左节点还是右节点。
示例
int main()
{BSTreeint tree;int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto f : a){tree.Insert(f);}for (auto f : a){tree.Erase(f);tree.InTraversal();cout endl;}return 0;
}结果中序遍历
