python3 二叉树遍历

淡淡的烟草味﹌ 2022-06-16 07:22 174阅读 0赞

# 二叉树遍历  （此文用来纪念今天在 你好星球 面试被技术总监吊打，哈哈，还是要注重基础啊，不能忘）
    
    # 前序遍历：根节点->左子树->右子树
    # 中序遍历：左子树->根节点->右子树
    # 后续遍历：左子树->右子树->根节点
    
    # 二叉树构建如图
    #               a
    #              / \
    #             b   c
    #            / \   \
    #           d   e   f
    #          /    /  / \
    #         g    h  i   j
    
    
    #  节点数据结构
    class Node:
        def __init__(self):
            self.father= None
            self.left= None
            self.right= None
            self.value= 0
    
    
    #  手撸二叉树 只为遍历 勿喷
    def generate_binary_tree(header):
        b = Node()
        c = Node()
        d = Node()
        e = Node()
        f = Node()
        g = Node()
        h = Node()
        i = Node()
        j = Node()
        b.value = 'b'
        c.value = 'c'
        d.value = 'd'
        e.value = 'e'
        f.value = 'f'
        g.value = 'g'
        h.value = 'h'
        i.value = 'i'
        j.value = 'j'
    
        header.left = b
        header.right = c
        b.father = header
        b.left = d
        b.right = e
        c.father = header
        c.right = f
        d.father = b
        d.left = g
        e.father = b
        e.left = h
        f.father = c
        f.left = i
        f.right = j
        g.father = d
        h.father = e
        i.father = f
        j.father = f
    
    
    # 前序遍历
    def preorder_traversal(header):
        print(header.value,',',end='')
        if header.left is not None:
            preorder_traversal(header.left)
        if header.right is not None:
            preorder_traversal(header.right)
    
    
    # 中序遍历
    def inorder_traversal(header):
        if header.left is not None:
            inorder_traversal(header.left)
        print(header.value,',',end='')
        if header.right is not None:
            inorder_traversal(header.right)
    
    
    # 后续遍历
    def postorder_traversal(header):
        if header.left is not None:
            postorder_traversal(header.left)
        if header.right is not None:
            postorder_traversal(header.right)
        print(header.value,',',end='')
    
    # 执行
    header = Node()
    header.value = 'a'
    generate_binary_tree(header)
    print('前序遍历')
    preorder_traversal(header)
    print('中序遍历')
    inorder_traversal(header)
    print('后序遍历')
    postorder_traversal(header)

运行结果

前序遍历
    a ,b ,d ,g ,e ,h ,c ,f ,i ,j ,

中序遍历
    g ,d ,b ,h ,e ,a ,c ,i ,f ,j ,

后序遍历
    g ,d ,h ,e ,b ,i ,j ,f ,c ,a ,