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

Question

一些 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 的情况下，如何构建这样一个基于指针的二叉树？

Answer 1

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

唯一可能的方法是将整个树置于自动或全局范围内，并手动构建:

BTNode root;
BTNode left, right;

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

但是，要么整个事情都被破坏了，当自 Action 用域被留下时，要么你现在有一堆丑陋的全局变量。

动态范围和动态内存分配没有错；前提是正确使用。