python 樹(shù)遍歷算法

遍歷是訪問(wèn)樹(shù)的所有節(jié)點(diǎn)的過(guò)程，也可以打印它們的值。因?yàn)樗泄?jié)點(diǎn)都通過(guò)邊（鏈接）連接，所以我們始終從根（頭）節(jié)點(diǎn)開(kāi)始。也就是說(shuō)，我們不能隨機(jī)訪問(wèn)樹(shù)中的一個(gè)節(jié)點(diǎn)。我們用三種方式來(lái)遍歷一棵樹(shù)

• 按順序遍歷
• 預(yù)購(gòu)遍歷
• 后序遍歷

按順序遍歷

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

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

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

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

預(yù)購(gòu)遍歷

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

在下面的python程序中，我們使用node類(lèi)為根節(jié)點(diǎn)以及左右節(jié)點(diǎn)創(chuàng)建占位符。然后我們創(chuàng)建一個(gè)插入函數(shù)來(lái)將數(shù)據(jù)添加到樹(shù)中。最后，pre- order遍歷邏輯通過(guò)創(chuàng)建一個(gè)空列表并首先添加根節(jié)點(diǎn)，然后添加左節(jié)點(diǎn)來(lái)實(shí)現(xiàn)。最后添加正確的節(jié)點(diǎn)以完成預(yù)訂遍歷。請(qǐng)注意，對(duì)于每個(gè)子樹(shù)重復(fù)此過(guò)程，直到遍歷所有節(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è)遍歷方法中，最后訪問(wèn)根節(jié)點(diǎn)，因此名稱(chēng)。首先我們遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后遍歷根節(jié)點(diǎn)。

在下面的python程序中，我們使用node類(lèi)為根節(jié)點(diǎn)以及左右節(jié)點(diǎn)創(chuàng)建占位符。然后我們創(chuàng)建一個(gè)插入函數(shù)來(lái)將數(shù)據(jù)添加到樹(shù)中。最后，通過(guò)創(chuàng)建一個(gè)空列表并首先添加左節(jié)點(diǎn)，然后添加右節(jié)點(diǎn)來(lái)實(shí)現(xiàn)post- order遍歷邏輯。最后，根或父節(jié)點(diǎn)被添加以完成后序遍歷。請(qǐng)注意，對(duì)于每個(gè)子樹(shù)重復(fù)此過(guò)程，直到遍歷所有節(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()

# 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]