若以 D、L、R分别表示根结点、左子树、右子树，理论上来说，二叉树的遍历方式有六种，
但如果限定先左后右，则只有三种遍历方式：DLR(先序遍历)、LDR(中序遍历)、LRD(后续遍历)。
另外，还有一种特殊的遍历方式：层次遍历
A
_____/ \_____
/ \
B C
_/ \_ _/ \_
/ \ / \
D E F G
\
H
递归方式特别好实现，以下是三种遍历的递归实现：
def pre_order_recursion(node):
if not node:
return
print(node.data, end="")
pre_order_recursion(node.left_child)
pre_order_recursion(node.right_child)
def in_order_recursion(node):
if not node:
return
in_order_recursion(node.left_child)
print(node.data, end="")
in_order_recursion(node.right_child)
def post_order_recursion(node):
if not node:
return
post_order_recursion(node.left_child)
post_order_recursion(node.right_child)
print(node.data, end="")
层次遍历：ABCDEFGH
A
_____/ \_____
/ \
B C
_/ \_ _/ \_
/ \ / \
D E F G
\
H
层次遍历是一层一层进行遍历。
由于二叉树并非线性结构，倘若和线性结构一样，只依靠一个遍历指针，获取不到父结点和兄弟结点，
如：当遍历到 B，下一个应该是 C，但是要拿到 C需要先拿到 A，从这个角度看，似乎应事先准备个变量 parent_node 存储 A，
可如果遍历到E，如何拿到F呢？或者遍历G后，如何拿到H呢？显然，记录前置结点这种方式并不能解决问题。
那么应该如何进行呢？单个结点有”只能看到左右孩子“的局限性，就好像人在陌生的地方，视野有限，很容易迷路，
如何才能按照正确的路线走下去？我们需要地图或者导航。
所以接下来是怎么设计导航的问题：
已知：
1、每个结点只能看到自己和自己的两个孩子
2、孩子的访问顺序是从左往右
导航的作用是，在”迷路“时提供方向，我们会在C之后失去方向，因此导航需要告诉我们下一个是D，
那么，导航需事先把D保存好，因为在访问B时，才能获取D，所以在访问B时就应存好D
所以导航的设计要素：
1、访问到某结点时，记录下该结点的左右子结点
2、迷路时提供下一个结点
3、队列结构，先进先出
所以，我们可以设置一个队列，先把根结点A放进去，从队头中取出A，读取数据，并把两个孩子B、C放到队尾，
这样就排好了A之后的两个顺序，接下来再从队头取出B，把B的孩子放到队尾....循环进行直至队列为空了，
这样就完成一层一层遍历了
代码：
def level_order(node):
node_list = [node, ]
while node_list:
n = node_list.pop(0)
print(n.data, end="")
if n.left_child:
node_list.append(n.left_child)
if n.right_child:
node_list.append(n.right_child)
二叉树常规遍历非递归实现
非递归实现相对来说更复杂，但从层次遍历我们知道，只要建立导航就行了
A
_____/ \_____
/ \
B C
_/ \_ _/ \_
/ \ / \
D E F G
\
H
先序：ABDEHCFG
迷路的点：访问D之后，需要访问E；访问H后，需要访问C
因此，在D之后，导航需要提供B， H之后还需要提供A，不难看出，这是倒着提供，符合栈的数据结构，
所以导航的设计要素：
1、在左子树访问完毕后，提供父结点，以此访问右子树
2、记录每个结点
3、栈数据结构
def pre_order_not_recursion(node):
parent_stacks = []
while node or parent_stacks:
while node:
print(node.data, end="")
parent_stacks.append(node)
node = node.left_child
# 左孩子为空，从栈中拿出父结点，获取右孩子
# 或者 右孩子也为空，从栈中拿出上上个结点
parent_node = parent_stacks.pop()
node = parent_node.right_child
中序：DBEHAFCG
def in_order_not_recursion(node):
parent_stacks = []
while node or parent_stacks:
while node:
parent_stacks.append(node)
node = node.left_child
# 左孩子为空，从栈中获取父结点，从而获取它的右结点
# 或 右孩子为空，从栈中获取上上个结点
parent_node = parent_stacks.pop()
print(parent_node.data, end="")
node = parent_node.right_child
后序：DHEBFGCA
后序迷路的点一样，在D之后，导航需要提供B，以获得E，但因为是后序，获得E后，接下来还需要获取B，
因此，导航需要提供两次B，这里就有第一次和第二次的区别，为了区分这个，就可以设置一个计数器，
当第一次从导航中获取时，则获取右子树，并且不从栈中移除，第二次则正式读取数据并从栈中移除。
def post_order_not_recursion(node):
parent_stacks = list()
node_pop_history = dict() # 记录结点从栈中 pop 的次数，
# 若第一次 pop，则用来获取右孩子， 然后再 push 回去
# 若第二次 pop，则说明结点的 右子树都遍历完毕，开始读取该结点数据
while node or parent_stacks:
while node:
parent_stacks.append(node)
node = node.left_child
parent_node = parent_stacks[-1]
if parent_node not in node_pop_history: # 首次，获取右孩子
node = parent_node.right_child
node_pop_history[parent_node] = 1
else: # 二次，说明右子树遍历完成，读取该结点数据
parent_stacks.pop()
print(parent_node.data, end="")