2

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

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

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

4

3 回答 3

2

正如其他人所指出的，您将需要使用动态分配。使用 时new，您通常需要遵守三、四或五规则。这意味着您需要决定销毁、复制构造、分配、移动构造和移动分配应该如何表现并实现它们。通常对于容器，您需要深度复制语义。即使您使用智能指针使销毁变得简单，您也需要做更多的事情来使副本更深。

However, one doesn't necessarily need to involve new to apply dynamic memory allocation. For example, you could use a list<> to represent left and right instead, and doing it this way gives you deep copy semantics automatically:

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);
}

Instead of list<>, you could use Boost.Optional, or if C++14 is available to you, std::optional.

于 2013-06-04T05:53:22.843 回答
1

您创建了一个动态容器 - 例如。一个，它是在运行时构建的。在这种结构的情况下，您必须动态分配它们并使用指针来引用它们。那是：

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;
}
于 2013-06-04T04:59:09.670 回答
1

您需要动态分配数据。例如创建

  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;
}
于 2013-06-04T05:00:37.827 回答