Python樹遍歷演算法


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

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

按順序遍歷

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

在下面的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]