二叉树的深度优先遍历
二叉树的深度优先遍历
- 先序遍历:根左右
- 中序遍历:左根右
- 后序遍历:左右根
代码实现(完全二叉树)
class Node(object):
"""节点类"""
def __init__(self, item):
self.item = item
self.lchild = None
self.rchild = None
class BinaryTree(object):
"""完全二叉树"""
def __init__(self, node=None):
self.root = node
def add(self, item):
"""添加节点"""
if self.root == None:
self.root = Node(item)
return
# 队列
queue = []
# 从尾部添加数据
queue.append(self.root)
while True:
# 从头部取出数据
node = queue.pop(0)
# 判断左节点是否为空
if node.lchild == None:
node.lchild = Node(item)
return
else:
queue.append(node.lchild)
if node.rchild == None:
node.rchild = Node(item)
return
else:
queue.append(node.rchild)
def preorder_travel(self, root):
"""先序遍历 根 左 右"""
if root is not None:
print(root.item, end="")
self.preorder_travel(root.lchild)
self.preorder_travel(root.rchild)
def inorder_travel(self, root):
"""中序遍历 左根右"""
if root is not None:
self.inorder_travel(root.lchild)
print(root.item, end="")
self.inorder_travel(root.rchild)
def postorder_travel(self, root):
"""后序遍历 左右根"""
if root is not None:
self.postorder_travel(root.lchild)
self.postorder_travel(root.rchild)
print(root.item, end="")
if __name__ == '__main__':
tree = BinaryTree()
tree.add("0")
tree.add("1")
tree.add("2")
tree.add("3")
tree.add("4")
tree.add("5")
tree.add("6")
tree.add("7")
tree.add("8")
tree.add("9")
tree.preorder_travel(tree.root)
print()
tree.inorder_travel(tree.root)
print()
tree.postorder_travel(tree.root)
由遍历结果反推二叉树的结构
知道中序遍历和先序遍历或者后序遍历就可以推出二叉树的结构。