使用 python 中的列表表示树
Tree representation using list in python
对于这棵树，
作为初学者，下面是我的列表表示，
tree = [
[
[
[
[], 3, []
],
10,
[
[], 17, []
]
],
25,
[
[
[], 30, []
],
32,
[
[], 38, []
]
]
],
40,
[
[
[], 50, []
],
78,
[
[], 93, []
]
]
]
使用 python 列表这种表示是否正确？
我可以在这个表示中避免空列表 [] 吗？
这取决于你所说的 'represent' 是什么意思。您可以仅通过列表中的元素来表示树，例如list = [40,25,78,10,32,50,93,3,17,30,38] 然后遍历它，如果你想重新创建你可以遍历列表的树，因为你知道生命 child of list[(i+1)*2-1] 右边的child是list[(i+1)*2]。
注意：你必须执行 i+1 因为第一个元素的索引为 0，而 I 是 parent 节点的索引，例如25 的索引+1 是 2 因此 25 的左索引+1 child 是 4.
使用列表表示树的方法有很多种。
您可以使用一维列表。这对于具有一定数量 children 的完整树非常有效。或者对于缺少 children 的数组，用 None 填充数组，其中叶节点的 child 应该是。
如果当前节点位于索引 i，则其 children 将位于索引 i*2 + 1 和 (i+1)*2。你的 parent 将是 (i-1)/2.
您也可以使用 lisp-like 树表示。
[根, LEFT_SUB_TREE, RIGHT_SUB_TREE]
你的示例树看起来像：
[40, [25, [10, 3, 17], [32, 30, 38]], [78, 50, 93]]
叶节点不需要是一个列表，它们可以只是它们的值。
与一维列表表示相比，此方法为备用树使用的内存更少。
对于任何二叉树也很容易做到这一点，每个节点的 children 数量不同。
[根, SUB_TREE_1, SUB_TREE_2, ..., SUB_TREE_n]
你的表示很有意义，因为它只使用了 2 个简单的规则。树是一个列表，可以是：
[] #empty tree
[list, number, list] #non-empty tree
这种简单性使得以统一的方式编写代码和处理事物变得容易（并且没有很多 if 语句）。
另一个同样简单的表示是使用元组而不是列表 and/or 使用 None 表示空树。
另一种表示是将叶子节点中的数字直接放在父节点中（例如将10以下的子树编码为[3,10,17]）。这更紧凑并摆脱了空列表，但现在逻辑更复杂，一棵树可以用 5 种不同的方式表示：
[]
[list, number, list]
[list, number, number]
[number, number, list]
[number, number, number]
表示更复杂意味着您可能需要编写更多代码。
对于这棵树，
作为初学者，下面是我的列表表示，
tree = [
[
[
[
[], 3, []
],
10,
[
[], 17, []
]
],
25,
[
[
[], 30, []
],
32,
[
[], 38, []
]
]
],
40,
[
[
[], 50, []
],
78,
[
[], 93, []
]
]
]
使用 python 列表这种表示是否正确？
我可以在这个表示中避免空列表 [] 吗？
这取决于你所说的 'represent' 是什么意思。您可以仅通过列表中的元素来表示树，例如list = [40,25,78,10,32,50,93,3,17,30,38] 然后遍历它，如果你想重新创建你可以遍历列表的树，因为你知道生命 child of list[(i+1)*2-1] 右边的child是list[(i+1)*2]。
注意：你必须执行 i+1 因为第一个元素的索引为 0，而 I 是 parent 节点的索引，例如25 的索引+1 是 2 因此 25 的左索引+1 child 是 4.
使用列表表示树的方法有很多种。
您可以使用一维列表。这对于具有一定数量 children 的完整树非常有效。或者对于缺少 children 的数组，用 None 填充数组，其中叶节点的 child 应该是。 如果当前节点位于索引 i，则其 children 将位于索引 i*2 + 1 和 (i+1)*2。你的 parent 将是 (i-1)/2.
您也可以使用 lisp-like 树表示。
[根, LEFT_SUB_TREE, RIGHT_SUB_TREE]
你的示例树看起来像：
[40, [25, [10, 3, 17], [32, 30, 38]], [78, 50, 93]]
叶节点不需要是一个列表，它们可以只是它们的值。
与一维列表表示相比，此方法为备用树使用的内存更少。
对于任何二叉树也很容易做到这一点，每个节点的 children 数量不同。
[根, SUB_TREE_1, SUB_TREE_2, ..., SUB_TREE_n]
你的表示很有意义，因为它只使用了 2 个简单的规则。树是一个列表，可以是：
[] #empty tree
[list, number, list] #non-empty tree
这种简单性使得以统一的方式编写代码和处理事物变得容易（并且没有很多 if 语句）。
另一个同样简单的表示是使用元组而不是列表 and/or 使用 None 表示空树。
另一种表示是将叶子节点中的数字直接放在父节点中（例如将10以下的子树编码为[3,10,17]）。这更紧凑并摆脱了空列表，但现在逻辑更复杂，一棵树可以用 5 种不同的方式表示：
[]
[list, number, list]
[list, number, number]
[number, number, list]
[number, number, number]
表示更复杂意味着您可能需要编写更多代码。