最近在看算法，看到经典的二叉树，可是在C#和objective-v中可以用结构体来表示，那么在Python中怎么表示啊？要用什么数据结构呢？

打开百度一搜，果然一大堆，下面是提取并补充的一些知识点。

用嵌套字典表示二叉树

image.png

比如上图中的二叉树就可以用字典这样表示：
tree = ['A',
['B',
['D', [ ], [ ] ],
['E', [ ], [ ] ] ],
['C',
['F', [ ], [ ] ],
[ ] ]
]
这样看很难看是吧？我画了张草图，希望能帮助你看懂。

image.png
image.png

也不知道你看明白了没有，随缘吧。

构建二叉树

知道了二叉树的结构之后我们要构造和上面一样的一个二叉树。代码如下：

# 构建父节点，返回tree。字典的结构是[父节点，左节点，右节点]
def binaryTree(item):
    return [item, [], []]

# 插入左边子节点
def insertLeft(tree, item):
    leftSubTree = tree.pop(1)
    if leftSubTree:
        tree.insert(1, [item, leftSubTree, []])
    else:
        tree.insert(1, [item, [], []])
    return tree

# 插入右边子节点
def insertRight(tree, item):
    rightSubTree = tree.pop(2)
    if rightSubTree:
        tree.insert(2, [item, [], rightSubTree])
    else:
        tree.insert(2, [item, [], []])
    return tree

# 获取左节点
def getLeftChild(tree):
    return tree[1]

# 获取右节点
def getRightChild(tree):
    return tree[2]

# 开始构造树
tree = binaryTree('A')
insertLeft(tree, 'B')
insertRight(tree, 'C')
insertLeft(getLeftChild(tree), 'D')
insertRight(getLeftChild(tree), 'E')
insertLeft(getRightChild(tree), 'F')

print(tree)

打印结果如图：

image.png

困了，睡觉，明天睡醒了继续更新。实现二叉树类，以及先序，中序，后序遍历。

支持原创，参考博客：

Python数据结构——二叉树的实现