Python實作深度優先與廣度優先

二叉樹的兩種周遊是資料結構的經典考察題目, 廣度周遊考察隊列結構, 深度周遊考察遞歸

二叉樹

深度優先

• 先序周遊(父, 左子, 右子) 0, 1, 3, 7, 8, 4, 9, 2, 5, 6
• 中序周遊(左子, 父, 右子) 7, 3, 8, 1, 9, 4, 0, 5, 2, 6
• 後序周遊(左子, 右子, 父) 7, 8, 3, 9, 4, 1, 5, 6, 2, 0

"深度優先周遊"考察遞歸, 将子節點為空作為終止遞歸的條件

廣度優先

"廣度優先周遊"考察隊列的結構, 消除父節點(出隊列,順便列印), 添加子節點(進隊列),當隊列内元素個數為零, 完成周遊

添加元素

廣度優先周遊

先序周遊

中序周遊

後續周遊

Python3 實作

class Node(object):
    """初始化一個節點,需要為節點設定值"""
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BinaryTree(object):
    """
    建立二叉樹,完成
    - 添加元素
    - 廣度周遊
    - 深度周遊(先序周遊, 中序周遊, 後序周遊)
    """
    def __init__(self):
        self.root = None
        pass

    # 添加元素
    def addNode(self, val):
        # 建立隊列結構存儲結點
        nodeStack = [self.root,]

        # 如果根結點為空
        if self.root == None:
            self.root = Node(val)
            print("添加根節點{0}成功!".format(self.root.val))
            return


        while len(nodeStack) > 0:
            # 隊列元素出列
            p_node = nodeStack.pop()

            # 如果左子結點為空
            if p_node.left == None:
                p_node.left = Node(val)
                print("添加左:{0} ".format(p_node.left.val))
                return

            # 如果右子節點為空
            if p_node.right == None:
                p_node.right = Node(val)
                print("添加右:{0} ".format(p_node.right.val))
                return

            nodeStack.insert(0, p_node.left)
            nodeStack.insert(0, p_node.right)

    # 廣度周遊(中序: 先讀父節點,再讀左子節點, 右子節點)
    def breadthFirst(self):
        nodeStack = [self.root, ];

        while len(nodeStack) > 0:
            my_node = nodeStack.pop()
            print("-->",my_node.val)

            if my_node.left is not None:
                nodeStack.insert(0, my_node.left)

            if my_node.right is not None:
                nodeStack.insert(0, my_node.right)

    # 深度優先(先序周遊)

    def preorder(self, start_node):

        if start_node == None:
            return

        print(start_node.val)
        self.preorder(start_node.left)
        self.preorder(start_node.right)


    # 深度優先(中序周遊)
    def inorder(self, start_node):
        if start_node == None:
            return

        self.inorder(start_node.left)
        print(start_node.val)
        self.inorder(start_node.right)

    # 深度優先(後序周遊)
    def outorder(self, start_node):
        if start_node == None:
            return
        self.outorder(start_node.left)
        self.outorder(start_node.right)
        print(start_node.val)

def main():
    bt = BinaryTree()
    bt.addNode(0)
    bt.addNode(1)
    bt.addNode(2)
    bt.addNode(3)
    bt.addNode(4)
    bt.addNode(5)
    bt.addNode(6)
    bt.addNode(7)
    bt.addNode(8)
    bt.addNode(9)

    print("廣度周遊-->")
    bt.breadthFirst()
    
    print("先序周遊-->")
    bt.preorder(bt.root)

    print("中序周遊-->")
    bt.inorder(bt.root)
    
    print("後序周遊-->")
    bt.outorder(bt.root)

if __name__ == '__main__':
    main()