image.png
    树的遍历主要有两种，
    一种是深度优先遍历，像前序、中序、后序；
    另一种是广度优先遍历，像层次遍历。
    在树结构中两者的区别还不是非常明显，但从树扩展到有向图，到无向图的时候，深度优先搜索和广度优先搜索的效率和作用还是有很大不同的。
    深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。
    Python实现功能：

    • 树的构造
    • 递归实现先序遍历、中序遍历、后序遍历
    • 堆栈实现先序遍历、中序遍历、后序遍历
    • 队列实现层次遍历
    1. class Node(object):
    2.     """节点类"""
    3.     def __init__(self, elem=-1, lchild=None, rchild=None):
    4.         self.elem = elem
    5.         self.lchild = lchild
    6.         self.rchild = rchild
    8. class Tree(object):
    9.     """树类"""
    11.     def __init__(self):
    12.         self.root = Node()
    13.         self.myQueue = []
    15.     def add(self, elem):
    16.         """为树添加节点"""
    17.         node = Node(elem)
    18.         if self.root.elem == -1:  # 如果树是空的，则对根节点赋值
    19.             self.root = node
    20.             self.myQueue.append(self.root)
    21.         else:
    22.             treeNode = self.myQueue[0]  # 此结点的子树还没有齐。
    23.             if treeNode.lchild == None:
    24.                 treeNode.lchild = node
    25.                 self.myQueue.append(treeNode.lchild)
    26.             else:
    27.                 treeNode.rchild = node
    28.                 self.myQueue.append(treeNode.rchild)
    29.                 self.myQueue.pop(0)  # 如果该结点存在右子树，将此结点丢弃。
    31.     def front_digui(self, root):
    32.         """利用递归实现树的先序遍历"""
    33.         if root == None:
    34.             return
    35.         print(root.elem)
    36.         self.front_digui(root.lchild)
    37.         self.front_digui(root.rchild)
    39.     def middle_digui(self, root):
    40.         """利用递归实现树的中序遍历"""
    41.         if root == None:
    42.             return
    43.         self.middle_digui(root.lchild)
    44.         print(root.elem)
    45.         self.middle_digui(root.rchild)
    47.     def later_digui(self, root):
    48.         """利用递归实现树的后序遍历"""
    49.         if root == None:
    50.             return
    51.         self.later_digui(root.lchild)
    52.         self.later_digui(root.rchild)
    53.         print(root.elem)
    55.     def front_stack(self, root):
    56.         """利用堆栈实现树的先序遍历"""
    57.         if root == None:
    58.             return
    59.         myStack = []
    60.         node = root
    61.         while node or myStack:
    62.             while node:  # 从根节点开始，一直找它的左子树
    63.                 print(node.elem)
    64.                 myStack.append(node)
    65.                 node = node.lchild
    66.             node = myStack.pop()  # while结束表示当前节点node为空，即前一个节点没有左子树了
    67.             node = node.rchild  # 开始查看它的右子树
    69.     def middle_stack(self, root):
    70.         """利用堆栈实现树的中序遍历"""
    71.         if root == None:
    72.             return
    73.         myStack = []
    74.         node = root
    75.         while node or myStack:
    76.             while node:  # 从根节点开始，一直找它的左子树
    77.                 myStack.append(node)
    78.                 node = node.lchild
    79.             node = myStack.pop()  # while结束表示当前节点node为空，即前一个节点没有左子树了
    80.             print(node.elem)
    81.             node = node.rchild  # 开始查看它的右子树
    83.     def later_stack(self, root):
    84.         """利用堆栈实现树的后序遍历"""
    85.         if root == None:
    86.             return
    87.         myStack1 = []
    88.         myStack2 = []
    89.         node = root
    90.         myStack1.append(node)
    91.         while myStack1:  # 这个while循环的功能是找出后序遍历的逆序，存在myStack2里面
    92.             node = myStack1.pop()
    93.             if node.lchild:
    94.                 myStack1.append(node.lchild)
    95.             if node.rchild:
    96.                 myStack1.append(node.rchild)
    97.             myStack2.append(node)
    98.         while myStack2:  # 将myStack2中的元素出栈，即为后序遍历次序
    99.             print(myStack2.pop().elem)
    101.     def level_queue(self, root):
    102.         """利用队列实现树的层次遍历"""
    103.         if root == None:
    104.             return
    105.         myQueue = []
    106.         node = root
    107.         myQueue.append(node)
    108.         while myQueue:
    109.             node = myQueue.pop(0)
    110.             print(node.elem)
    111.             if node.lchild != None:
    112.                 myQueue.append(node.lchild)
    113.             if node.rchild != None:
    114.                 myQueue.append(node.rchild)
    117. if __name__ == '__main__':
    118.     """主函数"""
    119.     elems = range(10)  # 生成十个数据作为树节点
    120.     tree = Tree()  # 新建一个树对象
    121.     for elem in elems:
    122.         tree.add(elem)  # 逐个添加树的节点
    124.     print('队列实现层次遍历:')
    125.     tree.level_queue(tree.root)
    127.     print('\n\n递归实现先序遍历:')
    128.     tree.front_digui(tree.root)
    129.     print('\n递归实现中序遍历:')
    130.     tree.middle_digui(tree.root)
    131.     print('\n递归实现后序遍历:')
    132.     tree.later_digui(tree.root)
    134.     print('\n\n堆栈实现先序遍历:')
    135.     tree.front_stack(tree.root)
    136.     print('\n堆栈实现中序遍历:')
    137.     tree.middle_stack(tree.root)
    138.     print('\n堆栈实现后序遍历:')
    139.     tree.later_stack(tree.root)