保定网站开发公司,怎么选择扬中网站建设,网络挣钱,资源网站推荐首先查找元素是否在二叉搜索树中#xff0c;如果不存在#xff0c;则返回
要删除的结点可能分下面四种情况#xff1a;
a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中…首先查找元素是否在二叉搜索树中如果不存在则返回
要删除的结点可能分下面四种情况
a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程如下
情况1删除该结点 且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除 情况2删除该结点 且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除 情况3找它的右子树的最小值或者左子树的最大值用它的值填补到被删除节点中再来处理该结点的删除问题--替换法删除 tip 我们可以把一个父节点看作父亲每一个父亲只能照顾两个儿子 情况1和情况2如果这个父亲只有一个孩子要照顾或者一个也没有那么他想要脱身只需要把这个孩子托付给他的长辈没有就是nullptr我们可以把这个过程叫托孤 情况3就比较复杂这个父亲有两个孩子托孤就行不通了所以他要找一个人来代替他他需要满足两个条件 首先要确保他是可以脱身的他要是有一个孩子就托孤这样他就可以过来照顾这两个孩子了 其次他要满足照顾这两个孩子的条件这个节点的key值要比左子树的每个节点key都要大比右子树的每个节点key都要小 右子树的最小值或者左子树的最大值就满足这些条件我们可以把这个过程叫找月嫂 bool Erase(const K data)
{node* parent nullptr;node* cur _root;while (cur cur-_data ! data)//找要删除的位置{parent cur;if (data cur-_data){cur cur-_left;}else{cur cur-_right;}}if (cur nullptr)return false;if (cur-_left nullptr)//托孤给父母{if (parent nullptr)//考虑特殊rootnullptr{_root cur-_right;}else{if (cur-_data parent-_data)parent-_left cur-_right;elseparent-_right cur-_right;}delete cur;}else if (cur-_right nullptr)//托孤给父母{if (parent nullptr)//考虑特殊rootnullptr{_root cur-_left;}else{if (cur-_data parent-_data)parent-_left cur-_left;elseparent-_right cur-_left;}delete cur;}else//找月嫂替代合适 有且只有一个娃或者没有{node* maxleft cur-_left;node* maxparent cur;while (maxleft-_right){maxparent maxleft;maxleft maxleft-_right;}cur-_data maxleft-_data;// maxparent-_right maxleft-_left;错误//月嫂托孤if (maxparent-_left maxleft)//maxparentcur{maxparent-_left maxleft-_left;}else{maxparent-_right maxleft-_left;}delete maxleft;}return true;
} 注意特殊情况 1.在情况一和情况二下可能删除_root节点在函数里面就需要特殊考虑 2.情况三月嫂的托孤月嫂不一定是父亲的右孩子左子树最大值的前提下月嫂可能就是要被删除节点的左孩子所以也要妥善处理 递归版
bool _EraseR(node* root, const K data)
{if (root nullptr)return false;if (data root-_data)return _EraseR(root-_left, data);else if (data root-_data)return _EraseR(root-_right, data);else{node* del root;if (root-_left nullptr){root root-_right;delete del;}else if (root-_right nullptr){root root-_left;delete del;}else{node* maxleft root-_left;while (maxleft-_right)maxleft maxleft-_right;del maxleft;swap(root-_data, maxleft-_data);_EraseR(root-_left, data);//转为子问题}return true;}
} node* root 1.就不需要再找父节点了这样还少了判断被删除节点是父亲节点的左孩子还是右孩子 2.对于删除根节点的处理也可以不用特殊处理 _EraseR(root-_left, data);//转为子问题 月嫂托孤的过程转变为删除月嫂节点 搜索二叉树的删除时间复杂度O(N)
