Python数据结构——树的实现
“嵌套列表”表示树
在用嵌套列表表示树时，我们使用 Python 的列表来编写这些函数。虽然把界面写成列表的一系列方法与我们已实现其他的抽象数据类型有些不同，但这样做比较有意思，因为它为我们提供一个简单、可以直接查看的递归数据结构。在列表实现树时，我们将存储根节点作为列表的第一个元素的值。列表的第二个元素的本身是一个表示左子树的列表。这个列表的第三个元素表示在右子树的另一个列表。为了说明这个存储结构，让我们来看一个例子。图 1 展示出一个简单的树以及相应的列表实现。
图 1: 简单树
| 12345678 | myTree = [\’a\’, #root [\’b\’, #left subtree [\’d\’ [], []], [\’e\’ [], []] ], [\’c\’, #right subtree [\’f\’ [], []], [] ] ] |
请注意，我们可以使用索引来访问列表的子树。树的根是myTree[0]，根的左子树是myTree[1]，和右子树是myTree[2]。下面的代码说明了如何用列表创建简单树。一旦树被构建，我们可以访问根和左、右子树。嵌套列表法一个非常好的特性就是子树的结构与树相同，本身是递归的。子树具有根节点和两个表示叶节点的空列表。列表的另一个优点是它容易扩展到多叉树。在树不仅仅是一个二叉树的情况下，另一个子树只是另一个列表。
| 12345 | myTree = [\’a\’, [\’b\’, [\’d\’,[],[]], [\’e\’,[],[]] ], [\’c\’, [\’f\’,[],[]], []] ]print(myTree)print(\’left subtree = \’, myTree[1])print(\’root = \’, myTree[0])print(\’right subtree = \’, myTree[2]) |
让我们定义一些函数，使我们很容易像使用列表一样操作树。请注意，我们不会去定义一个二叉树类。我们将编写的函数将只是操作列表使之类似于树。
| 12 | def BinaryTree(r): return [r, [], []] |
该二叉树只是构建一个根节点和两个空子节点的列表。左子树添加到树的根，我们需要插入一个新的列表到根列表的第二个位置。我们必须注意，如果列表中已经有值在第二个位置，我们需要跟踪它，将新节点插入树中作为其直接的左子节点。Listing 1 显示了插入左子节点。
Listing 1
| 1234567 | def insertLeft(root,newBranch): t = root.pop(1) if len(t) > 1: root.insert(1,[newBranch,t,[]]) else: root.insert(1,[newBranch, [], []]) return root |
请注意，插入一个左子节点，我们首先获取对应于当前左子节点的列表（可能是空的）。然后，我们添加新的左子节点，将原来的左子节点作为新节点的左子节点。这使我们能够将新节点插入到树中的任何位置。对于insertRight的代码类似于insertLeft，如Listing 2 中。
Listing 2
| 1234567 | def insertRight(root,newBranch): t = root.pop(2) if len(t) > 1: root.insert(2,[newBranch,[],t]) else: root.insert(2,[newBranch,[],[]]) return root |
为了完善树的实现（参见Listing3），让我们写几个用于获取和设置根值的函数，以及获得左边或右边子树的函数。
Listing 3
| 1234567891011 | def getRootVal(root): return root[0] def setRootVal(root,newVal):。在列表实现树时，我们将存储根节点作为列表的第一个元素的值。列表的第二个元素的本身是一个表示左子树的列表。这个列表的第三个元素表示在右子树的另一个列表。为了说明这个存储结构，让我们来看一个例子。图 1 展示出一个简单的树以及相应的列表实现。
图 1: 简单树
请注意，我们可以使用索引来访问列表的子树。树的根是
让我们定义一些函数，使我们很容易像使用列表一样操作树。请注意，我们不会去定义一个二叉树类。我们将编写的函数将只是操作列表使之类似于树。
该二叉树只是构建一个根节点和两个空子节点的列表。左子树添加到树的根，我们需要插入一个新的列表到根列表的第二个位置。我们必须注意，如果列表中已经有值在第二个位置，我们需要跟踪它，将新节点插入树中作为其直接的左子节点。Listing 1 显示了插入左子节点。 Listing 1
请注意，插入一个左子节点，我们首先获取对应于当前左子节点的列表（可能是空的）。然后，我们添加新的左子节点，将原来的左子节点作为新节点的左子节点。这使我们能够将新节点插入到树中的任何位置。对于 Listing 2
为了完善树的实现（参见Listing3），让我们写几个用于获取和设置根值的函数，以及获得左边或右边子树的函数。 Listing 3
|
上一篇：奇怪的 dead lock
下一篇：Python初学者的17个技巧