本文实例讲述了Python实现二叉树的常见遍历操作。分享给大家供大家参考，具体如下：
二叉树的定义：
|
1
2
3
4
5
|
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
|
二叉树的前序遍历
递归
|
1
2
3
4
5
6
7
|
def preorder(root,res=[]):
if not root:
return
res.append(root.val)
preorder(root.left,res)
preorder(root.right,res)
return res
|
迭代
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
def preorder(root):
res=[]
if not root:
return []
stack=[root]
while stack:
node=stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node,left)
return res
|
二叉树的中序遍历
递归
|
1
2
3
4
5
6
7
|
def inorder(root,res=[]):
if not root:
return
inorder(root.left,res)
res.append(root.val)
inorder(root.right,res)
return res
|
迭代
|
1
2
3
4
5
6
7
8
9
10
11
12
|
def inorder(root):
stack=[]
node=root
res=[]
while stack or node:
while node:
stack.append(node)
node=node.left
node=stack.pop()
res.append(node.val)
node=node.right
return res
|
二叉树的后序遍历
递归
|
1
2
3
4
5
6
7
|
def laorder(root,res=[]):
if not root:
return
laorder(root.left,res)
laorder(root.right,res)
res.append(root.val)
return res
|
迭代
|
1
2
3
4
5
6
7
8
9
10
11
|
def laorder(root):
stack=[root]
res=[]
while stack:
node=stack.pop()
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
res.append(node.val)
return res[::-1]
|
二叉树的层次遍历
迭代
|
1
2
3
4
5
6
7
8
9
10
11
|
def levelorder(root):
queue=[root]
res=[]
while queue:
node=queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(node.val)
return res
|
希望本文所述对大家Python程序设计有所帮助。
原文链接：https://blog.csdn.net/wenkenza5368/article/details/79573333