顺序存储结构的二叉树
时间: 2023-12-01 13:40:35 浏览: 40
顺序存储结构的二叉树是一种使用数组来存储二叉树的结构。在这种结构中,我们使用数组来存储二叉树的节点,具体的存储方式是按照层次遍历的顺序,从上到下、从左到右依次存储每个节点。对于一个节点的下标为i,它的左子节点的下标为2i,右子节点的下标为2i+1,它的父节点的下标为i/2。这种存储方式可以有效地节省空间,但是在插入和删除节点时需要进行大量的数据移动,效率较低。
顺序存储结构的二叉树通常用于存储堆,堆是一种特殊的二叉树,它满足父节点的值总是大于或小于它的子节点的值。堆可以用于实现优先队列等数据结构,常见的堆有最大堆和最小堆。
下面是一个使用数组实现最小堆的例子:
```python
class MinHeap:
def __init__(self):
self.heap = [0]
self.size = 0
def push(self, val):
self.heap.append(val)
self.size += 1
self._sift_up(self.size)
def pop(self):
if self.size == 0:
return None
val = self.heap[1]
self.heap[1] = self.heap[self.size]
self.heap.pop()
self.size -= 1
self._sift_down(1)
return val
def _sift_up(self, i):
while i // 2 > 0:
if self.heap[i] < self.heap[i // 2]:
self.heap[i], self.heap[i // 2] = self.heap[i // 2], self.heap[i]
i //= 2
def _sift_down(self, i):
while i * 2 <= self.size:
min_child = self._get_min_child(i)
if self.heap[i] > self.heap[min_child]:
self.heap[i], self.heap[min_child] = self.heap[min_child], self.heap[i]
i = min_child
def _get_min_child(self, i):
if i * 2 + 1 > self.size or self.heap[i * 2] < self.heap[i * 2 + 1]:
return i * 2
else:
return i * 2 + 1
```