如何在不使用动态内存分配的情况下创建基于指针的二叉树？

一些C++程序员说动态内存分配不好，应尽可能避免。我试图做一个二叉树数据结构，而不使用动态内存分配，它不起作用。下面是我的尝试：如何在不使用动态内存分配的情况下创建基于指针的二叉树？

struct BTNode { 
    BTNode *left = 0, *right = 0; 
    int data; 

    BTNode(int d_) { data = d_; } 

    void insert(int d_) { 
     BTNode n(d_); 
     if (d_ <= data) 
      if (left == 0) left = &n; 
      else left->insert(d_); 
     else 
      if (right == 0) right = &n; 
      else right->insert(d_); 
    } 
}

然后在主做这个...

BTNode root(8); 
root.insert(9); 
root.insert(10); 
cout << root.right->right->data;

导致段错误，因为包含数据的BTNode很久以前出去的范围。

我的问题是，如何构建一个基于指针的二叉树，而不使用new和delete？

来源

2016-07-24 Coffee Maker

使用值而不是指针 – user4759923

您可以创建一个包含足够元素的BTNode数组，并将其用作内存池，从数组中获取节点。 – MikeCAT

你可以创建一个'std :: vector '来容纳所有的节点。我个人认为这不是必要的。我会简单地执行'auto newNode = new BTNode（8）;'然后设置适当的指针。 –

简短的回答是：你几乎不能。

唯一可能的途径是整个树是为以自动或全球范围内，并手动构造：

BTNode root; 
BTNode left, right; 

root.left=&left; 
root.right=&right;

但是，无论是整个事情被破坏，自动范围离开的时候，或者你现在有一堆丑陋的全局变量。

动态范围和动态内存分配没有任何问题;只要它使用正确。

来源

2016-07-24 02:53:16

您可以将所有节点放在一个std::array<>中。当你释放你的阵列时，他们可以自由地指向对方，你的所有节点也会被安全地释放。您只需确保知道阵列中的哪些元素已被使用。

任何方式，出于教育原因，或者如果你有非常非常好的理由不使用标准库提供的，请只实现你自己的树和类似的容器。在后一种情况下，尽可能模拟标准接口，以便为其他C++开发人员提供标准算法，基于范围的for循环和易于理解的代码。

来源

2016-07-24 07:38:56 cdonat

插入方法在堆栈中分配BTNode对象，这意味着插入函数返回后对象的内存无效。

你可以做

 BTNode newObj(9) 
     root.insert(newObj);

你也必须修改插入方法

 void insert(BTNode &node) { ...

在这种情况下newObj对象范围仍然直到你离开你的主要功能。更好的是，你可以使它成为静态作用域，然后它将在程序期间。

来源

2016-07-24 09:46:26 MichaelMoser

如何在不使用动态内存分配的情况下创建基于指针的二叉树？

回答

相关问题