二叉树列表表示

Question

我一直在做一些关于二叉树和数组列表表示的研究。我很难理解最坏情况下的空间复杂度是O（2^n）。具体而言，该书指出，空间使用是O（N）（N =数组大小），在最坏的情况下是O（2^n）。如果每个节点有两个孩子（索引）不是O（2^n），其中n = no，我会认为它在最坏的情况下会是2n。的元素。

一个例子，如果我有一个二叉树与7个节点，则空间会为2n = 14不是2^N = 128。

Answer 1

这是一个阵列上的堆实现。其中

A[1..n] 
left_child(i) = A[2*i] 
right_child(i) = A[2*i+1] 
parent(i) = A[floor(i/2)] 

现在，来到空间。想直观，

当您插入第一个元素n = 1，位置= A [1]，同样，

n=2 @A[2] left_child(1) 
n=3 @A[3] right_child(1) 
n=4 @A[4] left_child(2) 
n=5 @A[5] right_child(2) 

你看，正^日元素将进入A[n]。所以空间复杂度是O(n)。

当你编码时，你只需插入要插入的元素，最后说的是A[n+1]，并且说它是floor((n+1)/2)的孩子。

参见：http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation

---

堆是几乎完整的树，在树中的元素，这样总数将是2h-1 < n <= 2h+1-1，这是数组的长度，你需要什么。参见：this

Answer 2

二进制树的最坏情况下的空间复杂度是O（ n）（不是O（2^n）在你的问题中），但使用数组来表示二叉树可以节省指针的空间，如果它几乎是一个完整的二叉树。

参见http://en.wikipedia.org/wiki/Binary_tree#Arrays

Answer 3

我认为这指的是在一个数组表示，这是通常用于完整或几乎完全二叉树存储任意二叉树，特别是在堆的实施。

在这个表示中，根存储在数组中的索引0，以及用于与索引n任何节点，其左和右的儿童存储在索引2n+1和2n+2，分别。

如果你有一个没有节点的退化树（树实际上是一个链表），那么第一项将被存储在索引0, 1, 3, 7, 15, 31, ...。通常，此列表中的第n个项目（从0开始）将存储在索引2n-1，因此在这种情况下，数组表示需要θ(2n)空间。