完全二叉树
对一颗具有n个结点的二叉树按层进行编号，如果编号为i (1 <= i <= n)的结点与同样深度的满二叉树节点编号为i的结点在二叉树中的位置完全相同，则这颗树，我们称之为完全二叉树。
先序遍历（左-中-右）：1,2,4,8,9,5,3,6,7
中序遍历（中-左-右）：8,4,9,2,5,1,6,3,7
后序遍历（左-右-中）：8,9,4,5,2,6,7,3,1
层次遍历（宽度优先遍历）：利用队列，依次将根，左子树，右子树存入队列，按照队列的先进先出规则来实现层次遍历。1,2,3,4,5,6,7,8,9
深度优先遍历：利用栈，先将根入栈，再将根出栈，并将根的右子树，左子树存入栈，按照栈的先进后出规则来实现深度优先遍历。1,2,4,8,9,5,3,6,7
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def preTraverse(root):
‘‘‘
前序遍历
‘‘‘
if root==None:
return
print(root.value)
preTraverse(root.left)
preTraverse(root.right)
def midTraverse(root):
‘‘‘
中序遍历
‘‘‘
if root==None:
return
midTraverse(root.left)
print(root.value)
midTraverse(root.right)
def afterTraverse(root):
‘‘‘
后序遍历
‘‘‘
if root==None:
return
afterTraverse(root.left)
afterTraverse(root.right)
print(root.value)
if __name__==‘__main__‘:
root=Node(‘D‘,Node(‘B‘,Node(‘A‘),Node(‘C‘)),Node(‘E‘,right=Node(‘G‘,Node(‘F‘))))
print(‘前序遍历：‘)
preTraverse(root)
print(‘\n‘)
print(‘中序遍历：‘)
midTraverse(root)
print(‘\n‘)
print(‘后序遍历：‘)
afterTraverse(root)
print(‘\n‘)
广度优先（队列，先进先出）
def BFS(self, root):
‘‘‘广度优先‘‘‘
if root == None:
return
# queue队列，保存节点
queue = []
# res保存节点值，作为结果
#vals = []
queue.append(root)
while queue:
# 拿出队首节点
currentNode = queue.pop(0)
#vals.append(currentNode.val)
print(currentNode.val, end=‘ ‘)
if currentNode.left:
queue.append(currentNode.left)
if currentNode.right:
queue.append(currentNode.right)
#return vals
深度优先（栈，后进先出）
def DFS(self, root):
‘‘‘深度优先‘‘‘
if root == None:
return
# 栈用来保存未访问节点
stack = []
# vals保存节点值，作为结果
#vals = []
stack.append(root)
while stack:
# 拿出栈顶节点
currentNode = stack.pop()
#vals.append(currentNode.val)
print(currentNode.val, end=‘ ‘)
if currentNode.right:
stack.append(currentNode.right)
if currentNode.left:
stack.append(currentNode.left)
#return vals
原文：https://www.cnblogs.com/iupoint/p/11578052.html