实现二叉树的各种遍历算法 目的：领会二叉树的各种遍历过程及遍历算法设计。 内容：编写一个程序exp6-2.py， 实现二叉树的先序遍历、中序遍历和后序遍历的递归和非递归算法，以及层次遍历算法，并对图7.33所示的二叉树b给出求解结果。

以下是exp6-2.py的代码实现：

# 定义二叉树节点类
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 先序遍历递归算法
def pre_order_recursive(node):
    if node is not None:
        print(node.value, end=' ')
        pre_order_recursive(node.left)
        pre_order_recursive(node.right)

# 中序遍历递归算法
def in_order_recursive(node):
    if node is not None:
        in_order_recursive(node.left)
        print(node.value, end=' ')
        in_order_recursive(node.right)

# 后序遍历递归算法
def post_order_recursive(node):
    if node is not None:
        post_order_recursive(node.left)
        post_order_recursive(node.right)
        print(node.value, end=' ')

# 先序遍历非递归算法
def pre_order_non_recursive(node):
    stack = []
    while node is not None or len(stack) != 0:
        while node is not None:
            print(node.value, end=' ')
            stack.append(node)
            node = node.left
        if len(stack) != 0:
            node = stack.pop()
            node = node.right

# 中序遍历非递归算法
def in_order_non_recursive(node):
    stack = []
    while node is not None or len(stack) != 0:
        while node is not None:
            stack.append(node)
            node = node.left
        if len(stack) != 0:
            node = stack.pop()
            print(node.value, end=' ')
            node = node.right

# 后序遍历非递归算法
def post_order_non_recursive(node):
    stack1 = []
    stack2 = []
    while node is not None or len(stack1) != 0:
        while node is not None:
            stack1.append(node)
            stack2.append(False)
            node = node.left
        if len(stack1) != 0:
            if stack2[-1] is False:
                stack2[-1] = True
                node = stack1[-1].right
            else:
                print(stack1.pop().value, end=' ')
                stack2.pop()
                node = None

# 层次遍历算法
def level_order(node):
    queue = []
    if node is not None:
        queue.append(node)
    while len(queue) != 0:
        node = queue.pop(0)
        print(node.value, end=' ')
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)

# 构建二叉树b
a = Node('A')
b = Node('B')
c = Node('C')
d = Node('D')
e = Node('E')
f = Node('F')
g = Node('G')
h = Node('H')
i = Node('I')
j = Node('J')
k = Node('K')
a.left, a.right = b, c
b.left, b.right = d, e
c.left, c.right = f, g
d.left, d.right = None, None
e.left, e.right = h, i
f.left, f.right = j, k
g.left, g.right = None, None
h.left, h.right = None, None
i.left, i.right = None, None
j.left, j.right = None, None
k.left, k.right = None, None

print('先序遍历递归算法：', end='')
pre_order_recursive(a)
print()
print('中序遍历递归算法：', end='')
in_order_recursive(a)
print()
print('后序遍历递归算法：', end='')
post_order_recursive(a)
print()
print('先序遍历非递归算法：', end='')
pre_order_non_recursive(a)
print()
print('中序遍历非递归算法：', end='')
in_order_non_recursive(a)
print()
print('后序遍历非递归算法：', end='')
post_order_non_recursive(a)
print()
print('层次遍历算法：', end='')
level_order(a)
print()

输出结果如下：

先序遍历递归算法：A B D E H I C F J K G 
中序遍历递归算法：D B H E I A J F K C G 
后序遍历递归算法：D H I E B J K F G C A 
先序遍历非递归算法：A B D E H I C F J K G 
中序遍历非递归算法：D B H E I A J F K C G 
后序遍历非递归算法：D H I E B J K F G C A 
层次遍历算法：A B C D E F G H I J K