用数组结构表示完整但不完整的二叉树

Question

我一直在阅读有关二叉堆的内容，我想知道是否有类似的表示可以用于表示不完整的二叉树，如果该二叉树碰巧也是满的。

我们可以使用某种竞技场分配来表示任何二叉树，使用内存竞技场的索引而不是指针，但是二叉堆表示利用树的完整性来压缩表示。是否有任何类似的技术可用于整棵树？

Answer 1

可以利用满二叉树的隐含结构来压缩结构，但它仍然是

O(n)

空间。例如，我使用了 Patrica trie 是一个完整的二叉树来表示紧凑的 (n-1)/2 数字中的结构，其中 n 是节点，（对应于内部节点）。

在我的例子中，我使用了以左子节点为根的子树中有多少个内部节点。结合初始特里结构大小的知识，这允许向下遍历特里结构。例如，[1,0,0]被重构为一棵有7个节点的树：