Python实现二叉树的常见遍历操作总结【7种方法】
本文实例讲述了Python实现二叉树的常见遍历操作。分享给大家供大家参考,具体如下:
二叉树的定义:
classTreeNode: def__init__(self,x): self.val=x self.left=None self.right=None
二叉树的前序遍历
递归
defpreorder(root,res=[]): ifnotroot: return res.append(root.val) preorder(root.left,res) preorder(root.right,res) returnres
迭代
defpreorder(root): res=[] ifnotroot: return[] stack=[root] whilestack: node=stack.pop() res.append(node.val) ifnode.right: stack.append(node.right) ifnode.left: stack.append(node,left) returnres
二叉树的中序遍历
递归
definorder(root,res=[]): ifnotroot: return inorder(root.left,res) res.append(root.val) inorder(root.right,res) returnres
迭代
definorder(root): stack=[] node=root res=[] whilestackornode: whilenode: stack.append(node) node=node.left node=stack.pop() res.append(node.val) node=node.right returnres
二叉树的后序遍历
递归
deflaorder(root,res=[]): ifnotroot: return laorder(root.left,res) laorder(root.right,res) res.append(root.val) returnres
迭代
deflaorder(root): stack=[root] res=[] whilestack: node=stack.pop() ifnode.left: stack.append(node.left) ifnode.right: stack.append(node.right) res.append(node.val) returnres[::-1]
二叉树的层次遍历
迭代
deflevelorder(root): queue=[root] res=[] whilequeue: node=queue.pop(0) ifnode.left: queue.append(node.left) ifnode.right: queue.append(node.right) res.append(node.val) returnres
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。