Python 下的数据结构实现

参考《Python 算法教程》《数据结构与算法 —— Python 语言描述》；

1. 用 Python 的 list 实现树形结构

二叉树是递归结构，或者说二叉树是通过递归定义的（二叉树的左右子树还是二叉树），而 Python 的 list 也是递归结构。基于 list 类型很容易实现二叉树，例如，可以采用下面的设计：

• 空树（比如当左子树或右子树为空时）用 None 表示
• 非空二叉树用包含三元素的表[d, l, r]表示，
  
  • d表示存在根节点的元素
  • l和r是两棵子树，采用与整个二叉树同样结构的 list 表示；

tree = ['A',    ['B', None, None],

                ['C',   ['D',   ['F', None, None],

                                ['G', None, None]],

                        ['E',   ['I', None, None],

                                ['H', None, None]]

                 ]]