从矢量创建树

Question

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

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

  4
 /
1

迭代 2： 8 大于最后一个引用 (4)。所以我们

  8
 /
3

4 的权利 child 并保留 8

的参考

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

 7
  \
   5

并将最后一个引用添加到此 child。

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

这是我的树 class:

#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

这是我的 main.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();
}

当我在第 2 次迭代中复制 4-1 分支时，不知何故被删除了。第一次打印的时候还在，复制之后就没了

Answer 1

问题出在下面这几行

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

一开始只有shared_ptrlast指向节点4，你把newNode赋值给last后，就没有shared_ptr指向节点4了了。这导致节点 8 中的 weak_ptr parent 过期。因此，当您调用 last->findRoot()（最后这里是节点 8）时，它无法 return 节点 4.

您的数据结构确保除根节点外的每个节点至少由 1 shared_ptr（其父节点）指向。所以你需要手动保留一个shared_ptr到根节点。

从矢量创建树

Create Tree from Vector

c++

algorithm

binary-tree

smart-pointers