python递归深度遍历多叉树（Python实现二叉树的常见遍历操作总结7种方法）

python递归深度遍历多叉树

Python实现二叉树的常见遍历操作总结7种方法

本文实例讲述了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