当存储为节点和引用时，二叉树如何浪费内存？
How does a binary tree waste memory when stored as nodes and references?
我正在研究二叉树，偶然发现了描述存储方法的部分。
它指出：
In a language with records and references, binary trees are typically constructed by having a tree node structure which contains some data and references to its left child and its right child...
...This method of storing binary trees wastes a fair bit of memory, as the pointers will be null (or point to the sentinel) more than half the time...
有人可以演示或进一步解释为什么会这样吗？
https://en.wikipedia.org/wiki/Binary_tree#Methods_for_storing_binary_trees
想象一棵高度为 3 的完整二叉树。它有 7 个节点。其中4个没有children。 4/7 > 1/2.
典型的二叉树表示由与节点关联的数据和分别指向左右子树的两个指针组成。
我认为通过表示很容易实现每个节点花费两个指针。因此，n 个节点的每棵树在存储中总共花费了 2 x n 个指针（用于指针）。
现在好了，除了根之外，n-1 个节点都有一个父节点（即弧或边）。因此，您实际上使用了 2n 的 n-1 指针（如前一段所述）。
也就是说，在总共 2n 个指针中，您总是使用 n-1。其余 2n - (n-1) = n+1 始终设置为 null。因此，无论树形拓扑如何，您总是花费 space 来存储 null 指针而不是存储树弧。
我正在研究二叉树，偶然发现了描述存储方法的部分。
它指出：
In a language with records and references, binary trees are typically constructed by having a tree node structure which contains some data and references to its left child and its right child...
...This method of storing binary trees wastes a fair bit of memory, as the pointers will be null (or point to the sentinel) more than half the time...
有人可以演示或进一步解释为什么会这样吗？
https://en.wikipedia.org/wiki/Binary_tree#Methods_for_storing_binary_trees
想象一棵高度为 3 的完整二叉树。它有 7 个节点。其中4个没有children。 4/7 > 1/2.
典型的二叉树表示由与节点关联的数据和分别指向左右子树的两个指针组成。
我认为通过表示很容易实现每个节点花费两个指针。因此，n 个节点的每棵树在存储中总共花费了 2 x n 个指针（用于指针）。
现在好了，除了根之外，n-1 个节点都有一个父节点（即弧或边）。因此，您实际上使用了 2n 的 n-1 指针（如前一段所述）。
也就是说，在总共 2n 个指针中，您总是使用 n-1。其余 2n - (n-1) = n+1 始终设置为 null。因此，无论树形拓扑如何，您总是花费 space 来存储 null 指针而不是存储树弧。