增加二叉树的正确方法

Question

这是我创建的类

#include <memory>
template <typename T> 
class binary_tree {
private:
T t_data;
std::unique_ptr<binary_tree<T>> t_left, t_right;

class binary_tree_iterator {                  // -----------------------
private:
T data;
public:                                       
binary_tree_iterator(T d) : data(d) {}    //     Iterator class
T& operator*() {return data;}
binary_tree_iterator& operator++() {} // <--------- ??????
};                                            
// ------------------------
public:
binary_tree(T d) : t_data(d), t_left(nullptr), t_right(nullptr)
{}

void insert(T data) {
if(data <= t_data) {
if(t_left == nullptr) {
t_left = std::unique_ptr<binary_tree<T>>(new binary_tree<T>(data));
} else {
t_left->insert(data);
}          
} else {
if(t_right == nullptr)
t_right = std::unique_ptr<binary_tree<T>>(new binary_tree<T>(data));
else
t_right->insert(data);
}
}

const T data() const {
return t_data;
}

const std::unique_ptr<binary_tree<T>>& left() const {
return t_left;
}

const std::unique_ptr<binary_tree<T>>& right() const {
return t_right;
}

binary_tree_iterator begin() {      
if(t_left == nullptr) {
return binary_tree_iterator(t_data);
} else {
return t_left->begin();
}
}

binary_tree_iterator end() {
if(t_right == nullptr) {
return binary_tree_iterator(t_data);
} else {
return t_right->end();
}
}
};

我在容器类中声明了迭代器类。这可能是一个错误，但无论哪种方式，我不确定如何定义我的重载增量函数。一旦我找到了begin()，我就迷路了。unique_ptr()似乎是为单向指向而设计的。假设我必须以这种方式使用unique_ptr，这里有一些工作吗?我考虑过给binary_tree的每个实例一个头成员，它指向它来的地方，但是每个节点应该只能从它上面的节点访问。我做了一些索引，但这似乎完全违背了这种容器类型的目的。我正在解决练习，所以我被限制使用unique_ptr.

Answer 1

您将迭代器定义为包含树中的data值。

这不是迭代器的全部意义。迭代器不包含它们所引用的值，而是包含对该值的引用(一般意义上的引用，而不是c++术语)，通常是指针。

当然你不知道怎么处理++。对于迭代器，很自然地期望++操作符将迭代器推进到树中的下一个节点，但是由于迭代器不包含指向任何东西的指针，因此没有任何东西可以推进到那里，并且遇到了心理阻塞。

你需要重新设计你的迭代器，使它包含一个指向binary_tree的指针;它的*重载解引用;并且++将使用其指针前进到二叉树中的下一个元素，然后它将能够这样做。

在这一点上，你会遇到另一个心理障碍。遍历整个二叉树需要在某些时候备份到树中的父节点。毕竟，在递归到二叉树的left部分之后，在某一点上，在遍历二叉树之后，你需要，以某种方式，在二叉树的right部分结束。但是，按照设计，您的binary_tree没有导航到任何节点的父节点的方法。这是您需要以某种方式解决的另一个设计缺陷。

我认为，在迭代器本身中实现整个回溯是可能的，让迭代器记录其访问的每个节点，以便在需要时备份到它。但是，迭代器应该是轻量级对象，本身只不过是一个指针，而不是实现复杂操作的完整数据结构。

总之，在为二叉树实现一个有效的迭代器之前，您需要解决二叉树设计中的几个漏洞。