二叉树遍历-前序|中序|后序|层次 python实现
1、概念
四种遍历的基本思想：
前序遍历：根结点 ---> 左子树 ---> 右子树
中序遍历：左子树 ---> 根结点 ---> 右子树
后序遍历：左子树 ---> 右子树 ---> 根结点
层次遍历：从根结点开始，从左到右，按层次遍历就可以
2、四种遍历示例
前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
层次遍历：1 2 3 4 5 6 7 8
3、python实现
class BinaryTree:
def __init__(self,root):
self.val = root
self.left = None
self.right = None
def insertLeft(self, newNode):
if self.left == None:
self.left = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.left = self.left
self.left = t
def insertRight(self, newNode):
if self.right == None:
self.right = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.right = self.right
self.right = t
# 前序遍历
def PreOrder(self, node):
if node:
print(node.val)
self.PreOrder(node.left)
self.PreOrder(node.right)
# 中序遍历
def InOrder(self, node):
if node:
self.InOrder(node.left)
print(node.val)
self.InOrder(node.right)
# 后序遍历
def PostOrder(self, node):
if node:
self.PostOrder(node.left)
self.PostOrder(node.right)
print(node.val)
# 层次遍历
def LevelOrder(self, node):
if node == None:
return
stack = []
stack.append(node)
while stack!=[]:
node = stack[0]
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
print(node.val)
stack.pop(0)
代码示例：
root = BinaryTree(18)
root.left = BinaryTree(7)
root.right = BinaryTree(11)
root.left.left = BinaryTree(3)
root.left.right = BinaryTree(4)
root.right.left = BinaryTree(5)
root.right.right = BinaryTree(6)
root.right.left.left = BinaryTree(1)
root.right.left.right = BinaryTree(3)
root.right.right.left = BinaryTree(2)
root.right.right.right = BinaryTree(4)
前序遍历：ouput: 18 7 3 4 11 5 1 3 6 2 4
中序遍历：output：3 7 4 18 1 5 3 11 2 6 4
后序遍历：output:3 4 7 1 3 5 2 4 6 11 18
层次遍历：output: 18 7 11 3 4 5 6 1 3 2 4
备注：原文出处 https://blog.csdn.net/Rai_Code/article/details/100006080