问题描述

请递归实现二叉树的先序遍历，中序遍历，后序遍历和层次遍历。

二叉树结构：

二叉树先序遍历

代码实现

''' 实现二叉树的结构，树的节点有三个私有属性:左指针，右指针和值'''class Node: def __init__(self, value=None, left=None, right=None): self._value = value # 在变量前加'_'表示私有属性 self._left = left self._right = right# 先序遍历 遍历过程:根节点，左节点，右节点def pro_order(tree): if tree == None: return False print(tree._value,end=' ') pro_order(tree._left) pro_order(tree._right)# 中序遍历 遍历过程:左节点，根节点，右节点def mid_order(tree): if tree == None: return False mid_order(tree._left) print(tree._value,end=' ') mid_order(tree._right)# 后续遍历 遍历过程:左节点,右节点,根节点def pos_order(tree): if tree == None: return False pos_order(tree._left) pos_order(tree._right) print(tree._value,end=' ')# 层次遍历def row_order(tree): queue = [] queue.append(tree) while True: if queue == []: break print(queue[0]._value,end=' ') first_tree = queue[0] if first_tree._left != None: queue.append(first_tree._left) if first_tree._right != None: queue.append(first_tree._right) queue.remove(first_tree)if __name__ == '__main__': tree = Node('A', Node('B', Node('D'), Node('E')), Node('C', Node('F'), Node('G'))) print('先序遍历:') pro_order(tree) print() print('中序遍历:') mid_order(tree) print() print('后序遍历:') pos_order(tree) print() print('层次遍历:') row_order(tree)

运行结果

先序遍历:A B D E C F G 中序遍历:D B E A F C G 后序遍历:D E B F G C A 层次遍历:A B C D E F G