最近在复习二叉树的相关内容,这里将二叉树的三种常规遍历的递归形式和非递归形式总结一下。
三种遍历的规则如下:
- 前序遍历:根节点->左⼦树->右⼦树
- 中序遍历:左⼦树->根节点->右⼦树
- 后序遍历:左⼦树->右⼦树->根节点
可以看到:前序、中序、后序均是针对根节点而言,另外左子树总数先于右子树。
构建二叉树
class BinaryTree:
def __init__(self):
self.root = None
def _add(self, item):
"""广度优先遍历方式添加节点"""
if self.root is None:
self.root = Node(item)
else:
queue = list()
queue.append(self.root)
while len(queue) > 0:
node = queue.pop(0)
if not node.left:
node.left = Node(item)
return
else:
queue.append(node.left)
if not node.right:
node.right = Node(item)
return
else:
queue.append(node.right)
@property
def header(self):
return self.root
def add(self,arr):
for i in arr:
self._add(i)
本文构造如下二叉树:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
前序遍历
def preoder(root):
stack = []
outlist = []
while stack or root:
while root:
outlist.append(root.val)
stack.append(root)
root = root.left
root = stack.pop()
root = root.right
return outlist
验证:
# 构建二叉树
arr = [1,2,3,4,5,6,7,8,9]
tree = BinaryTree()
tree.add(arr)
# 前序遍历
print(preoder(tree.header))
输出:
[1, 2, 4, 8, 9, 5, 3, 6, 7]
中序遍历
def inorder(root):
stack = []
outlist = []
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
outlist.append(root.val)
root = root.right
return outlist
验证:
# 构建二叉树
arr = [1,2,3,4,5,6,7,8,9]
tree = BinaryTree()
tree.add(arr)
# 中序遍历
print(inorder(tree.header))
输出:
[8, 4, 9, 2, 5, 1, 6, 3, 7]
后序遍历
def postorder(root):
stack = []
outlist = []
while stack or root:
while root:
stack.append(root)
root = root.left if root.left else root.right
root = stack.pop()
outlist.append(root.val)
if stack and stack[-1].left == root:
root = stack[-1].right
else:
root = None
return outlist
验证:
# 构建二叉树
arr = [1,2,3,4,5,6,7,8,9]
tree = BinaryTree()
tree.add(arr)
# 后序遍历
print(postorder(tree.header))
输出:
[8, 9, 4, 5, 2, 6, 7, 3, 1]