Python樹遍歷演算法 - tw511教學網

遍歷是存取樹的所有節點的過程，也可以列印它們的值。因為所有節點都通過邊(連結)連線，所以始終從根(頭)節點開始。也就是說，我們不能隨機存取樹中的一個節點。這裡介紹三種方式來遍歷一棵樹 -

順序遍歷
前序遍歷
後序遍歷

按順序遍歷

在這種遍歷方法中，首先存取左側子樹，然後存取根，然後存取右側子樹。我們應該永遠記住每個節點本身可能代表一個子樹。

在下面的python程式中，使用Node類為根節點以及左右節點建立預留位置。然後建立一個insert()函式來將資料新增到樹中。最後，Inorder遍歷邏輯通過建立一個空列表，並首先新增新增根節點或父節點，然後左節點來實現。最後新增左節點以完成Inorder遍歷。請注意，對於每個子樹重複此過程，直到遍歷所有節點。

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the Tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Inorder traversal
# Left -> Root -> Right
    def inorderTraversal(self, root):
        res = []
        if root:
            res = self.inorderTraversal(root.left)
            res.append(root.data)
            res = res + self.inorderTraversal(root.right)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))

執行上面範例程式碼，得到以下結果 -

[10, 14, 19, 27, 31, 35, 42]

前序遍歷

在這種遍歷方法中，首先存取根節點，然後存取左邊的子樹，最後存取右邊的子樹。

在下面的python程式中，使用Node類為根節點以及左右節點建立預留位置。然後建立一個insert()函式來將資料新增到樹中。最後，前序遍歷遍歷邏輯通過建立一個空列表並首先新增根節點，然後新增左節點來實現。最後新增右節點以完成前序遍歷。請注意，對於每個子樹重複此過程，直到遍歷所有節點。

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the Tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Preorder traversal
# Root -> Left ->Right
    def PreorderTraversal(self, root):
        res = []
        if root:
            res.append(root.data)
            res = res + self.PreorderTraversal(root.left)
            res = res + self.PreorderTraversal(root.right)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))

當上面的程式碼被執行時，它會產生以下結果 -

[27, 14, 10, 19, 35, 31, 42]

後序遍歷

在這個遍歷方法中，最後存取根節點。首先遍歷左子樹，然後遍歷右子樹，最後遍歷根節點。

在下面的python程式中，使用Node類為根節點以及左右節點建立預留位置。然後建立一個insert()函式來將資料新增到樹中。最後，通過建立一個空列表並新增左節點，然後新增右節點來實現後序遍歷邏輯。最後，新增根或父節點以完成後序遍歷。請注意，對於每個子樹重複此過程，直到遍歷所有節點。參考以下程式碼實現 -

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the Tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Postorder traversal
# Left ->Right -> Root
    def PostorderTraversal(self, root):
        res = []
        if root:
            res = self.PostorderTraversal(root.left)
            res = res + self.PostorderTraversal(root.right)
            res.append(root.data)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))

當上面的程式碼被執行時，它會產生以下結果 -

[10, 19, 14, 31, 42, 35, 27]