二叉树的深度优先遍历以及广度优先遍历实现
程序员文章站
2022-05-21 19:28:59
...
深度遍历分为先序遍历,中序遍历,以及后序遍历;而深度遍历的方式又分为递归深度遍历和栈深度遍历。
广度优先遍历是层序遍历:
#!/usr/bin/env python
#coding:utf-8
class TreeNode(object):
def __init__(self):
self.data = '#'
self.lchild = None
self.rchild = None
class Tree(TreeNode):
def __init__(self):
self.root = TreeNode()
self.myQueue = []
#Create a tree
def create_tree(self,tree):
data = raw_input('->')
if data == '#':
tree = None
else:
tree.data = data
tree.lchild = TreeNode()
self.create_tree(tree.lchild)
tree.rchild = TreeNode()
self.create_tree(tree.rchild)
def visit(self,tree):
#输入#代表空树
if tree.data is not '#':
print str(tree.data)+'\t'
def pre_order(self,tree):
if tree is not None:
self.visit(tree)
self.pre_order(tree.lchild)
self.pre_order(tree.rchild)
def in_order(self,tree):
if tree is not None:
self.in_order(tree.lchild)
self.visit(tree)
self.in_order(tree.rchild)
def post_order(self,tree):
if tree is not None:
self.post_order(tree.lchild)
self.post_order(tree.rchild)
self.visit(tree)
def pre_stack(self,tree):
if tree == None:
return
myStack = []
none = tree
while node or myStack:
while node:
print node.data
myStack.append(node)
node = node.lchild
node = myStack.pop()
node = node.rchild
def in_stack(self,tree):
if tree == None:
return
myStack = []
node = tree
while node or myStack:
myStack.append(node)
node=node.lchild
node=myStack.pop()
print node.data
node=node.rchild
def post_stack(self,tree):
if tree == None:
return
myStack1 = []
myStack2 = []
node=tree
myStack1.append(node)
while myStack1:
node = myStack1.pop()
if node.lchild:
myStack1.append(node.lchild)
if node.rchild:
myStack1.append(node.rchild)
myStack2.append(node)
while myStack2:
print myStack2.pop().data
def level_order(self,tree):
if tree == None:
return
myQueue = []
node = tree
myQueue.append(node)
while myQueue:
node=myQueue.pop(0)
print node.data
if node.lchild:
myQueue.append(node.lchild)
if node.rchild:
myQueue.append(node.rchild)