第一部分
手动二叉树的构建
【《面试》---Python 实现二叉树结构以及相关遍历】构建二叉树
a
b c
d f e
实际上是一个list
[a,[b,[d,[],[]],[f,[],[]]],[c,[],[e,[],[]]]]
# 构建根节点
def BinaryTree(item):
return [item,[],[]]# 访问左右子数
def getLeftChild(tree):
return tree[1]
def getRightChild(tree):
return tree[2]# 插入左子树
def insertLeft(tree,item):
leftSubtree = tree.pop(1)
# pop() 函数是 对原list去掉这个值，但是这个可以理解为取值
if leftSubtree:
# 如果原左子树节点存在的话，则插入节点，原节点，[]
tree.insert(1,[item,leftSubtree,[]])
else:
# 如果原左子树节点不存在的话，直接把节点当做节点插入 item,[],[]
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#根节点
tree=BinaryTree('a')
# 第一层
insertLeft(tree,'b')
insertRight(tree,'c')
#第二层
insertLeft(getLeftChild(tree),'d')
insertRight(getLeftChild(tree),'e')
insertRight(getRightChild(tree),'f')
print tree
