不使用指针的树实现？

Question

我在某个地方找到了这段代码，它是一棵树的简单实现。为什么 left 和 right 必须是指向 Node 的指针？换句话说，如果 left 和 right 不是指针并且只是 Node 类型，你还能实现一棵树吗？如果是这样，有人可以提供一个例子吗

#include <iostream>

struct Node { 
    int data; 
    struct Node* left; 
    struct Node* right; 
  
    Node(int val) { 
        data = val;
        left = NULL; 
        right = NULL; 
    } 
};

int main(int argc, char* argv[]) {
    struct Node* root = new Node(0);
    root->left = new Node(1);
    root->right = new Node(0);
    root->right->left = new Node(1);
    root->right->right = new Node(0);
    root->right->left->left = new Node(1);
    root->right->left->right = new Node(1);

    std::cout << root->data << "\n";
}

感谢所有帮助，谢谢！

Answer 1

更简单的链表例子，即每个Node只有一个next:

struct Node {
    Node next;
};

C++不允许这样做，你会得到一个错误，但让我们考虑一下没有错误。然后每个 Node 包含另一个 Node 并且该成员再次包含另一个 Node。 Node 还有另一个成员 next 也是 Node。此 Node 具有类型 Node 的成员 next。 Node 还有另一个成员 next 也是 Node。此 Node 有一个 next 类型的成员 Node... 无限。

也许您来自一种语言，其中对象实际上是引用。在 C++ 中，对象就是对象。它不能是“无对象”。对象不能是 NULL.

另一方面，指针可以指向一个对象，但也可以指向任何地方。这很好：

 struct Node {
     Node* next;
 };

每个 Node 都有一个成员 next 指向 Node 或不指向 Node。

C++ 中不允许第一个原因的一种方法是编译器必须知道成员的大小。无论对象本身的大小如何，指针的大小都是相同的。但是，正如上面所解释的，这不是C++的限制，而是不可能有无限多次包含自己的东西。

不使用指针的树实现？

Tree implementation without using pointers?

c++

pointers

reference