发卡网站建设7az,中国网站建设中心,徐州自助建站模板,网店代运营合同模板目录 1.什么是二叉搜索树
2.二叉搜索树的查找
3.二叉搜索树插入
4.二叉搜索树的删除
1.删除的节点只有左子树或者右子树
2.删除节点左右子树都有的情况
5.代码 1.什么是二叉搜索树
左节点的值小于根节点
右节点大于根节点
左右子树也满足上面两个条件
例#xff1a;…目录 1.什么是二叉搜索树
2.二叉搜索树的查找
3.二叉搜索树插入
4.二叉搜索树的删除
1.删除的节点只有左子树或者右子树
2.删除节点左右子树都有的情况
5.代码 1.什么是二叉搜索树
左节点的值小于根节点
右节点大于根节点
左右子树也满足上面两个条件
例arr[] {5,2,1,3,4,7,6,8} 转化为二叉搜索树 2.二叉搜索树的查找
思路寻找44比5小去左子树寻找- 4比2大去右子树寻找-4比3大去右子树寻找-找到4。
3.二叉搜索树插入
思路查找插入元素可以存储的位置 插入。
例插入9, 9比5大去右子树寻找-9比7大去右子树寻找-9比8大去右子树寻找-找到9可以插入的位置-将9插入8的右子树。
4.二叉搜索树的删除
二叉搜索树删除的情况可以分成两种
1.删除的节点只有左子树或者右子树 如果删除节点是删除节点父亲节点的左子树那就把删除节点的左子树或者右子树托付给父亲节点的左子树。 如果删除节点是删除节点父亲节点的右子树那就把删除节点的左子树或者右子树托付给父亲节点的右子树。
例删除3就把4托付给2的右子树 删除4就把空节点托付给3的右子树
2.删除节点左右子树都有的情况
找左子树的最右节点或者右子树的最左节点替换删除节点再将左子树最右节点或者右子树最左节点删除因为最右节点一定没有右子树最左节点一定没有左子树就把问题转化为情况1了。
例删除2
用右子树的最左节点3为右子树最左节点把3赋值给2去右子树把3删除把4托付给3的右子树 。
用左子树的最右节点1为左子树最右节点把1赋值给2去左子树把1删除把空节点托付给1的左子树。
5.代码
#pragma oncenamespace V
{templateclass Kstruct BinarySearchTreeNode//节点{typedef struct BinarySearchTreeNodeK Node;BinarySearchTreeNode():_val(){}BinarySearchTreeNode(const K val):_val(val){}Node* _left nullptr;Node* _right nullptr;K _val;};template class Kclass BST//二叉搜索树{typedef struct BinarySearchTreeNodeK Node;public:BST()//构造函数:_root(nullptr){}BST(const BSTK t){_root Copy(t._root);}Node* Copy(Node* root){if (nullptr root){return nullptr;}Node* newNode new Node(root-_val);newNode-_left Copy(root-_left);newNode-_right Copy(root-_right);return newNode;}BSTK operator(BSTK t){std::swap(_root,t._root);return *this;}bool Insert(const K key){if (nullptr _root){_root new Node(key);return true;}Node* cur _root;Node* parent nullptr;while (nullptr ! cur){if (key cur-_val){parent cur;cur cur-_right;}else if (key cur-_val){parent cur;cur cur-_left;}else { return false; }}Node* newNode new Node(key);if (parent-_val newNode-_val){parent-_left newNode;return true;}else{parent-_right newNode;return true;}}Node* Find(const K key){Node* cur _root;while (nullptr ! cur){if (cur-_val key){cur cur-_left;}else if (cur-_val key){cur cur-_right;}else if (cur-_val key){return cur;}}return nullptr;}bool Erase(const K key){Node* cur _root;Node* parent _root;while (nullptr ! cur){if (cur-_val key){parent cur;cur cur-_left;}else if (cur-_val key){parent cur;cur cur-_right;}else if (cur-_val key)//找到key{if (nullptr cur-_left)//当key左子树为空{if (_root cur){_root cur-_right;}else if (cur parent-_left)//当cur是父亲的左子树{parent-_left cur-_right;}else if(cur parent-_right)//cur是父亲的右子树{parent-_right cur-_right;}delete cur;cur nullptr;return true;}else if (nullptr cur-_right)//key的右子树为空{if(cur _root){ _root cur-_left;}else if (cur parent-_left){parent-_left cur-_left;}else{parent-_right cur-_left;}delete cur;cur nullptr;return true;}else //左右子树都不为空 {Node* LNode cur-_left;Node* LParent cur;while (LNode-_right)//找左子树的最右节点 替换cur {LParent LNode;LNode LNode-_right;}cur-_val LNode-_val;//修改值//最右节点没有右子树if (LNode LParent-_left){LParent-_left LNode-_left;}else{LParent-_right LNode-_left;}delete LNode;LNode nullptr;return true;}}}return false;}void InOrder(){return _InOrder(_root);}void Destory(){_Destory(_root);}~BST(){Destory();}///递归实现bool FindR(const K val){return _FindR(_root,val);}bool InsertR(const K val){return _InsertR(_root,val);}bool EraseR(const K val){return _EraseR(_root, val);}private:Node* _root;void _InOrder(Node* root){if (nullptr root){return;}std::cout root-_val ;_InOrder(root-_left);_InOrder(root-_right);}void _Destory(Node * root){if (nullptr root){return;}_Destory(root-_left);_Destory(root-_right);delete root;}bool _InsertR(Node * root, const K val){if (nullptr root){root new Node(val);return true;}if (root-_val val)_InsertR(root-_left, val);else if (root-_val val)_InsertR(root-_right, val);return false;}bool _FindR(Node * root,const Kval){if (nullptr root)return false;if (root-_val val)_FindR(root-_left, val);else if (root-_val val)_FindR(root-_right, val);else return true;}bool _EraseR(Node * root,const Kval){if (root nullptr){return false;}if(root-_val val){_EraseR(root-_left,val);}else if (root-_val val){_EraseR(root-_right, val);}else{Node* del root;//当左孩子为空if (nullptr root-_left){root root-_right;}else if (nullptr root-_right){root root-_left;}else {Node* leftmax root-_left;while (leftmax-_right)//左子树的最右节点{leftmax leftmax-_right;}swap(leftmax-_val, root-_val);return _EraseR(root-_left,val);}delete del;return true;}}};}
