基于python实现二叉树的遍历 Marathon

"""
    二叉树实践：
    用递归构建树的遍历

    # 思路分析
        -- 1.使用链式存储，一个Node表示一个数的节点
        -- 2.节点考虑使用两个属性变量，分别表示左连接右连接

"""
# 用列表存储，[d,l,r],其中d表示根节点，l/r左子树和右子树
# bitree.py 二叉树的简单实践

# 自定义异常类
class QueueError(Exception):
    pass

# 队列-顺序存储代码-入队，出队，判断空满
class SeqQueue:
    def __init__(self):
        # 创建空列表作为存储空间
        self._elems = []

    # 入队-加到最后，内存不移动
    def enqueue(self,val):
       self._elems.append(val)

    # 出队-头部删除,内存移动
    def dequeue(self):
        # 空队列，报异常
        # if not self._elems: # 如果为空，假假真
        if self._elems == []:
            raise QueueError("queue is empty")
        # 非空队列，pop出第一个元素
        return self._elems.pop(0)

    # 判断空满
    def is_empty(self):
        return self._elems == []

    # 打印队列
    def print_queue(self):
        # 先判断是否为空
        if self._elems == []:
            raise QueueError("queue is empty")
        else:
            for item in self._elems:
                print(item,end= " ")
            print()

    # 反转队列 或者用顺序栈的进出栈(出队入栈，出栈入队)方法
    def reverse_queue(self):
        """
        算法：1.设置中间列表，遍历n-1次从队列出列，值存入中间列表
            2.遍历n-1次，从中间列表倒着入列
        :return: 反转后的队列
        """
        if  self.is_empty():
            raise QueueError("queue is empty")
        middle_list = []
        len_iterator = len(self._elems)-1
        for i in range(len_iterator):
            middle_list.append(self.dequeue())
        for i in range(len_iterator):
            self.enqueue(middle_list.pop())


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

# 二叉树的操作，遍历类
class BiTree:
    def __init__(self,root = None):
        self.root = root

    # 先序遍历
    def preorder(self,node):
        if node is None: # 终止条件
            return
        print(node.val,end= " ")
        self.preorder(node.left)
        self.preorder(node.right)

    # 中序遍历
    def inorder(self,node):
        if node is None: # 终止条件
            return
        self.inorder(node.left)
        print(node.val,end= " ")
        self.inorder(node.right)

    # 后序遍历
    def postorder(self,node):
        if node is None: # 终止条件
            return
        self.postorder(node.left)
        self.postorder(node.right)
        print(node.val,end= " ")

    # 层次遍历-基于顺序队列实现
    def levelorder(self,node):
        """
        让初始节点入队，谁出队遍历谁，
        并且其左右子节点直到队列为空
        :param node:
        :return:
        """
        sq = SeqQueue()
        sq.enqueue(node)
        while not sq.is_empty():
            node = sq.dequeue()
            # 打印出队元素
            print(node.val,end=" ")
            if node.left:
                sq.enqueue(node.left)
            if node.right:
                sq.enqueue(node.right)

if __name__ == "__main__":
    # 后序 B F G D I H E C A
    b = Node("B")
    f = Node("F")
    g = Node("G")
    d = Node("D",f,g)
    i = Node("I")
    h = Node("H")
    e = Node("E",i,h)
    c = Node("C",d,e)
    a = Node("A",b,c) # 树根
    # 将a作为遍历的起始位置
    bt = BiTree(a)
    bt.preorder(a)
    print()
    bt.inorder(a)
    print()
    bt.postorder(a)
    print()
    bt.levelorder(a)