c++ - 如何在 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 .