从向量创建树

Question

我正在研究一个符号计算器。但为了给出一个小的可验证的例子，我把它分解为下面的例子，乍一看可能很奇怪。

我有一个点 {1， 4， 3， 8， 5， 7} 的列表，我对其进行了迭代。我在每次迭代中读了两点。 我希望这段代码做的是：
迭代 1：没有树，所以我们创建一个。我们保留了4的参考。

4
/
1

迭代 2：8 大于上次引用 (4)。所以我们使

8
/
3

4岁的正确孩子，并在8上保持参考

4
/   
1      8
/
3

迭代 3：7 小于最后一个引用 (8)，因此我们返回，直到找到小于 4 的数字(或到达根)。然后我们创建节点

7

5

并将最后一个引用作为左子项添加到此引用中。

7
/   
4      5
/  
1    8
/
3

请注意：我不关心这里的特殊情况等。我很肯定，一旦我开始工作，我就可以自己解决这个问题。

这是我的树类：

#ifndef NODE_H
#define NODE_H
#include <memory>
#include <string>
template<typename T>
class Node : public std::enable_shared_from_this< Node<T> >{
public:
typedef std::shared_ptr< Node<T> > NodePtr;
typedef std::weak_ptr< Node<T> > NodeWPtr;
T data;
NodePtr left, right;
NodeWPtr parent;
Node(){}
Node(const T& data) : data(data){}
Node(const T& data, NodeWPtr parent) : data(data), parent(parent){}
Node(const T& data, NodeWPtr parent, NodePtr& left) : data(data), parent(parent), left(left){
left->parent = this->shared_from_this();
}
Node(const Node& n) : data(n.data), left(n.left), right(n.right){}
Node& operator=(const Node&) = delete;
~Node() = default;
NodePtr findRoot(){
if( parent.lock() ){
return parent.lock()->findRoot();
}
return this->shared_from_this();
}
void print(int indent=0){
std::cout << data << std::endl;
std::cout << std::string(2*indent+2, '-') << "L: ";
if( left ){
left->print(indent+1);
}
std::cout << std::endl;
std::cout << std::string(2*indent+2, '-') << "R: ";
if( right ){
right->print(indent+1);
}
if( indent==0 ) std::cout << std::endl;
}
};
#endif // NODE_H

这是我的主要.cpp

#include <iostream>
#include <vector>
#include "Node.h"
int main(){
typedef std::shared_ptr< Node<int> > NodePtr;
NodePtr last;
std::vector<int> list {1, 4, 3, 8, 5, 7};
for( unsigned int i = 0; i < list.size(); i += 2 ){
if( !last ){
last = std::make_shared< Node<int> >(Node<int>(list.at(i+1)));
last->left = std::make_shared< Node<int> >(Node<int>(list.at(i), last));
continue;
}
if( list.at(i+1) >= last->data ){
NodePtr newNode = std::make_shared< Node<int> >(Node<int>(list.at(i+1)));
newNode->left = std::make_shared< Node<int> >(Node<int>(list.at(i)));
last->right = newNode;
newNode->parent = last;
newNode->findRoot()->print();
last = newNode;
last->findRoot()->print();
}else{
while( !last->parent.expired() && last->data < list.at(i+1) ){
last = last->parent.lock();
}
NodePtr newNode = std::make_shared< Node<int> >(Node<int>(list.at(i+1)));
newNode->right = std::make_shared< Node<int> >(Node<int>(list.at(i)));
newNode->left = last;
last->parent = newNode;
last = newNode;
}
}
last->findRoot()->print();
}

不知何故，当我在第二次迭代中复制 4-1 分支时，它被删除了。它在第一次印刷中仍然存在，但在复制之后，它就消失了。

Answer 1

问题出在下面这几行

newNode->parent = last;
newNode->findRoot()->print();
last = newNode;

最初，只有 shared_ptrlast指向节点 4。将newNode分配给last后，不再有指向节点 4 的shared_ptr。这会导致节点 8 中的weak_ptrparent过期。因此，当您调用last->findRoot()(此处的最后一个是节点 8)时，它无法返回节点 4。

您的数据结构确保除根节点外，每个节点都指向至少 1 个shared_ptr(其父节点)。因此，您需要手动保留对根节点的shared_ptr。