c++ - 如何在C++函数中构造二叉树并将其返回？

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center。




7年前关闭。




我在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) {}
};

我想编写一个创建二叉树并将其返回的函数。不幸的是，该结构包含指针。因此，如果我在堆栈上返回二叉树，则指针将变得无关紧要。

有没有办法让我返回二叉树结构？

最佳答案

正如其他人指出的那样，您将需要利用动态分配。使用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);
}

可以使用Boost.Optional代替list<>，或者如果您可以使用C++ 14，请使用 std::optional 。

关于c++ - 如何在C++函数中构造二叉树并将其返回？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16910035/