Как построить двоичное дерево в C++-функции и вернуть его?

Question

Я сделал простую бинарную структуру дерева в C++:

template <class T> 
struct MyBinaryTree { 
    T val; 
    BinaryTree<T>* left; 
    BinaryTree<T>* right; 
    BinaryTree<T>(T v, BinaryTree<T>* l, BinaryTree<T>* r) 
     : val(v), left(l), right(r) {} 
}; 

Я хочу, чтобы написать функцию, которая создает бинарное дерево и возвращает его. К сожалению, эта структура содержит указатели. Следовательно, если я верну бинарное дерево в стеке, указатели станут неактуальными.

Есть ли способ вернуть двоичную структуру дерева?

Answer 1

Как уже отмечалось, вам нужно будет использовать динамическое выделение. При использовании new вам обычно необходимо подчиняться Rule of Three, Four, or Five. Это означает, что вам нужно будет принять решение о том, как разрушение, построение копии, назначение, перемещение конструкции и перемещение назначения должны вести себя и реализовывать их. Обычно для контейнера требуется глубокая семантика. Даже если вы используете интеллектуальные указатели, чтобы сделать уничтожение простым, вам нужно сделать что-то еще, чтобы сделать копии в глубину.

Однако для применения динамического распределения памяти необязательно включать new. Например, вы могли бы использовать list<> представлять left и right вместо этого, и делать это таким образом дает глубокие копии семантики автоматически:

template <typename T> 
class MyBinaryTree { 
    T val_; 
    std::list< MyBinaryTree<T> > left_; 
    std::list< MyBinaryTree<T> > right_; 

    template <typename U> 
    friend MyBinaryTree<U> MakeMyBinaryTree (U v, 
              MyBinaryTree<U> *l = 0, 
              MyBinaryTree<U> *r = 0) { 
     MyBinaryTree<U> t; 
     t.val_ = v; 
     if (l) t.left_.push_back(*l); 
     if (r) t.right_.push_back(*r); 
     return t; 
    } 

public: 
    MyBinaryTree<T>* left() { return left_.empty() ? 0 : &*left_.begin(); } 
    MyBinaryTree<T>* right() { return right_.empty() ? 0 : &*right_.begin(); } 
    T & val() { return val_; } 
}; 

MyBinaryTree<int> make_a_tree() 
{ 
    MyBinaryTree<int> n1 = MakeMyBinaryTree(1); 
    MyBinaryTree<int> n3 = MakeMyBinaryTree(3); 
    return MakeMyBinaryTree(2, &n1, &n3); 
} 

Вместо list<>, вы могли бы использовать Boost.Optional, или если C++ 14 для вас, std::optional.

Answer 2

Создан динамический контейнер - например. тот, который построен во время выполнения. В случае таких структур вы должны распределять их динамически и использовать указатель, чтобы ссылаться на них. То есть:

MyBinaryTree * BuildSimpleTree() 
{ 
    BinaryTree<int> * node1 = new BinaryTree(0, nullptr, nullptr); 
    BinaryTree<int> * node2 = new BinaryTree(0, nullptr, nullptr); 

    return new MyBinaryTree<int>(0, node1, node 2); 
} 

MyBinaryTree * tree = BuildSimpleTree(); 

Причиной требования динамического распределения является то, что все локальные статически выделенные объекты (например, находящиеся на стеке вместо кучи.) Автоматически уничтожаются, когда вы выходите из функции или метода. Однако, чтобы дерево работало правильно, все его дети (и рекурсивно их дети) остаются живыми после возвращения из функции, поэтому их нужно распределять динамически.

Вы должны помнить, хотя бесплатно все экземпляров выделенных классов. Это можно сделать вручную или автоматически, рекурсивно - в BinaryTree и MyBinaryTree dtors.

---

Если вы можете скомпилировать код, используя C++ 11, всегда есть возможность использовать перемещение семантику - вы сможете вернуть дерево по значению и сохранить код быстро и эффективно использует память в то же время. Это решение будет выглядеть следующим образом:

template <class T> 
struct MyBinaryTree 
{ 
    T val; 
    BinaryTree<T>* left; 
    BinaryTree<T>* right; 
    BinaryTree<T>(T v, BinaryTree<T>* l, BinaryTree<T>* r) 
     : val(v), left(l), right(r) 
    { 
    } 

    BinaryTree<T>(BinaryTree<T> && r) 
    { 
     val = r.val; 
     left = r.left; 
     right = r.right; 
    } 
}; 

Затем вы можете вернуть свое дерево по значению (но по-прежнему строит узлы динамически):

MyBinaryTree BuildTree() 
{ 
    auto left = new BinaryTree<int>(0, nullptr, nullptr); 
    auto right = new BinaryTree<int>(0, nullptr, nullptr); 
    MyBinaryTree<int> result(0, left, right); 
    return result; 
} 

Answer 3

Вы должны динамически выделять данные. Например, чтобы создать

2 
/\ 
1 3 

используя структуру вы могли бы сделать следующее:

MyBinaryTree<int>* getTestStructure(){ 
    MyBinaryTree<int> *root = new MyBinaryTree<int>(2); 
    MyBinaryTree<int> *leftChild = new MyBinaryTree<int>(1); 
    MyBinaryTree<int> *rightChild = new MyBinaryTree<int>(3); 
    root.left = leftChild; 
    root.right = rightChild; 
    return root; 
}