构建高度为 30 的完美二叉树
Building a perfect binary tree with height 30
我正在尝试构建一棵高度为30的完美二叉树。它不一定是BST，只是一棵普通树；数据也不重要，因此每个节点的数据都可以为空。我以前从未尝试过这样做，所以当我创建这棵树的方法导致疯狂的内存使用并在 运行 几分钟后开始锁定我的计算机时，我有点沮丧。这是我的 Python 构建树的代码：
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.data = val
def build_tree(h):
node = Node(0)
if h == 1:
return node
node.left = build_tree(h-1)
node.right = build_tree(h-1)
return node
root = build_tree(30)
可能值得一提的是，我也尝试过使用列表表示法。不幸的是，这样大小的列表的内存使用也是有问题的。
任何人都可以阐明一种不使用太多内存并且可以在合理的时间内完成的方法吗？
在一棵完美的二叉树中，每一层的节点数都会翻倍。 n 层的二叉树中的节点总数为 2**n-1。这意味着具有 30 个级别的完美二叉树将具有
1,073,741,823
个节点。这将导致 "insane memory usage" 除非你重复节点，这是一个 "perfect binary tree."
您能做的最好的事情就是为每个节点使用尽可能少的内存。我能想到的最好的方法是使用完整二叉树的列表表示——索引 j 处节点的子节点位于索引 2*j 和 2*j+1 处，父节点位于指数 j//2。 （这是针对 one-based 数组的。）这意味着您不需要存储指向子节点或父节点的指针或索引。最后，使用占用内存尽可能少的列表。 TNumpy's Boolean array 每个项目只使用一个字节。这仍然意味着您的树需要 1 GB 的内存。
我正在尝试构建一棵高度为30的完美二叉树。它不一定是BST，只是一棵普通树；数据也不重要，因此每个节点的数据都可以为空。我以前从未尝试过这样做，所以当我创建这棵树的方法导致疯狂的内存使用并在 运行 几分钟后开始锁定我的计算机时，我有点沮丧。这是我的 Python 构建树的代码：
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.data = val
def build_tree(h):
node = Node(0)
if h == 1:
return node
node.left = build_tree(h-1)
node.right = build_tree(h-1)
return node
root = build_tree(30)
可能值得一提的是，我也尝试过使用列表表示法。不幸的是，这样大小的列表的内存使用也是有问题的。
任何人都可以阐明一种不使用太多内存并且可以在合理的时间内完成的方法吗？
在一棵完美的二叉树中，每一层的节点数都会翻倍。 n 层的二叉树中的节点总数为 2**n-1。这意味着具有 30 个级别的完美二叉树将具有
1,073,741,823
个节点。这将导致 "insane memory usage" 除非你重复节点，这是一个 "perfect binary tree."
您能做的最好的事情就是为每个节点使用尽可能少的内存。我能想到的最好的方法是使用完整二叉树的列表表示——索引 j 处节点的子节点位于索引 2*j 和 2*j+1 处，父节点位于指数 j//2。 （这是针对 one-based 数组的。）这意味着您不需要存储指向子节点或父节点的指针或索引。最后，使用占用内存尽可能少的列表。 TNumpy's Boolean array 每个项目只使用一个字节。这仍然意味着您的树需要 1 GB 的内存。