python 二叉樹

樹表示由邊連接的節(jié)點。它是一個非線性數(shù)據(jù)結(jié)構(gòu)。它具有以下屬性。

• 一個節(jié)點被標記為根節(jié)點。
• 除根之外的每個節(jié)點都與一個父節(jié)點相關(guān)聯(lián)。
• 每個節(jié)點可以有一個數(shù)字的節(jié)點號。

我們使用前面討論的概念os節(jié)點在python中創(chuàng)建一個樹數(shù)據(jù)結(jié)構(gòu)。我們將一個節(jié)點指定為根節(jié)點，然后將更多節(jié)點添加為子節(jié)點。下面是創(chuàng)建根節(jié)點的程序。

創(chuàng)建根

我們只需創(chuàng)建一個node類并添加一個值給節(jié)點。這變成只有根節(jié)點的樹。

class node:

    def __init__(self, data):

        self.left = none
        self.right = none
        self.data = data


    def printtree(self):
        print(self.data)

root = node(10)

root.printtree()

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

10

插入樹中

為了插入到樹中，我們使用上面創(chuàng)建的相同節(jié)點類并為其添加插入類。insert類將節(jié)點的值與父節(jié)點進行比較，并決定將其添加為左節(jié)點或右節(jié)點。最后，printtree類用于打印樹。

class node:

    def __init__(self, data):

        self.left = none
        self.right = none
        self.data = data

    def insert(self, data):
# compare the new value with the parent node
        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()

# use the insert method to add nodes
root = node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.printtree()

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

3 6 12 14

travesring一棵樹

樹可以通過決定訪問每個節(jié)點的序列來遍歷。我們可以清楚地看到，我們可以從一個節(jié)點開始，然后訪問左側(cè)子樹第一個和右側(cè)子樹?；蛘呶覀円部梢韵仍L問右邊的子樹，然后訪問左邊的子樹。因此，這些樹遍歷方法有不同的名稱。我們在這里實現(xiàn)樹遍歷算法的章節(jié)中詳細研究它們。