目录
二叉搜索树的删除(较复杂)
Gitee代码:二叉搜索树
二叉搜索树的删除(较复杂)
bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { // 删除 if (cur->_left == nullptr) { if (cur == parent->_left) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } delete cur; } else if (cur->_right == nullptr) { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } delete cur; } else { // 找到右树最小节点去替代删除 Node* minRightParent = cur; Node* minRight = cur->_right; while (minRight->_left) { minRightParent = minRight; minRight = minRight->_left; } cur->_key = minRight->_key; if (minRight == minRightParent->_left) minRightParent->_left = minRight->_right; else minRightParent->_right = minRight->_right; delete minRight; } return true; } } return false; }
(较难)对于2个孩子的节点删除,用替代法删除法
上面代码的删除,如果全删除的话,会发现程序崩溃了——出现空指针
改进===>
Gitee代码:二叉搜索树===>>>会发现不会崩溃
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)