5.2 使用列表表示的树_Python算法详解-QQ阅读女生短篇网

上QQ阅读APP看书，第一时间看更新

5.2 使用列表表示的树

图5-4展示了一棵简单的树以及相应的列表实现。

我们可以使用索引来访问列表的子树。树的根是myTree[0]，根的左子树是myTree[1]、右子树是myTree[2]。例如在下面的实例文件shu.py中，演示了使用列表创建简单树的过程。树一旦被构建，就可以访问根和左、右子树。嵌套列表法的一个非常好的特性就是：子树的结构与树相同，本身是递归的。子树具有根节点和两个表示叶节点的空列表。列表的另一个优点是容易扩展到多叉树。在树不仅仅是一棵二叉树的情况下，另一棵子树只是另一个列表。

源码路径：daima\第5章\shu.py

myTree = ['a',
         ['b',
         ['d',[], []],
         ['e', [], []] ],
         ['c',  #right subtree
         ['f' ,[], []],
         [] ]
     ]
myTree = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]
print(myTree)
print('left subtree = ', myTree[1])
print('root = ', myTree[0])
print('right subtree = ', myTree[2])

执行后会输出：

['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]
left subtree = ['b', ['d', [], []], ['e', [], []]]
root = a
right subtree = ['c', ['f', [], []], []]