今天给大家分享： python 实现 二叉树 的常见遍历操作

二叉树的定义

class Tree node :
 def __init__(self, x):
 self.val = x
 self.left = None
 self.right = None
 

二叉树的 前序遍历

递归

def preorder(root,res=[]):
 if not root:
 return
 res.append(root.val)
 preorder(root.left,res)
 preorder(root.right,res)
 return res
 

迭代

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
 

二叉树的 中序遍历

递归

def inorder(root,res=[]):
 if not root:
 return
 inorder(root.left,res)
 res.append(root.val)
 inorder(root.right,res)
 return res
 

迭代

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
 

二叉树的 后序遍历

递归

def laorder(root,res=[]):
 if not root:
 return
 laorder(root.left,res)
 laorder(root.right,res)
 res.append(root.val)
 return res
 

迭代

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]
 

二叉树的层次遍历

迭代

最后多说一句，小编是一名python开发工程师，这里有我自己整理了一套最新的python系统学习教程，包括从基础的python脚本到web开发、 爬虫 、数据分析、数据可视化、机器学习等。想要这些资料的可以关注小编，并在后台私信小编：“01”即可领取。