## 沐瑶 / LearningNotes

forked from / LearningNotes
Explore and code with more than 6 million developers，Free private repositories ！：）

# 树的遍历

## 构建一个二叉树

class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None

if __name__ == '__main__':
t1 = TreeNode(1)
t2 = TreeNode(2)
t3 = TreeNode(3)
t4 = TreeNode(4)
t5 = TreeNode(5)
t6 = TreeNode(6)
t7 = TreeNode(7)
t8 = TreeNode(8)
t1.left = t2
t1.right = t3
t2.left = t4
t2.right = t5
t3.left = t6
t3.right = t7
t6.right = t8

## 递归遍历

class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None

# 递归先序遍历
def preOrderRecusive(root):
if root == None:
return None
print(root.val, end=" ")
preOrderRecusive(root.left)
preOrderRecusive(root.right)

# 递归中序遍历
def midOrderRecusive(root):
if root == None:
return None
midOrderRecusive(root.left)
print(root.val, end=" ")
midOrderRecusive(root.right)

# 递归后序遍历
def latOrderRecusive(root):
if root == None:
return None
latOrderRecusive(root.left)
latOrderRecusive(root.right)
print(root.val, end=" ")

if __name__ == '__main__':
t1 = TreeNode(1)
t2 = TreeNode(2)
t3 = TreeNode(3)
t4 = TreeNode(4)
t5 = TreeNode(5)
t6 = TreeNode(6)
t7 = TreeNode(7)
t8 = TreeNode(8)
t1.left = t2
t1.right = t3
t2.left = t4
t2.right = t5
t3.left = t6
t3.right = t7
t6.right = t8

preOrderRecusive(t1)
print()
midOrderRecusive(t1)
print()
latOrderRecusive(t1)

1 2 4 5 3 6 8 7
4 2 5 1 8 6 3 7
4 5 2 8 6 7 3 1 

## 非递归遍历

# 非递归先序遍历
def preOrder(root):
if root == None:
return None
stack = []
tempNode = root
while tempNode != None or stack:
print(tempNode.val, end=" ")
stack.append(tempNode)
tempNode = tempNode.left
while tempNode == None and stack != None:
tempNode = stack.pop()
tempNode = tempNode.right
# 非递归中序遍历
def midOrder(root):
if root == None:
return None
stack = []
tempNode = root
while tempNode != None or stack:
stack.append(tempNode)
tempNode = tempNode.left
while tempNode == None and stack != []:
tempNode = stack.pop()
print(tempNode.val, end=" ")
tempNode = tempNode.right
# 非递归后序遍历
def latOrder(root):
if root == None:
return None
stack = []
tempNode = root
while tempNode != None or stack:
stack.append(tempNode)
tempNode = tempNode.left
while tempNode == None and stack != []:
# 后序遍历，pop的方式有变化，不能在右子树不为空的时候pop
node = stack[-1] # 因此这里不出列
tempNode = node.right
# 当右节点没有的时候，才能够pop
if node.right == None:
print(node.val, end=" ")
node = stack.pop()
# 判断pop的节点，是否是上一个节点
while stack and node == stack[-1].right:
node = stack.pop()
print(node.val, end=" ")