遍歷是訪問樹的所有節(jié)點(diǎn)的過程，也可以打印它們的值。 因?yàn)樗泄?jié)點(diǎn)都通過邊(鏈接)連接，所以始終從根(頭)節(jié)點(diǎn)開始。 也就是說，我們不能隨機(jī)訪問樹中的一個(gè)節(jié)點(diǎn)。 這里介紹三種方式來遍歷一棵樹 -

• 順序遍歷
• 前序遍歷
• 后序遍歷

按順序遍歷

在這種遍歷方法中，首先訪問左側(cè)子樹，然后訪問根，然后訪問右側(cè)子樹。 我們應(yīng)該永遠(yuǎn)記住每個(gè)節(jié)點(diǎn)本身可能代表一個(gè)子樹。

在下面的python程序中，使用Node類為根節(jié)點(diǎn)以及左右節(jié)點(diǎn)創(chuàng)建占位符。 然后創(chuàng)建一個(gè)insert()函數(shù)來將數(shù)據(jù)添加到樹中。 最后，Inorder遍歷邏輯通過創(chuàng)建一個(gè)空列表，并首先添加添加根節(jié)點(diǎn)或父節(jié)點(diǎn)，然后左節(jié)點(diǎn)來實(shí)現(xiàn)。 最后添加左節(jié)點(diǎn)以完成Inorder遍歷。 請(qǐng)注意，對(duì)于每個(gè)子樹重復(fù)此過程，直到遍歷所有節(jié)點(diǎn)。

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))

執(zhí)行上面示例代碼，得到以下結(jié)果 -

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

前序遍歷

在這種遍歷方法中，首先訪問根節(jié)點(diǎn)，然后訪問左邊的子樹，最后訪問右邊的子樹。

在下面的python程序中，使用Node類為根節(jié)點(diǎn)以及左右節(jié)點(diǎn)創(chuàng)建占位符。 然后創(chuàng)建一個(gè)insert()函數(shù)來將數(shù)據(jù)添加到樹中。 最后，前序遍歷遍歷邏輯通過創(chuàng)建一個(gè)空列表并首先添加根節(jié)點(diǎn)，然后添加左節(jié)點(diǎn)來實(shí)現(xiàn)。 最后添加右節(jié)點(diǎn)以完成前序遍歷。 請(qǐng)注意，對(duì)于每個(gè)子樹重復(fù)此過程，直到遍歷所有節(jié)點(diǎn)。

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))

當(dāng)上面的代碼被執(zhí)行時(shí)，它會(huì)產(chǎn)生以下結(jié)果 -

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

后序遍歷

在這個(gè)遍歷方法中，最后訪問根節(jié)點(diǎn)。 首先遍歷左子樹，然后遍歷右子樹，最后遍歷根節(jié)點(diǎn)。

在下面的python程序中，使用Node類為根節(jié)點(diǎn)以及左右節(jié)點(diǎn)創(chuàng)建占位符。 然后創(chuàng)建一個(gè)insert()函數(shù)來將數(shù)據(jù)添加到樹中。 最后，通過創(chuàng)建一個(gè)空列表并添加左節(jié)點(diǎn)，然后添加右節(jié)點(diǎn)來實(shí)現(xiàn)后序遍歷邏輯。 最后，添加根或父節(jié)點(diǎn)以完成后序遍歷。 請(qǐng)注意，對(duì)于每個(gè)子樹重復(fù)此過程，直到遍歷所有節(jié)點(diǎn)。參考以下代碼實(shí)現(xiàn) -

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))

當(dāng)上面的代碼被執(zhí)行時(shí)，它會(huì)產(chǎn)生以下結(jié)果 -

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