为什么我的二进制搜索树无效删除功能无法正常工作？
Why is my Binary Search Tree void remove function not working properly?
我无法让我的二叉搜索树删除功能正常工作。无论我做什么，它实际上都不想正常工作。当我试图让它正常运行时，它似乎总是做一些最奇怪的事情。
node* 结构和 root_ 一样位于另一个头文件中（它们在正常的右、左和数据存储配置中设置）
void remove(int value){
node* n = root_;
node* nClone = nullptr;
while (n != nullptr) {//constant checker to ensure that a
if (value > n->value_) { // if value is larger than value stored within node n it will descend further down right
nClone = n; //stores n before continueing
n = n->rhs_;
} else if (value < n->value_) { // if value is less than value stored within node n it will descend further down left
nClone = n; //stores n before continueing
n = n->lhs_;
} else { //if it is equal to the value (there are no other possible outcomes so an else would work) check if there are any subsiquent leaves attached
if (n->lhs_ == nullptr && n->rhs_ == nullptr) { //if both left and right are empty (I.E. no leaves attached to node) set n to nullptr and then delete using free();
nClone->lhs_ = nullptr; //stores both left
nClone->rhs_ = nullptr; // and right leaves as nullptr
free(n); //frees n
n = nullptr;
count_--;//decreases count_/size counter by 1
return; //exits from function as there is nothing more to do
} else if (n->lhs_ == nullptr || n->rhs_ == nullptr) { //if n has one connection whether it be on the left or right it stores itself in nClone and then deletes n
if (n->lhs_ != nullptr) { //if statement to check if left leaf of n exists
nClone->lhs_ = n->lhs_; //if it does it stores n's left leaf in nClone
} else { //if it doesnt have anything stored in the left then there garuntteed is one on the right
nClone->rhs_ = n->rhs_; //stores n's right leaf in nClone
}
free(n);
count_--; //decreases count_/size counter by 1
return; //exits from function as there is nothing more to do
} else {
//for preorder succession
node* nSuc = n->rhs_; //stores right leaf of n in nSuc
while (nSuc->lhs_ != nullptr) { //look for successor
nSuc = nSuc->lhs_;
}
n->value_ = nSuc->value_;
free(n);
count_--;
return;
}
}
}
}
你的代码就像是用 C 写的一样。C++ 是一种不同的语言，你可以而且应该利用它来发挥你的优势。
下面的文字中穿插了一个complete, compileable example，你可以在线尝试:)当然这不是实现树的唯一方法，我不得不掩盖实现树所需的各种细节至少让它成为一个功能齐全的解决方案。 “现实生活”的实现可能要复杂得多，因为“教科书”方法通常不能很好地与现代 CPU 上的缓存层次结构混合，并且与最先进的实现相比，像这样的树会相当慢.但我认为，它确实有助于弥合普遍的“类 C”树思维方式与现代 C++ 带来的差距。
再说一次：这个例子是最小的，它没有做很多通常实践中需要的事情，但它至少指向远离 C 和 C++ 的方向，这就是我的意图。
首先，让我们有一个 Node 类型，它使用子节点的拥有指针。这些指针自动管理内存并从根本上防止您犯下会泄漏内存或允许使用悬空指针的错误。术语“拥有指针”意味着总是有一个明确定义的所有者：它就是指针本身。例如，这些指针不能被复制——从那时起您将拥有同一个对象的两个所有者，为此您需要共享所有权。但是共享所有权很难做到正确，因为必须有一些适当的协议来确保您不会获得循环引用。构建树时，“父”节点是“子”节点的自然所有者，因此 unique 所有权正是所需要的。
// complete example begins
#include <cassert>
#include <memory>
using Value = int;
struct Node {
std::unique_ptr<Node> lhs_;
std::unique_ptr<Node> rhs_;
Value value_;
explicit Node(int value) : value_(value) {}
};
// cont'd.
我们还应该有一个 Tree 拥有根节点，并保持节点计数：
// cont'd.
struct Tree {
std::unique_ptr<Node> root_;
int count_ = 0;
};
// cont'd.
在对此类数据结构进行操作时，您经常不仅要访问节点指针的 值，还要访问指针本身这样就可以修改了。因此，我们需要某种“节点引用”，它的行为主要类似于 Node*，但在内部，它还携带指向节点的 指针 的地址，因此那例如节点可以是 replaced:
// cont'd.
class NodeRef {
std::unique_ptr<Node> *owner;
public:
NodeRef() = delete;
NodeRef(std::unique_ptr<Node> &o) : owner(&o) {}
Node *get() const { return owner->get(); }
// Use -> or * to access the underlying node
Node *operator->() const { return get(); }
Node &operator*() const { return *get(); }
// In boolean contexts, it's true if the Node exists
explicit operator bool() const { return bool(*owner); }
// Replace the Node (if any) with some other one
void replace(std::unique_ptr<Node> &&oldNode) {
*owner = std::move(oldNode);
}
NodeRef &operator=(std::unique_ptr<Node> &val) {
owner = &val;
return *this;
}
};
// cont'd.
NodeRef持有指向节点所有者的指针（所有者是拥有指针类型std::unique_ptr）。
以下是您可以像 Node* 一样使用 NodeRef 的方法：
NodeRef node = ...;
node->value_ // access to pointed-to Node using ->
(*node).value // access to pointed-to Node using *
if (node) ... // null check
node = otherNode; // assignment from another node (whether owner or NodeRef)
以下是 NodeRef 与 std::unique_ptr<Node> & 类似的行为方式，即类似于对节点所有者的引用，允许您更改所有权：
Tree tree;
NodeRef root = tree.root_; // reference the root of the tree
root.replace(std::make_unique<Node>(2)); // replace the root with a new node
请注意，由于 std::unique_ptr 和移动语义的强大功能，此代码执行所有必要的内存分配和释放。任何地方都没有 no new、delete、malloc 或 free 语句。而且，性能与手动分配相当——此代码不使用任何类型的垃圾收集或引用计数。 std::unique_ptr 是一种工具，可让您利用编译器以保证正确的方式为您编写内存分配和释放代码。
但是，NodeRef 不是一个“观察”指针，即如果它指向的节点的 owner 突然消失，那么 NodeRef 变成悬空。否则会产生更多的开销，并且需要使用一些跟踪指针，例如shared_ptr 和 weak_ptr，或者定制的解决方案——当然超出了这里的范围。
因此 NodeRef 满足了典型的要求，使实际的树管理代码更容易编写、理解和维护，并减少了出错的可能性。这种方法有利于设计正确的代码，即导致未定义行为的错误大多被编译器捕获，或者无法编写。
让我们看看二进制节点搜索的外观，使用我们上面介绍的类型：
// cont'd
// Finds the owner of a node that contains a given value,
// or the insertion point where the value would be
NodeRef find(Tree &tree, const Value &value)
{
NodeRef node = tree.root_;
while (node) {
if (value < node->value_)
node = node->lhs_;
else if (node->value_ < value)
node = node->rhs_;
else
break; // we found the value we need
}
return node;
}
// cont'd
首先，请注意，虽然 returned 节点引用可以为空，但这并不意味着它“无用”。 NodeRef 永远不会“完全”为 null，并且必须始终引用某个节点所有者 - 这就是删除默认构造函数的原因，因此您不能错误地创建无效的 NodeRef。 node 可以为 null，而不是指向该节点的拥有指针的底层引用。
请注意该代码与使用 Node * 的版本有多么相似，但它更强大。由于这个版本的findreturn是一个NodeRef，我们可以使用这个引用来替换节点（或者如果它是null则第一次设置），而签名Node *find(Node *root, const Value &value) 只会让我们访问节点本身，而不是它的所有者。而且，如果找不到节点，它将 return 一个空指针 - 也不会让我们更接近于知道在哪里插入新节点， 和 丢弃工作找到这样的插入点 (!)。
NodeRef 为我们提供了对父节点的谨慎访问：它不公开整个父节点，而只公开拥有给定节点的拥有指针——它也比“父节点”更通用节点将是，因为拥有指针甚至不需要由 Node 类型持有。事实上，当节点的所有者在 Tree class 中时，NodeRef 工作得很好，或者它也可以引用一个独立的指针：
std::unique_ptr<Node> myNode;
NodeRef node = myNode;
// The two lines below are equivalent - both change the `myNode` owning pointer
node.replace(std::make_unique<Node>(42));
myNode = std::make_unique<Node>(42);
原则上，可以有一个 NodeRef &NodeRef::operator=(std::unique_ptr<Node> &&)，即一种移动分配节点本身的方法，但这会隐藏一个重要的事实，即 NodeRef 并不真正拥有该节点，但仅指一些所有者，replace 方法使这一点更加明确：我们正在替换所有者持有的节点。
现在我们可以实现您要的功能：节点移除。此函数接受一个NodeRef，并修改该节点根部的子树，以便删除原始节点：
// cont'd
// Removes the given node. Returns true if the node was removed, or false if
// there was nothing to remove
bool remove(NodeRef node)
{
for (;;) {
if (!node) return false; // the node is empty, nothing to do
if (!node->lhs_) {
// replace the node with its sole right child, if any
node.replace(std::move(node->rhs_));
return true;
}
else if (!node->rhs_) {
// replace the node with its sole left child, if any
node.replace(std::move(node->lhs_));
return true;
}
else {
// node has two children
// 1. take on the largest value in the left subtree
// oldValue is a *reference* to the value of the node being replaced
Value &oldValue = node->value_;
node = node->lhs_;
while (node->rhs_) node = node->rhs_;
// we found the node with a replacement value - substitute it for
// the old value
oldValue = std::move(node->value_);
// 2. remove that child - continue the removal loop
continue;
// instead of continue, we could also do
// remove(node);
// return;
// but by continuing we don't have recursion, and we levarage
// the fact that the `node` references the correct node to remove
}
}
}
// cont'd
我们 std::move 值 - 这在处理像整数这样的“简单”值类型时根本不重要，但是如果 Value 是一种类型只能移动不能复制，例如using Value = std::unique_ptr<SomeType>;.
现在管理 Tree 中节点删除的助手：
// cont'd
void remove(Tree &tree, const Value& value)
{
auto node = find(tree, value);
if (remove(node))
-- tree.count_;
}
// cont'd
我们本可以使用 int value 而不是 const Value &value，但这种方法更通用，可以与其他 Value 类型一起使用。
节点插入也相当容易，因为 find 已经提供了值所在的插入点，如果它存在的话：
// cont'd
bool insert(Tree &tree, const Value& value)
{
auto node = find(tree, value);
if (node) {
// Such a value already exists
assert(node->value_ == value);
return false;
} else {
// Insert new value
node.replace(std::make_unique<Node>(value));
++ tree.count_;
return true;
}
}
// cont'd
如果 Value 是不可复制的类型，那么我们需要一个采用右值引用的 insert 签名，即 bool insert(Tree &tree, Value &&value).
现在您可能会问：我们将如何“行走”这棵树？在 C++ 中，处理项集合的惯用方法是通过迭代器，然后可以使用所谓的 range-for。以下示例打印出向量的元素：
std::vector<int> values{1,2,3,4,5};
for (int val : values)
std::cout << val << "\n";
在迭代或“遍历”树时，我们需要在身后留下一些“面包屑”，以便我们可以找到回到树上的路。那些需要引用节点，以及节点是否被访问或遍历：
// cont'd
#include <functional>
#include <stack>
#include <vector>
// An entry in the node stack used to iterate ("walk") the tree
struct BreadCrumb {
NodeRef node;
bool visited = false; // was this node visited?
bool traversedLeft = false; // was the left child descended into?
bool traversedRight = false; // was the right child descended into?
BreadCrumb(std::unique_ptr<Node> &owner) : node(owner) {}
BreadCrumb(NodeRef node) : node(node) {}
Node *operator->() const { return node.get(); }
explicit operator bool() const { return bool(node); }
};
// cont'd
我们沿着树向下走的“路径”保存在一个专门用于此目的的堆栈中：
// cont'd
// A stack holds the path to the current node
class NodeStack {
// Top of stack is the current node
std::stack<BreadCrumb, std::vector<BreadCrumb>> m_stack;
public:
NodeStack() = default;
NodeStack(NodeRef n) { if (n) m_stack.push(n); }
bool empty() const { return m_stack.empty(); }
// The breadcrumb that represents the top of stack, and thus the current node
BreadCrumb &crumb() { return m_stack.top(); }
const BreadCrumb &crumb() const { return m_stack.top(); }
NodeRef node() { return crumb().node; }
Node *node() const { return empty() ? nullptr : crumb().node.get(); }
void push(NodeRef n) { m_stack.push(n); }
// Visit and mark the node if not visited yet
bool visit() {
if (crumb().visited) return false;
crumb().visited = true;
return true;
}
// Descend one level via the left edge if not traversed left yet
bool descendLeft() {
if (crumb().traversedLeft) return false;
crumb().traversedLeft = true;
auto &n = crumb()->lhs_;
if (n) m_stack.push(n);
return bool(n);
}
// Descends one level via right edge if not traversed right yet
bool descendRight() {
if (crumb().traversedRight) return false;
crumb().traversedRight = true;
auto &n = crumb()->rhs_;
if (n) m_stack.push(n);
return bool(n);
}
// Ascends one level
bool ascend() {
m_stack.pop();
return !empty();
}
};
// cont'd
树遍历操作被抽象到栈中，因此剩余的代码是更高层次的，没有这些细节。
现在我们可以实现一个节点迭代器，它使用堆栈来保持其面包屑轨迹：
// cont'd
// Node Forward Iterator - iterates the nodes in given order
class NodeIterator {
using Advancer = void (NodeIterator::*)();
NodeStack m_stack; // Breadcrumb path to the current node
Advancer m_advancer; // Method that advances to next node in chosen order
Order m_order = Order::In;
public:
NodeIterator() = default;
// Dereferencing operators
Node& operator*() { return *m_stack.node(); }
Node* operator->() { return m_stack.node().get(); }
// Do the iterators both point to the same node (or no node)?
bool operator==(const NodeIterator &other) const {
return m_stack.node() == other.m_stack.node();
}
bool operator==(decltype(nullptr)) const { return !bool(m_stack.node()); }
bool operator!=(const NodeIterator &other) const { return m_stack.node(); }
bool operator!=(decltype(nullptr)) const { return bool(m_stack.node()); }
NodeIterator(NodeRef n, Order order = Order::In) : m_stack(n) {
setOrder(order);
if (n) operator++(); // Start the traversal
}
void setOrder(Order order) {
if (order == Order::In)
m_advancer = &NodeIterator::advanceInorder;
else if (order == Order::Pre)
m_advancer = &NodeIterator::advancePreorder;
else if (order == Order::Post)
m_advancer = &NodeIterator::advancePostorder;
m_order = order;
}
NodeIterator &operator++() { // Preincrement operator
assert(!m_stack.empty());
std::invoke(m_advancer, this);
return *this;
}
// No postincrement operator since it'd need to copy the stack and thus
// be way too expensive to casually expose via postincrement.
void advanceInorder();
void advancePreorder();
void advancePostorder();
bool goLeft() { return m_stack.descendLeft(); }
bool goRight() { return m_stack.descendRight(); }
};
// cont'd
还记得堆栈吗？它让我们相当简洁地描述了 in-、pre- 和 post-order 遍历：
// cont'd
void NodeIterator::advanceInorder() {
for (;;) {
if (m_stack.descendLeft())
continue;
if (m_stack.visit())
break;
if (m_stack.descendRight())
continue;
if (m_stack.ascend())
continue;
assert(m_stack.empty());
break;
}
}
void NodeIterator::advancePreorder() {
for (;;) {
if (m_stack.visit())
break;
if (m_stack.descendLeft())
continue;
if (m_stack.descendRight())
continue;
if (m_stack.ascend())
continue;
assert(m_stack.empty());
break;
}
}
void NodeIterator::advancePostorder() {
for (;;) {
if (m_stack.descendLeft())
continue;
if (m_stack.descendRight())
continue;
if (m_stack.visit())
break;
if (m_stack.ascend())
continue;
assert(m_stack.empty());
break;
}
}
// cont'd
现在，当我们希望迭代以某个节点为根的树时，我们需要一些简单的方法来使用此迭代器：
// cont'd
class TreeRangeAdapter {
NodeRef m_root;
Order m_order;
public:
TreeRangeAdapter(NodeRef root, Order order) :
m_root(root), m_order(order) {}
NodeIterator begin() const { return {m_root, m_order}; }
constexpr auto end() const { return nullptr; }
};
auto inOrder(NodeRef node) { return TreeRangeAdapter(node, Order::In); }
auto preOrder(NodeRef node) { return TreeRangeAdapter(node, Order::Pre); }
auto postOrder(NodeRef node) { return TreeRangeAdapter(node, Order::Post); }
// cont'd
这一切如何运作？这只是一个简单的填充树的例子，中序遍历：
// cont'd
#include <iostream>
#include <cstdlib>
int main() {
Tree tree;
for (int i = 0; i < 10; ++i) insert(tree, rand() / (RAND_MAX/100));
for (auto &node : inOrder(tree.root_)) {
std::cout << node.value_ << " ";
}
std::cout << "\n";
}
// complete example ends
输出：
19 27 33 39 55 76 78 79 84 91
我无法让我的二叉搜索树删除功能正常工作。无论我做什么，它实际上都不想正常工作。当我试图让它正常运行时，它似乎总是做一些最奇怪的事情。
node* 结构和 root_ 一样位于另一个头文件中（它们在正常的右、左和数据存储配置中设置）
void remove(int value){
node* n = root_;
node* nClone = nullptr;
while (n != nullptr) {//constant checker to ensure that a
if (value > n->value_) { // if value is larger than value stored within node n it will descend further down right
nClone = n; //stores n before continueing
n = n->rhs_;
} else if (value < n->value_) { // if value is less than value stored within node n it will descend further down left
nClone = n; //stores n before continueing
n = n->lhs_;
} else { //if it is equal to the value (there are no other possible outcomes so an else would work) check if there are any subsiquent leaves attached
if (n->lhs_ == nullptr && n->rhs_ == nullptr) { //if both left and right are empty (I.E. no leaves attached to node) set n to nullptr and then delete using free();
nClone->lhs_ = nullptr; //stores both left
nClone->rhs_ = nullptr; // and right leaves as nullptr
free(n); //frees n
n = nullptr;
count_--;//decreases count_/size counter by 1
return; //exits from function as there is nothing more to do
} else if (n->lhs_ == nullptr || n->rhs_ == nullptr) { //if n has one connection whether it be on the left or right it stores itself in nClone and then deletes n
if (n->lhs_ != nullptr) { //if statement to check if left leaf of n exists
nClone->lhs_ = n->lhs_; //if it does it stores n's left leaf in nClone
} else { //if it doesnt have anything stored in the left then there garuntteed is one on the right
nClone->rhs_ = n->rhs_; //stores n's right leaf in nClone
}
free(n);
count_--; //decreases count_/size counter by 1
return; //exits from function as there is nothing more to do
} else {
//for preorder succession
node* nSuc = n->rhs_; //stores right leaf of n in nSuc
while (nSuc->lhs_ != nullptr) { //look for successor
nSuc = nSuc->lhs_;
}
n->value_ = nSuc->value_;
free(n);
count_--;
return;
}
}
}
}
你的代码就像是用 C 写的一样。C++ 是一种不同的语言，你可以而且应该利用它来发挥你的优势。
下面的文字中穿插了一个complete, compileable example，你可以在线尝试:)当然这不是实现树的唯一方法，我不得不掩盖实现树所需的各种细节至少让它成为一个功能齐全的解决方案。 “现实生活”的实现可能要复杂得多，因为“教科书”方法通常不能很好地与现代 CPU 上的缓存层次结构混合，并且与最先进的实现相比，像这样的树会相当慢.但我认为，它确实有助于弥合普遍的“类 C”树思维方式与现代 C++ 带来的差距。
再说一次：这个例子是最小的，它没有做很多通常实践中需要的事情，但它至少指向远离 C 和 C++ 的方向，这就是我的意图。
首先，让我们有一个 Node 类型，它使用子节点的拥有指针。这些指针自动管理内存并从根本上防止您犯下会泄漏内存或允许使用悬空指针的错误。术语“拥有指针”意味着总是有一个明确定义的所有者：它就是指针本身。例如，这些指针不能被复制——从那时起您将拥有同一个对象的两个所有者，为此您需要共享所有权。但是共享所有权很难做到正确，因为必须有一些适当的协议来确保您不会获得循环引用。构建树时，“父”节点是“子”节点的自然所有者，因此 unique 所有权正是所需要的。
// complete example begins
#include <cassert>
#include <memory>
using Value = int;
struct Node {
std::unique_ptr<Node> lhs_;
std::unique_ptr<Node> rhs_;
Value value_;
explicit Node(int value) : value_(value) {}
};
// cont'd.
我们还应该有一个 Tree 拥有根节点，并保持节点计数：
// cont'd.
struct Tree {
std::unique_ptr<Node> root_;
int count_ = 0;
};
// cont'd.
在对此类数据结构进行操作时，您经常不仅要访问节点指针的 值，还要访问指针本身这样就可以修改了。因此，我们需要某种“节点引用”，它的行为主要类似于 Node*，但在内部，它还携带指向节点的 指针 的地址，因此那例如节点可以是 replaced:
// cont'd.
class NodeRef {
std::unique_ptr<Node> *owner;
public:
NodeRef() = delete;
NodeRef(std::unique_ptr<Node> &o) : owner(&o) {}
Node *get() const { return owner->get(); }
// Use -> or * to access the underlying node
Node *operator->() const { return get(); }
Node &operator*() const { return *get(); }
// In boolean contexts, it's true if the Node exists
explicit operator bool() const { return bool(*owner); }
// Replace the Node (if any) with some other one
void replace(std::unique_ptr<Node> &&oldNode) {
*owner = std::move(oldNode);
}
NodeRef &operator=(std::unique_ptr<Node> &val) {
owner = &val;
return *this;
}
};
// cont'd.
NodeRef持有指向节点所有者的指针（所有者是拥有指针类型std::unique_ptr）。
以下是您可以像 Node* 一样使用 NodeRef 的方法：
NodeRef node = ...;
node->value_ // access to pointed-to Node using ->
(*node).value // access to pointed-to Node using *
if (node) ... // null check
node = otherNode; // assignment from another node (whether owner or NodeRef)
以下是 NodeRef 与 std::unique_ptr<Node> & 类似的行为方式，即类似于对节点所有者的引用，允许您更改所有权：
Tree tree;
NodeRef root = tree.root_; // reference the root of the tree
root.replace(std::make_unique<Node>(2)); // replace the root with a new node
请注意，由于 std::unique_ptr 和移动语义的强大功能，此代码执行所有必要的内存分配和释放。任何地方都没有 no new、delete、malloc 或 free 语句。而且，性能与手动分配相当——此代码不使用任何类型的垃圾收集或引用计数。 std::unique_ptr 是一种工具，可让您利用编译器以保证正确的方式为您编写内存分配和释放代码。
但是，NodeRef 不是一个“观察”指针，即如果它指向的节点的 owner 突然消失，那么 NodeRef 变成悬空。否则会产生更多的开销，并且需要使用一些跟踪指针，例如shared_ptr 和 weak_ptr，或者定制的解决方案——当然超出了这里的范围。
因此 NodeRef 满足了典型的要求，使实际的树管理代码更容易编写、理解和维护，并减少了出错的可能性。这种方法有利于设计正确的代码，即导致未定义行为的错误大多被编译器捕获，或者无法编写。
让我们看看二进制节点搜索的外观，使用我们上面介绍的类型：
// cont'd
// Finds the owner of a node that contains a given value,
// or the insertion point where the value would be
NodeRef find(Tree &tree, const Value &value)
{
NodeRef node = tree.root_;
while (node) {
if (value < node->value_)
node = node->lhs_;
else if (node->value_ < value)
node = node->rhs_;
else
break; // we found the value we need
}
return node;
}
// cont'd
首先，请注意，虽然 returned 节点引用可以为空，但这并不意味着它“无用”。 NodeRef 永远不会“完全”为 null，并且必须始终引用某个节点所有者 - 这就是删除默认构造函数的原因，因此您不能错误地创建无效的 NodeRef。 node 可以为 null，而不是指向该节点的拥有指针的底层引用。
请注意该代码与使用 Node * 的版本有多么相似，但它更强大。由于这个版本的findreturn是一个NodeRef，我们可以使用这个引用来替换节点（或者如果它是null则第一次设置），而签名Node *find(Node *root, const Value &value) 只会让我们访问节点本身，而不是它的所有者。而且，如果找不到节点，它将 return 一个空指针 - 也不会让我们更接近于知道在哪里插入新节点， 和 丢弃工作找到这样的插入点 (!)。
NodeRef 为我们提供了对父节点的谨慎访问：它不公开整个父节点，而只公开拥有给定节点的拥有指针——它也比“父节点”更通用节点将是，因为拥有指针甚至不需要由 Node 类型持有。事实上，当节点的所有者在 Tree class 中时，NodeRef 工作得很好，或者它也可以引用一个独立的指针：
std::unique_ptr<Node> myNode;
NodeRef node = myNode;
// The two lines below are equivalent - both change the `myNode` owning pointer
node.replace(std::make_unique<Node>(42));
myNode = std::make_unique<Node>(42);
原则上，可以有一个 NodeRef &NodeRef::operator=(std::unique_ptr<Node> &&)，即一种移动分配节点本身的方法，但这会隐藏一个重要的事实，即 NodeRef 并不真正拥有该节点，但仅指一些所有者，replace 方法使这一点更加明确：我们正在替换所有者持有的节点。
现在我们可以实现您要的功能：节点移除。此函数接受一个NodeRef，并修改该节点根部的子树，以便删除原始节点：
// cont'd
// Removes the given node. Returns true if the node was removed, or false if
// there was nothing to remove
bool remove(NodeRef node)
{
for (;;) {
if (!node) return false; // the node is empty, nothing to do
if (!node->lhs_) {
// replace the node with its sole right child, if any
node.replace(std::move(node->rhs_));
return true;
}
else if (!node->rhs_) {
// replace the node with its sole left child, if any
node.replace(std::move(node->lhs_));
return true;
}
else {
// node has two children
// 1. take on the largest value in the left subtree
// oldValue is a *reference* to the value of the node being replaced
Value &oldValue = node->value_;
node = node->lhs_;
while (node->rhs_) node = node->rhs_;
// we found the node with a replacement value - substitute it for
// the old value
oldValue = std::move(node->value_);
// 2. remove that child - continue the removal loop
continue;
// instead of continue, we could also do
// remove(node);
// return;
// but by continuing we don't have recursion, and we levarage
// the fact that the `node` references the correct node to remove
}
}
}
// cont'd
我们 std::move 值 - 这在处理像整数这样的“简单”值类型时根本不重要，但是如果 Value 是一种类型只能移动不能复制，例如using Value = std::unique_ptr<SomeType>;.
现在管理 Tree 中节点删除的助手：
// cont'd
void remove(Tree &tree, const Value& value)
{
auto node = find(tree, value);
if (remove(node))
-- tree.count_;
}
// cont'd
我们本可以使用 int value 而不是 const Value &value，但这种方法更通用，可以与其他 Value 类型一起使用。
节点插入也相当容易，因为 find 已经提供了值所在的插入点，如果它存在的话：
// cont'd
bool insert(Tree &tree, const Value& value)
{
auto node = find(tree, value);
if (node) {
// Such a value already exists
assert(node->value_ == value);
return false;
} else {
// Insert new value
node.replace(std::make_unique<Node>(value));
++ tree.count_;
return true;
}
}
// cont'd
如果 Value 是不可复制的类型，那么我们需要一个采用右值引用的 insert 签名，即 bool insert(Tree &tree, Value &&value).
现在您可能会问：我们将如何“行走”这棵树？在 C++ 中，处理项集合的惯用方法是通过迭代器，然后可以使用所谓的 range-for。以下示例打印出向量的元素：
std::vector<int> values{1,2,3,4,5};
for (int val : values)
std::cout << val << "\n";
在迭代或“遍历”树时，我们需要在身后留下一些“面包屑”，以便我们可以找到回到树上的路。那些需要引用节点，以及节点是否被访问或遍历：
// cont'd
#include <functional>
#include <stack>
#include <vector>
// An entry in the node stack used to iterate ("walk") the tree
struct BreadCrumb {
NodeRef node;
bool visited = false; // was this node visited?
bool traversedLeft = false; // was the left child descended into?
bool traversedRight = false; // was the right child descended into?
BreadCrumb(std::unique_ptr<Node> &owner) : node(owner) {}
BreadCrumb(NodeRef node) : node(node) {}
Node *operator->() const { return node.get(); }
explicit operator bool() const { return bool(node); }
};
// cont'd
我们沿着树向下走的“路径”保存在一个专门用于此目的的堆栈中：
// cont'd
// A stack holds the path to the current node
class NodeStack {
// Top of stack is the current node
std::stack<BreadCrumb, std::vector<BreadCrumb>> m_stack;
public:
NodeStack() = default;
NodeStack(NodeRef n) { if (n) m_stack.push(n); }
bool empty() const { return m_stack.empty(); }
// The breadcrumb that represents the top of stack, and thus the current node
BreadCrumb &crumb() { return m_stack.top(); }
const BreadCrumb &crumb() const { return m_stack.top(); }
NodeRef node() { return crumb().node; }
Node *node() const { return empty() ? nullptr : crumb().node.get(); }
void push(NodeRef n) { m_stack.push(n); }
// Visit and mark the node if not visited yet
bool visit() {
if (crumb().visited) return false;
crumb().visited = true;
return true;
}
// Descend one level via the left edge if not traversed left yet
bool descendLeft() {
if (crumb().traversedLeft) return false;
crumb().traversedLeft = true;
auto &n = crumb()->lhs_;
if (n) m_stack.push(n);
return bool(n);
}
// Descends one level via right edge if not traversed right yet
bool descendRight() {
if (crumb().traversedRight) return false;
crumb().traversedRight = true;
auto &n = crumb()->rhs_;
if (n) m_stack.push(n);
return bool(n);
}
// Ascends one level
bool ascend() {
m_stack.pop();
return !empty();
}
};
// cont'd
树遍历操作被抽象到栈中，因此剩余的代码是更高层次的，没有这些细节。
现在我们可以实现一个节点迭代器，它使用堆栈来保持其面包屑轨迹：
// cont'd
// Node Forward Iterator - iterates the nodes in given order
class NodeIterator {
using Advancer = void (NodeIterator::*)();
NodeStack m_stack; // Breadcrumb path to the current node
Advancer m_advancer; // Method that advances to next node in chosen order
Order m_order = Order::In;
public:
NodeIterator() = default;
// Dereferencing operators
Node& operator*() { return *m_stack.node(); }
Node* operator->() { return m_stack.node().get(); }
// Do the iterators both point to the same node (or no node)?
bool operator==(const NodeIterator &other) const {
return m_stack.node() == other.m_stack.node();
}
bool operator==(decltype(nullptr)) const { return !bool(m_stack.node()); }
bool operator!=(const NodeIterator &other) const { return m_stack.node(); }
bool operator!=(decltype(nullptr)) const { return bool(m_stack.node()); }
NodeIterator(NodeRef n, Order order = Order::In) : m_stack(n) {
setOrder(order);
if (n) operator++(); // Start the traversal
}
void setOrder(Order order) {
if (order == Order::In)
m_advancer = &NodeIterator::advanceInorder;
else if (order == Order::Pre)
m_advancer = &NodeIterator::advancePreorder;
else if (order == Order::Post)
m_advancer = &NodeIterator::advancePostorder;
m_order = order;
}
NodeIterator &operator++() { // Preincrement operator
assert(!m_stack.empty());
std::invoke(m_advancer, this);
return *this;
}
// No postincrement operator since it'd need to copy the stack and thus
// be way too expensive to casually expose via postincrement.
void advanceInorder();
void advancePreorder();
void advancePostorder();
bool goLeft() { return m_stack.descendLeft(); }
bool goRight() { return m_stack.descendRight(); }
};
// cont'd
还记得堆栈吗？它让我们相当简洁地描述了 in-、pre- 和 post-order 遍历：
// cont'd
void NodeIterator::advanceInorder() {
for (;;) {
if (m_stack.descendLeft())
continue;
if (m_stack.visit())
break;
if (m_stack.descendRight())
continue;
if (m_stack.ascend())
continue;
assert(m_stack.empty());
break;
}
}
void NodeIterator::advancePreorder() {
for (;;) {
if (m_stack.visit())
break;
if (m_stack.descendLeft())
continue;
if (m_stack.descendRight())
continue;
if (m_stack.ascend())
continue;
assert(m_stack.empty());
break;
}
}
void NodeIterator::advancePostorder() {
for (;;) {
if (m_stack.descendLeft())
continue;
if (m_stack.descendRight())
continue;
if (m_stack.visit())
break;
if (m_stack.ascend())
continue;
assert(m_stack.empty());
break;
}
}
// cont'd
现在，当我们希望迭代以某个节点为根的树时，我们需要一些简单的方法来使用此迭代器：
// cont'd
class TreeRangeAdapter {
NodeRef m_root;
Order m_order;
public:
TreeRangeAdapter(NodeRef root, Order order) :
m_root(root), m_order(order) {}
NodeIterator begin() const { return {m_root, m_order}; }
constexpr auto end() const { return nullptr; }
};
auto inOrder(NodeRef node) { return TreeRangeAdapter(node, Order::In); }
auto preOrder(NodeRef node) { return TreeRangeAdapter(node, Order::Pre); }
auto postOrder(NodeRef node) { return TreeRangeAdapter(node, Order::Post); }
// cont'd
这一切如何运作？这只是一个简单的填充树的例子，中序遍历：
// cont'd
#include <iostream>
#include <cstdlib>
int main() {
Tree tree;
for (int i = 0; i < 10; ++i) insert(tree, rand() / (RAND_MAX/100));
for (auto &node : inOrder(tree.root_)) {
std::cout << node.value_ << " ";
}
std::cout << "\n";
}
// complete example ends
输出：
19 27 33 39 55 76 78 79 84 91