我目前正在开发一个程序来处理 C++ 中的 BST.我的所有函数都在工作，除了 removeNode，它删除树中给定键值的节点.我认为前两种情况可行，但第三种情况给我带来了麻烦.我知道如何删除有两个孩子的节点的逻辑，但目前代码对我不起作用.这是节点
I'm currently working on a program to handle a BST in c++. I have all of my functions currently working, except removeNode, which deletes a node of given key value in the tree. I think the first two cases work, but the 3rd is giving me trouble. I know the logic of how to delete a node with two children, but the code is not working for me at the moment. Here is node
struct node{
int key;
node* left;
node* right;
};
这里是删除函数的代码，以一个节点在底部有多个子节点的情况
And here is the code for the delete function, with the case of a node with more than one child on the bottom
node* Tree::removeKey(node*& t, int k)
{
if(t == nullptr){
return root;
}
else if(k < t->key){
root->left = removeKey(t->left, k);
}
else if (k > t->key){
root->right = removeKey(t->right, k);
}
else {
node* parent = getParent(root, k);
// Case 1: No child
if(t->left == nullptr && t->right == nullptr) {
if(parent->left->key == t->key){
parent->left = nullptr;
return t;
}
if(parent->right->key == t->key){
parent->right = nullptr;
return t;
}
}
//Case 2: One child
else if(t->left != nullptr && t->right == nullptr) {
parent->left = t->left;
parent->right = nullptr;
return t;
}
else if(t->right != nullptr && t->left == nullptr) {
parent->right = t->right;
parent->left = nullptr;
return t;
}
// case 3: 2 children
else {
// node *temp = nullptr;
// temp->key = findMin(root->right);
// t->key = temp->key;
// t->right = removeKey(t->right,temp->key);
// return t;
}
}
还有，辅助函数getParent，
And also, helper function getParent,
node* Tree::getParent(node* t, int k)
{
if(t == nullptr){
return nullptr;
}else
if((t->left != nullptr && k == t->left->key ) ||
(t->right != nullptr && k == t->right->key)){
return t;
}else
if(k < t->key){
return getParent(t->left, k);
}
if(k > t->key){
return getParent(t->right, k);
}
return nullptr;
}
今天我已经重写了这篇文章很多次了.我需要它在不破坏树的完整性的情况下删除(显然)，它现在正在这样做.
I've rewritten this piece so many times today. I need it to delete (obviously) without destroying the integrity of the tree, which it's doing right now.
起初，我自己阅读了维基百科文章 我在评论中推荐的二叉搜索树中的删除.
At first, I read myself the Wikipedia article Deletion in Binary Search Trees which I recommended in the my comment.
提问者提到
我知道如何删除有两个孩子的节点的逻辑，但目前代码对我不起作用.
I know the logic of how to delete a node with two children, but the code is not working for me at the moment.
这样看来，提问者相信理解算法，但不知道如何正确实现最后一部分.因此，我尝试提供帮助:
So it seems, the questioner believes to understand the algorithm but does not know how to implement the last part correctly. Thus, I try to help:
node *tOld = t; // remember current top node (which shall be removed)
// find left-most child in right sub-tree
t = t->right;
if (!t->left) {
// special case: old right child becomes new top node
} else {
// traverse right sub-tree left down
node *parent = t; // old parent of new top node
for (; t->left; parent = t, t = t->left);
// swap nodes
parent->left = t->right; // old parent of left most child gets right child (or nullptr)
t->right = tOld->right; // new top node gets old right sub-tree
}
t->left = tOld->left; // new top node gets old left sub-tree
// return remove node
return tOld;
仔细观察整个函数，我发现其余部分似乎有问题:
Looking closer at the whole function, I realized that the rest seems to be buggy:
有一个 root 没有在 OP 示例中公开?缺少全局变量?忘记重命名?
There is referred a root which is not exposed in sample of OP? Missing global variable? Forgot to rename?
我对如何移除当前节点感到困惑.一方面，指向当前节点的指针作为参考提供(我个人也会这样做).另一方面，对于当前节点的替换，在父节点中标识当前节点(使用无效的getParent() 辅助函数).这不是必需的，因为节点指针可以直接更改(并且会影响原始指针).这就是为什么它是一个引用(node* &t).
I was confused a bit by the fact how the removal of current node is done. On one hand, the pointer to current node is provided as reference (which I personally would do as well). On the other hand, for the replacement of current node, the current node is identified in parent (using the ineffective getParent() helper function). This is not necessary as the node pointer can be changed directly (and will affect the original pointer). That's why it is a reference (node* &t).
风格问题:if(t == nullptr)可以写成if(t)if (t != nullptr) 可以写成 if (!t).
A question of style:
if (t == nullptr) can be written as if (t)
if (t != nullptr) can be written as if (!t).
所以，我完整地回顾了这个功能:
So, I reviewed the function completely:
node* Tree::removeKey(node *&t, int k)
{
// This happens if key is not found.
if (!t) return t;
// This is traversal by recursion to find the node to remove.
if (k < t->key) return removeKey(t->left, k);
if (k > t->key) return removeKey(t->right, k);
// This is the case where node with k has been found:
node *tOld = t; // remember current top node for return
// Case 1: No child
if (!t->left && !t->right) {
/* Override t
* if t is root -> tree becomes empty
* if t is left of parent node -> parent->left becomes empty
* if t is right of parent node -> parent->right becomes empty
*/
t = nullptr;
return tOld;
}
// Case 2: One child
if (t->left && !t->right) {
t = t->left;
return tOld;
}
if (t->right && !t->left) {
t = t->right;
return tOld;
}
// Case 3: 2 children
// find left-most child in right sub-tree
t = t->right;
if (!t->left) {
// special case: old right child becomes new top node
} else {
// traverse right sub-tree left down
node *parent = t; // old parent of new top node
for (; t->left; parent = t, t = t->left);
// swap nodes
parent->left = t->right; // old parent of left most child gets right child (or nullptr)
t->right = tOld->right; // new top node gets old right sub-tree
}
t->left = tOld->left; // new top node gets old left sub-tree
return tOld;
}
removeKey() 返回已删除的节点(或 nullptr 如果未找到键).这很重要，因为可能需要进行一些后处理才能释放节点.如果删除的节点是用 new 创建的，它必须是 deleted.(否则，任何删除的节点都会产生内存泄漏.)
The removeKey() returns the removed node (or nullptr if key was not found). That's important as there is probably some post-processing necessary to release the node. If the removed node was created with new it must be deleted. (Otherwise, memory-leaks are produced for any removed node.)
返回的node *tOld的left和right指针不会被重置.这可能是也可能不是问题(取决于返回的指针是如何后处理的).偏执的开发者 [wc] 将取代任何返回旧;
通过return tOld->left = tOld->right = nullptr, tOld;
The left and right pointer of the returned node *tOld are not reset. This may or may not be an issue (depending how returned pointer is post-processed). Paranoid developers [wc]ould replace any
return tOld;
by
return tOld->left = tOld->right = nullptr, tOld;
样本包含
if (!t->left) {
// special case: old right child becomes new top node
} else {显然可以写成更短的
if (t->left) {这是在移动代码片段的同时发展起来的.我决定保留当前状态，因为对于入门级的人来说，整个代码可能不太容易理解.
This evolved while shifting code pieces around. I decided to leave this in current state as the whole code is probably not easy to understand for somebody with entry level.
<小时>
OP 没有公开 MCVE.因此，我拿了一个我的旧样本并添加了以前不存在的 BSTreeT::remove() :
BSTreeT.h –二叉搜索树的模板类:
BSTreeT.h – a template class for a binary search tree:
#ifndef B_S_TREE_T_H
#define B_S_TREE_T_H
/* provides a less functor which simply wraps operator < for a certain
* type
*
* VALUE ... C++ type of value to less-compare
*/
template <typename VALUE>
struct lessFunc {
bool operator()(const VALUE &value1, const VALUE &value2) const
{
return value1 < value2;
}
};
/* provides a class template for a binary search tree.
*
* KEY ... C++ type of the key values of nodes
* VALUE ... C++ type of the other values of nodes
* COMP ... C++ type of
*/
template <typename KEY, typename VALUE, typename COMP = lessFunc<KEY> >
class BSTreeT {
public:
// node type
class Node {
/* This friend shall ensure that the corresponding
* BSTreeT template class may access private _pLeft and _pRight.
*/
friend class BSTreeT<KEY, VALUE, COMP>;
public:
// the key value of node (used to define an order)
const KEY key;
// other values of nodes
VALUE value;
private:
// pointers to left and right child nodes
Node *_pLeft, *_pRight;
private: // Construction/destruction is for exclusive use of BSTreeT.
// constructor.
Node(const KEY &key, const VALUE &value):
key(key), value(value), _pLeft(nullptr), _pRight(nullptr)
{ }
// destructor.
~Node() { delete _pLeft; delete _pRight; }
// disabled:
Node(const Node&) = delete;
Node& operator=(const Node&) = delete;
public:
// returns pointer to left child node (or nullptr if there is none).
const Node* getLeft() const { return _pLeft; }
// returns pointer to right child node (or nullptr if there is none).
const Node* getRight() const { return _pRight; }
};
public:
// less functor used to compare node keys
const COMP ∁
private:
// root pointer
Node *_pRoot;
public:
/* constructor.
*
* comp ... a less comparator to define order of nodes
*/
explicit BSTreeT(const COMP &comp = COMP()):
comp(comp), _pRoot(nullptr)
{ }
// destructor.
~BSTreeT() { delete _pRoot; }
// disabled:
BSTreeT(const BSTreeT&) = delete;
BSTreeT& operator=(const BSTreeT&) = delete;
public:
/* inserts a node.
*
* key ... the key value of node
* value ... the other value of node
* return: true ... key/value inserted
* false ... Error! Possible reasons:
* - duplicated key
* - allocation of node failed.
*/
bool insert(const KEY &key, const VALUE &value)
{
return insert(_pRoot, key, value);
}
/** removes a node.
*
* key ... the key value of node to remove
* return: true ... key/value inserted
* false ... Error! Possible reasons:
* - key not found
*/
bool remove(const KEY &key)
{
return remove(_pRoot, key);
}
/* provides a functor-like type which is applied to every node
* in traverse().
*
* If an instance of this class is provided the traverse() does nothing
* else than the pure traversal.
*/
struct Apply {
// pre-order access to node
virtual void preNode(Node &node) { }
// in-order access to node
virtual void inNode(Node &node) { }
// post-order access to node
virtual void postNode(Node &node) { }
};
/* traverses the tree and applies the provided object to every node.
*
* apply ... the action object applied to every node
*/
void traverse(Apply &apply)
{
if (_pRoot) traverse(_pRoot, apply);
}
/* provides a functor-like type which is applied to every const node
* in traverse().
*
* If an instance of this class is provided the traverse() does nothing
* else than the pure traversal.
*/
struct ConstApply {
// pre-order access to node
virtual void preNode(const Node &node) { }
// in-order access to node
virtual void inNode(const Node &node) { }
// post-order access to node
virtual void postNode(const Node &node) { }
};
/* traverses the tree and applies the provided object to every node.
*
* apply ... the action object applied to every node
*/
void traverse(ConstApply &apply) const
{
if (_pRoot) traverse(_pRoot, apply);
}
private:
// inserts a node.
bool insert(Node *&pTree, const KEY &key, const VALUE &value)
{ /* Every if-branch ends with return.
* Thus, no explict else is needed.
*/
if (!pTree) { /* (!pTree) ... (pTree == nullptr) */
return !!(pTree = new Node(key, value));
}
if (comp(key, pTree->key)) return insert(pTree->_pLeft, key, value);
if (comp(pTree->key, key)) return insert(pTree->_pRight, key, value);
return false;
}
// removes a node.
bool remove(Node *&pNode, const KEY &key)
{
// This happens if key is not found.
if (!pNode) return false;
// This is traversal by recursion to find the node to remove.
if (key < pNode->key) return remove(pNode->_pLeft, key);
if (key > pNode->key) return remove(pNode->_pRight, key);
// This is the case where node with key has been found:
Node *pNodeOld = pNode; // remember current node for delete
// Case 1: No child
if (!pNode->_pLeft && !pNode->_pRight) pNode = nullptr;
/* Override pNode
* if pNode is _pRoot -> tree becomes empty
* if pNode is _pLeft of parent node -> parent->_pLeft becomes empty
* if pNode is _pRight of parent node -> parent->_pRight becomes empty
*/
// Case 2: One child
else if (pNode->_pLeft && !pNode->_pRight) pNode = pNode->_pLeft;
else if (pNode->_pRight && !pNode->_pLeft) pNode = pNode->_pRight;
// Case 3: 2 children
else {
// find left-most child in right sub-tree
pNode = pNode->_pRight;
if (pNode->_pLeft) {
// traverse right sub-tree left down
Node *pParent = pNode; // old parent of new top node
for (; pNode->_pLeft; pParent = pNode, pNode = pNode->_pLeft);
// swap nodes
pParent->_pLeft = pNode->_pRight; // old parent of left most child gets right child (or nullptr)
pNode->_pRight = pNodeOld->_pRight; // new top node gets old right sub-tree
} // else: special case: old right child becomes new top node
// new top node gets old left sub-tree
pNode->_pLeft = pNodeOld->_pLeft;
}
// delete old node
pNodeOld->_pLeft = pNodeOld->_pRight = nullptr;
delete pNodeOld;
// done with success
return true;
}
// tries to find a node by key.
Node* find(Node *pTree, const KEY &key) const
{
if (comp(key, pTree->key)) {
return pTree->_pLeft ? find(pTree->_pLeft, key) : nullptr;
}
if (comp(pTree->key, key)) {
return pTree->_pRight ? find(pTree->_pRight, key) : nullptr;
}
return pTree;
}
// traverses the tree.
void traverse(Node *pTree, Apply &apply)
{
apply.preNode(*pTree);
if (pTree->_pLeft) traverse(pTree->_pLeft, apply);
apply.inNode(*pTree);
if (pTree->_pRight) traverse(pTree->_pRight, apply);
apply.postNode(*pTree);
}
// traverses the tree.
void traverse(const Node *pTree, ConstApply &apply) const
{
apply.preNode(*pTree);
if (pTree->_pLeft) traverse(pTree->_pLeft, apply);
apply.inNode(*pTree);
if (pTree->_pRight) traverse(pTree->_pRight, apply);
apply.postNode(*pTree);
}
};
#endif // B_S_TREE_T_H
BSTreePrint.h –使用某种 ASCII 艺术打印二叉搜索树的模板函数:
BSTreePrint.h – template functions to print a binary search tree with some kind of ASCII art:
#ifndef B_S_TREE_PRINT_H
#define B_S_TREE_PRINT_H
#include <cassert>
#include <iostream>
#include <string>
#include "BSTreeT.h"
namespace {
/* a derived tree-traversal action
* for graphical (i.e. ASCII-art) pre-order output of tree
*/
template <typename K, typename V, typename C>
struct PrintPreT: public BSTreeT<K, V, C>::ConstApply {
typedef BSTreeT<K, V, C> Tree;
std::ostream &out;
std::string indent;
explicit PrintPreT(std::ostream &out): out(out), indent(" ") { }
~PrintPreT() = default;
PrintPreT(const PrintPreT&) = delete;
PrintPreT operator=(const PrintPreT&) = delete;
virtual void preNode(typename Tree::Node const &node)
{
indent.pop_back(); char c = indent.back(); indent.pop_back();
out << indent << "+-"
<< (node.getLeft() || node.getRight() ? '+' : '-')
<< '-' << node << '
';
indent += c; indent += ' ';
indent += node.getRight() ? "| " : " ";
}
virtual void inNode(typename Tree::Node const &node)
{
indent.pop_back(); indent.pop_back();
indent += " ";
}
virtual void postNode(typename Tree::Node const &node)
{
indent.pop_back(); indent.pop_back();
}
};
/* a derived tree-traversal action
* for graphical (i.e. ASCII-art) in-order output of tree
*/
template <typename K, typename V, typename C>
struct PrintInT: public BSTreeT<K, V, C>::ConstApply {
typedef BSTreeT<K, V, C> Tree;
std::ostream &out;
std::string indent;
explicit PrintInT(std::ostream &out): out(out), indent(" ") { }
~PrintInT() = default;
PrintInT(const PrintInT&) = delete;
PrintInT operator=(const PrintInT&) = delete;
virtual void preNode(typename Tree::Node const&)
{
indent += " ";
}
virtual void inNode(typename Tree::Node const &node)
{
popIndent();
const char l = popIndent() == ' ' ? '|' : ' ';
const bool root = indent.empty();
out << indent
<< (root ? "--" : "+-")
<< (node.getLeft() || node.getRight() ? "+-" : "--")
<< node << '
';
indent += root ? ' ' : l; indent += ' ';
indent += "| ";
}
virtual void postNode(typename Tree::Node const&)
{
popIndent();
}
char popIndent()
{
indent.pop_back(); const char c = indent.back(); indent.pop_back();
return c;
}
};
} // namespace
template <typename K, typename V, typename C>
std::ostream& printPre(
std::ostream &out, const BSTreeT<K, V, C> &tree)
{
PrintPreT<K, V, C> printer(out);
tree.traverse(printer);
return out;
}
template <typename K, typename V, typename C>
std::ostream& printIn(
std::ostream &out, const BSTreeT<K, V, C> &tree)
{
PrintInT<K, V, C> printer(out);
tree.traverse(printer);
return out;
}
enum BSTreePrintStyle {
PrintBSTreePreOrder,
PrintBSTreeInOrder
};
template <typename K, typename V, typename C>
std::ostream& print(
std::ostream &out, const BSTreeT<K, V, C> &tree,
BSTreePrintStyle style = PrintBSTreePreOrder)
{
switch (style) {
case PrintBSTreePreOrder: return printPre(out, tree);
case PrintBSTreeInOrder: return printIn(out, tree);
default: assert(false);
}
return out;
}
#endif // B_S_TREE_PRINT_H
testRemove.cc –用于构建示例树并删除各种节点以测试各个案例的测试程序:
testRemove.cc – a test program to build a sample tree and remove various nodes to test the individual cases:
#include <iostream>
#include "BSTreeT.h"
#include "BSTreePrint.h"
using namespace std;
// template instances (for convenience)
struct Empty { };
typedef BSTreeT<char, Empty>::Node BSTreeNode;
typedef BSTreeT<char, Empty> BSTree;
ostream& operator<<(ostream &out, const BSTreeNode &node)
{
return out << node.key;
}
ostream& operator<<(ostream &out, const BSTree &tree)
{
return printIn(out, tree);
}
// recursive method to build balanced tree
void buildTree(BSTree &tree, char begin, char end)
{
char middle = (begin + end) / 2;
tree.insert(middle, Empty());
if (begin < middle) buildTree(tree, begin, middle);
if (middle < end) buildTree(tree, middle + 1, end);
}
// helper function
void remove(BSTree &tree, char key)
{
cout << "Remove node '" << key << "': "
<< (tree.remove(key) ? "done" : "failed") << '
'
<< tree << endl;
}
int main()
{
BSTree tree;
buildTree(tree, 'A', 'Z');
cout << "Initial tree:
" << tree << endl;
// Test Cases
// test key not found
remove(tree, '?');
// test case 1
remove(tree, 'K');
// test case 2
remove(tree, 'I');
remove(tree, 'H'); // intermediate step (case 1)
remove(tree, 'J');
// test cases 3
remove(tree, 'G');
remove(tree, 'T');
// done
return 0;
}
在 Windows 10 上的 cygwin 中编译和测试:
Compiled and tested in cygwin on Windows 10:
$ g++ --version
g++ (GCC) 6.4.0
$ g++ -std=c++11 -o testRemove testRemove.cc
$ ./testRemove
Initial tree:
+---A
+-+-B
| +---C
+-+-D
| | +---E
| +-+-F
+-+-G
| | +---H
| | +-+-I
| +-+-J
| | +---K
| +-+-L
--+-M
| +---N
| +-+-O
| | +---P
| +-+-Q
| | | +---R
| | +-+-S
+-+-T
| +---U
| +-+-V
+-+-W
| +---X
+-+-Y
+---Z
Remove node '?': failed
+---A
+-+-B
| +---C
+-+-D
| | +---E
| +-+-F
+-+-G
| | +---H
| | +-+-I
| +-+-J
| | +---K
| +-+-L
--+-M
| +---N
| +-+-O
| | +---P
| +-+-Q
| | | +---R
| | +-+-S
+-+-T
| +---U
| +-+-V
+-+-W
| +---X
+-+-Y
+---Z
Remove node 'K': done
+---A
+-+-B
| +---C
+-+-D
| | +---E
| +-+-F
+-+-G
| | +---H
| | +-+-I
| +-+-J
| +---L
--+-M
| +---N
| +-+-O
| | +---P
| +-+-Q
| | | +---R
| | +-+-S
+-+-T
| +---U
| +-+-V
+-+-W
| +---X
+-+-Y
+---Z
Remove node 'I': done
+---A
+-+-B
| +---C
+-+-D
| | +---E
| +-+-F
+-+-G
| | +---H
| +-+-J
| +---L
--+-M
| +---N
| +-+-O
| | +---P
| +-+-Q
| | | +---R
| | +-+-S
+-+-T
| +---U
| +-+-V
+-+-W
| +---X
+-+-Y
+---Z
Remove node 'H': done
+---A
+-+-B
| +---C
+-+-D
| | +---E
| +-+-F
+-+-G
| +-+-J
| +---L
--+-M
| +---N
| +-+-O
| | +---P
| +-+-Q
| | | +---R
| | +-+-S
+-+-T
| +---U
| +-+-V
+-+-W
| +---X
+-+-Y
+---Z
Remove node 'J': done
+---A
+-+-B
| +---C
+-+-D
| | +---E
| +-+-F
+-+-G
| +---L
--+-M
| +---N
| +-+-O
| | +---P
| +-+-Q
| | | +---R
| | +-+-S
+-+-T
| +---U
| +-+-V
+-+-W
| +---X
+-+-Y
+---Z
Remove node 'G': done
+---A
+-+-B
| +---C
+-+-D
| | +---E
| +-+-F
+-+-L
--+-M
| +---N
| +-+-O
| | +---P
| +-+-Q
| | | +---R
| | +-+-S
+-+-T
| +---U
| +-+-V
+-+-W
| +---X
+-+-Y
+---Z
Remove node 'T': done
+---A
+-+-B
| +---C
+-+-D
| | +---E
| +-+-F
+-+-L
--+-M
| +---N
| +-+-O
| | +---P
| +-+-Q
| | | +---R
| | +-+-S
+-+-U
| +---V
+-+-W
| +---X
+-+-Y
+---Z
$
注意:
左孩子打印在父母上方，右孩子打印在下方.我在准备测试代码时意识到了这一点.(因此，在这种情况下，将头转向左侧以获得自上而下的树木视图不起作用，因为在这种情况下树木看起来像是镜像".)请在检查结果时记住这一点.
Left children are printed above parents, right children below. I realized this while preparing the test code. (Hence, turning the head to the left to get a top-down view of trees does not work as the trees appear "mirrored" in this case.) Please, keep this in mind while checking the results.
这篇关于c ++从二叉搜索树中删除具有两个孩子的特定节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！