首先是三种遍历的递归实现，思路简单，重要的是要清楚每种遍历的顺序：
- 先序遍历： 根 --》 左子树 --》右子树
- 中序遍历： 左子树 --》根--》右子树
- 后序遍历： 左子树 --》右子树 --》根
首先是树的创建：
image.png
class binaryTree:
def __init__(self, root):
self.key = root
self.left_child = None
self.right_child = None
def insert_left(self, new_node):
if self.left_child == None:
self.left_child = binaryTree(new_node)
else:
t = binaryTree(new_node)
t.left_child = self.left_child
self.left_child = t
def insert_right(self, new_code):
if self.right_child == None:
self.right_child = binaryTree(new_code)
else:
t = binaryTree(new_code)
t.right_child = self.right_child
self.right_child = t
def get_right_child(self):
return self.right_child
def get_left_child(self):
return self.left_child
def set_root_val(self, obj):
self.key = obj
def get_root_val(self):
return self.key
递归方法：
def preOrder(root):
if root == None:
return
print root.key,
preOrder(root.left_child)
preOrder(root.right_child)
def inOrder(root):
if root == None:
return
inOrder(root.left_child)
print root.key,
inOrder(root.right_child)
def postOrder(root):
if root == None:
return
postOrder(root.left_child)
postOrder(root.right_child)
print root.key,
层次遍历：
def cengci(root):
if root == None:
return
stack = []
stack.append(root)
while len(stack):
p = stack[0]
print p.key ,
del stack[0]
if p.left_child:
stack.append(p.left_child)
if p.right_child:
stack.append(p.right_child)
测试：
if __name__ == "__main__":
r = binaryTree('a')
r.insert_left('b')
r.insert_right('c')
l = r.left_child
l.insert_left("d")
l.insert_right("e")
ri = r.right_child
ri.insert_left("f")
ri.insert_right("g")
print "pre: "
preOrder(r)
print "\n"
print "in: "
inOrder(r)
print "\n"
print "post: "
postOrder(r)
image.png
非递归方法：
- 先序遍历：
当p或者栈不为空时循环，为什么是这个条件（p很可能为None,但如果此时还能回溯的时候，程序就可以继续），首先一直压入左节点，（对应根节点）并且输出当前节点，当直到最左的时候，回溯（对应pop操作），考虑右节点
def preOrder1(root):
if root == None:
return
p = root
stack = []
while p != None or len(stack):
while p != None:
print p.key,
stack.append(p)
p = p.left_child
if len(stack):
p = stack[-1]
del stack[-1]
p = p.right_child
- 中序遍历，和前序遍历有点像，但是因为根是在中间遍历，所以要在出栈时候输出（相当于根节点被压栈了），最后考虑右节点
def inOrder1(root):
if root == None:
return
p = root
stack = []
while p != None or len(stack):
while p != None:
stack.append(p)
p = p.left_child
if len(stack):
p = stack[-1]
print p.key,
del stack[-1]
p = p.right_child
- 后序遍历：
左--》右--》根
当左节点和右节点不存在时，可以访问根节点，或者左节点或者右节点已经访问过的时候。
然后先压栈右节点，然后左节点，这样输出的时候先左节点，后右节点
def postOrder1(root):
if root == None:
return
p = root
stack = []
stack.append(p)
pre = None
while len(stack):
cur = stack[-1]
if (cur.left_child == None and cur.right_child == None) or (pre!=None and (pre == cur.left_child or pre == cur.right_child)):
print cur.key,
del stack[-1]
pre = cur
else:
if cur.right_child != None:
stack.append(cur.right_child)
if cur.left_child != None:
stack.append(cur.left_child)
image.png
