【下载文档:  Python实现二叉树的常见遍历操作总结【7种方法】.txt 】

---

Python实现二叉树的常见遍历操作总结【7种方法】
本文实例讲述了Python实现二叉树的常见遍历操作。分享给大家供大家参考，具体如下：
二叉树的定义：
class TreeNode:
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]
二叉树的层次遍历
迭代
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相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。