首先是树的建立:
class TreeNode:
def __init__(self,x,left=None,right=None):
self.val=x
self.left=left
self.right=right
建立好的树如图所示:
一、递归版的遍历(很好记)
class traveral:
def __init__(self):
self.pre_res=[]
self.in_res=[]
self.post_res=[]
#先序遍历(根左右)
def preorder(self,root):
if root is None:
return None
self.pre_res.append(root.val)
self.preorder(root.left)
self.preorder(root.right)
#中序遍历(左根右)
def inorder(self,root):
if root is None:
return None
self.inorder(root.left)
self.in_res.append(root.val)
self.inorder(root.right)
#后序遍历(左右根)
def postorder(self,root):
if root is None:
return None
self.postorder(root.left)
self.postorder(root.right)
self.post_res.append(root.val)
tra=traveral()
tra.preorder(root)
tra.inorder(root)
tra.postorder(root)
print(tra.pre_res)
print(tra.in_res)
print(tra.post_res)
输出:
二、非递归版本
class non_recursive:
def preorder(self,root):
stack=[]
pre_res=[]
while root or stack:
while root:
pre_res.append(root.val)
stack.append(root)
root=root.left
if stack:
t=stack.pop()
root=t.right
return pre_res
def inorder(self,root):
stack=[]
in_res=[]
while stack or root:
while root:
stack.append(root)
root=root.left
if stack:
t=stack.pop()
in_res.append(t.val)
root=t.right
return in_res
def postorder(self,root):
stack1=[]
stack2=[]
post_res=[]
stack1.append(root)
while stack1:
t=stack1.pop()
if t.left:
stack1.append(t.left)
if t.right:
stack1.append(t.right)
stack2.append(t)
while stack2:
post_res.append(stack2.pop().val)
return post_res
def levelorder(self,root):
queue=[root]
level_res=[]
while queue:
t=[]
for i in range(len(queue)):
cur=queue.pop(0)
t.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
level_res.append(t)
return level_res
nonre=non_recursive()
print(nonre.preorder(root))
print(nonre.inorder(root))
print(nonre.postorder(root))
print(nonre.levelorder(root))
输出: