二叉树的前序、中序、后序、层次遍历以及最大深度 Python写法

我不是女神ヾ 2021-12-14 20:19 74阅读 0赞

前序遍历：根节点、左子树、右子树  
中序遍历：左子树、根节点、右子树  
后序遍历：左子树、右子树、根节点、  
层次遍历：一层一层遍历，上层优先

class Node(object):
        def __init__(self,data=None,left =None, right =None):
            self.data =data
            self.left= left
            self.right = right
        def pre(self,root):
            if root ==None:
                return
            print(root.data,end="")
            self.pre(root.left)
            self.pre(root.right)
        def mid(self,root):
            if root == None:
                return
            self.mid(root.left)
            print(root.data,end="")
            self.mid(root.right)
        def behind(self,root):
            if root == None:
                return
            self.behind(root.left)
            self.behind(root.right)
            print(root.data,end="")
        def depth(self,root):
            if root ==None:
                return 0
            dl,rl = self.depth(root.left),self.depth(root.right)
            return max(dl,rl)+1  #不能用print()
        def level(self,root):
            if root == None:
                return
            queue = []
            queue.append(root)
            while queue:
                current = queue.pop(0)
                print(current.data,end="")
                if current.left !=None:
                    queue.append(current.left)
                if current.right != None:
                    queue.append(current.right)
    if __name__ == '__main__':
        t=Node()
        root = Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
        print('前序遍历：')
        t.pre(root)
        print()
        print('中序遍历：')
        t.mid(root)
        print()
        print('后序遍历：')
        t.behind(root)
        print()
        print('深度：')
        print(t.depth(root))
        print('层次遍历：')
        t.level(root)
    #输出：
    # 前序遍历：
    # DBACEGF
    # 中序遍历：
    # ABCDEFG
    # 后序遍历：
    # ACBFGED
    # 深度：
    # 4
    # 层次遍历：
    # DBEACGF