#3904. 【模板】二叉树的遍历

【模板】二叉树的遍历

题目描述

实现二叉树的层次遍历、先序遍历、中序遍历、后序遍历。

输入格式

第一行输入一个数 nn,第二行输入 nn 个以空格分隔的数,使用层次建树将其建立为一棵链式存储的二叉树。

输出格式

共三行,分别输出二叉树的层次遍历、先序遍历、中序遍历、后序遍历,元素间使用空格分隔。

样例

10
2022 301 15 1207 2048 698 2 475 520 606
2022 301 15 1207 2048 698 2 475 520 606 
2022 301 1207 475 520 2048 606 15 698 2 
475 1207 520 301 606 2048 2022 698 15 2 
475 520 1207 606 2048 301 698 2 15 2022

示例代码

  1. Python3Python3
# Author: guke

class Node(object):

    def __init__(self, item):
        self.elem = item
        self.lchild = None
        self.rchild = None


class Tree(object):

    def __init__(self):
        self.root = None

    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

    def breadth_travel(self):
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem, end=" ")
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

    def preorder(self, node):
        if node is None:
            return
        print(node.elem, end=" ")
        self.preorder(node.lchild)
        self.preorder(node.rchild)

    def inorder(self, node):
        if node is None:
            return
        self.inorder(node.lchild)
        print(node.elem, end=" ")
        self.inorder(node.rchild)

    def postorder(self, node):
        if node is None:
            return
        self.postorder(node.lchild)
        self.postorder(node.rchild)
        print(node.elem, end=" ")

if __name__ == "__main__":
    tree = Tree()
    n = int(input())
    li = [int(_) for _ in input().split()]
    for _ in range(n):
        tree.add(li[_])
    tree.breadth_travel()
    print()
    tree.preorder(tree.root)
    print()
    tree.inorder(tree.root)
    print()
    tree.postorder(tree.root)
    print()