摘要：列表的第二個(gè)元素的本身是一個(gè)表示左子樹(shù)的列表。子樹(shù)具有根節(jié)點(diǎn)和兩個(gè)表示葉節(jié)點(diǎn)的空列表。重要的是要記住這種表示的是左右子樹(shù)引用的是其他二叉樹(shù)的實(shí)例。為了完成一個(gè)簡(jiǎn)單的二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)的定義，我們寫(xiě)出訪問(wèn)參見(jiàn)左右子節(jié)點(diǎn)和根值的方法。

在用嵌套列表表示樹(shù)時(shí)，我們使用 Python 的列表來(lái)編寫(xiě)這些函數(shù)。雖然把界面寫(xiě)成列表的一系列方法與我們已實(shí)現(xiàn)其他的抽象數(shù)據(jù)類型有些不同，但這樣做比較有意思，因?yàn)樗鼮槲覀兲峁┮粋€(gè)簡(jiǎn)單、可以直接查看的遞歸數(shù)據(jù)結(jié)構(gòu)。在列表實(shí)現(xiàn)樹(shù)時(shí)，我們將存儲(chǔ)根節(jié)點(diǎn)作為列表的第一個(gè)元素的值。列表的第二個(gè)元素的本身是一個(gè)表示左子樹(shù)的列表。這個(gè)列表的第三個(gè)元素表示在右子樹(shù)的另一個(gè)列表。為了說(shuō)明這個(gè)存儲(chǔ)結(jié)構(gòu)，讓我們來(lái)看一個(gè)例子。圖 1 展示出一個(gè)簡(jiǎn)單的樹(shù)以及相應(yīng)的列表實(shí)現(xiàn)。

圖 1: 簡(jiǎn)單樹(shù)

myTree = ["a",   #root
      ["b",  #left subtree
       ["d" [], []],
       ["e" [], []] ],
      ["c",  #right subtree
       ["f" [], []],
       [] ]
     ]

請(qǐng)注意，我們可以使用索引來(lái)訪問(wèn)列表的子樹(shù)。樹(shù)的根是myTree[0]，根的左子樹(shù)是myTree[1]，和右子樹(shù)是myTree[2]。下面的代碼說(shuō)明了如何用列表創(chuàng)建簡(jiǎn)單樹(shù)。一旦樹(shù)被構(gòu)建，我們可以訪問(wèn)根和左、右子樹(shù)。嵌套列表法一個(gè)非常好的特性就是子樹(shù)的結(jié)構(gòu)與樹(shù)相同，本身是遞歸的。子樹(shù)具有根節(jié)點(diǎn)和兩個(gè)表示葉節(jié)點(diǎn)的空列表。列表的另一個(gè)優(yōu)點(diǎn)是它容易擴(kuò)展到多叉樹(shù)。在樹(shù)不僅僅是一個(gè)二叉樹(shù)的情況下，另一個(gè)子樹(shù)只是另一個(gè)列表。

myTree = ["a", ["b", ["d",[],[]], ["e",[],[]] ], ["c", ["f",[],[]], []] ]
print(myTree)
print("left subtree = ", myTree[1])
print("root = ", myTree[0])
print("right subtree = ", myTree[2])

讓我們定義一些函數(shù)，使我們很容易像使用列表一樣操作樹(shù)。請(qǐng)注意，我們不會(huì)去定義一個(gè)二叉樹(shù)類。我們將編寫(xiě)的函數(shù)將只是操作列表使之類似于樹(shù)。

def BinaryTree(r):
    return [r, [], []]

該二叉樹(shù)只是構(gòu)建一個(gè)根節(jié)點(diǎn)和兩個(gè)空子節(jié)點(diǎn)的列表。左子樹(shù)添加到樹(shù)的根，我們需要插入一個(gè)新的列表到根列表的第二個(gè)位置。我們必須注意，如果列表中已經(jīng)有值在第二個(gè)位置，我們需要跟蹤它，將新節(jié)點(diǎn)插入樹(shù)中作為其直接的左子節(jié)點(diǎn)。Listing 1 顯示了插入左子節(jié)點(diǎn)。

Listing 1

def insertLeft(root,newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1,[newBranch,t,[]])
    else:
        root.insert(1,[newBranch, [], []])
    return root

請(qǐng)注意，插入一個(gè)左子節(jié)點(diǎn)，我們首先獲取對(duì)應(yīng)于當(dāng)前左子節(jié)點(diǎn)的列表（可能是空的）。然后，我們添加新的左子節(jié)點(diǎn)，將原來(lái)的左子節(jié)點(diǎn)作為新節(jié)點(diǎn)的左子節(jié)點(diǎn)。這使我們能夠?qū)⑿鹿?jié)點(diǎn)插入到樹(shù)中的任何位置。對(duì)于insertRight的代碼類似于insertLeft，如Listing 2 中。

Listing 2

def insertRight(root,newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2,[newBranch,[],t])
    else:
        root.insert(2,[newBranch,[],[]])
    return root

為了完善樹(shù)的實(shí)現(xiàn)（參見(jiàn)Listing3），讓我們寫(xiě)幾個(gè)用于獲取和設(shè)置根值的函數(shù)，以及獲得左邊或右邊子樹(shù)的函數(shù)。

Listing 3

def getRootVal(root):
    return root[0]

def setRootVal(root,newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]

以下是完整的嵌套列表表示樹(shù)的代碼

def BinaryTree(r):
    return [r, [], []]

def insertLeft(root,newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1,[newBranch,t,[]])
    else:
        root.insert(1,[newBranch, [], []])
    return root

def insertRight(root,newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2,[newBranch,[],t])
    else:
        root.insert(2,[newBranch,[],[]])
    return root

def getRootVal(root):
    return root[0]

def setRootVal(root,newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]

r = BinaryTree(3)
insertLeft(r,4)
insertLeft(r,5)
insertRight(r,6)
insertRight(r,7)
l = getLeftChild(r)
print(l)

setRootVal(l,9)
print(r)
insertLeft(l,11)
print(r)
print(getRightChild(getRightChild(r)))

我們第二種表示樹(shù)的方式——節(jié)點(diǎn)和引用。在這種情況下，我們將定義具有根，以及左右子樹(shù)屬性的類。由于這種表示更緊密地結(jié)合了面向?qū)ο蟮姆绞?，我們將繼續(xù)使用這種表示完成本章的其余部分。

使用節(jié)點(diǎn)和引用，我們認(rèn)為該樹(shù)的結(jié)構(gòu)類似于圖 2 所示。

圖 2：使用節(jié)點(diǎn)和引用表示簡(jiǎn)單樹(shù)

我們將開(kāi)始用簡(jiǎn)單的節(jié)點(diǎn)和引用的類定義如Listing 4 所示。重要的是要記住這種表示的是左右子樹(shù)引用的是其他二叉樹(shù)的實(shí)例。例如，當(dāng)我們插入一個(gè)新的左子節(jié)點(diǎn)到樹(shù)上時(shí)，我們創(chuàng)建了二叉樹(shù)的另一個(gè)實(shí)例，修改了根節(jié)點(diǎn)的self leftChild使之指向新的樹(shù)。

Listing 4

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

注意Listing 4 中，構(gòu)造函數(shù)需要得到一些類型的對(duì)象存儲(chǔ)在根中。就像你可以在列表中存儲(chǔ)你喜歡的任何一種類型，樹(shù)的根對(duì)象可以指向任何一種類型。對(duì)于我們之前的例子中，我們將存儲(chǔ)節(jié)點(diǎn)設(shè)為根值的名稱。使用節(jié)點(diǎn)和引用來(lái)表示圖 2 中的樹(shù)，我們將創(chuàng)建二叉樹(shù)類的 6 個(gè)實(shí)例。

接下來(lái)讓我們看一下我們需要構(gòu)建的根節(jié)點(diǎn)以外的函數(shù)。為了添加左子節(jié)點(diǎn)，我們將創(chuàng)建一個(gè)新的二叉樹(shù)，并設(shè)置根的左屬性以指向這個(gè)新對(duì)象。insertLeft的代碼Listing 5 所示。

Listing 5

def insertLeft(self,newNode):
    if self.leftChild == None:
        self.leftChild = BinaryTree(newNode)
    else:
        t = BinaryTree(newNode)
        t.leftChild = self.leftChild
        self.leftChild = t

我們必須考慮兩種情況進(jìn)行插入。第一種情況是，沒(méi)有左子節(jié)點(diǎn)。當(dāng)沒(méi)有左子節(jié)點(diǎn)時(shí)，將新節(jié)點(diǎn)添加即可。第二種情況的特征是，當(dāng)前存在左子節(jié)點(diǎn)。在第二種情況下，我們插入一個(gè)節(jié)點(diǎn)并將之前的子節(jié)點(diǎn)降一級(jí)。第二種情況是由else語(yǔ)句在Listing 5的第 4 行進(jìn)行處理。

對(duì)于insertRight的代碼必須考慮一個(gè)對(duì)稱的情況。要么沒(méi)有右子節(jié)點(diǎn)，要么我們必須插入根和現(xiàn)有的右子節(jié)點(diǎn)之間。插入代碼Listing 6 所示。

Listing 6

def insertRight(self,newNode):
    if self.rightChild == None:
        self.rightChild = BinaryTree(newNode)
    else:
        t = BinaryTree(newNode)
        t.rightChild = self.rightChild
        self.rightChild = t

為了完成一個(gè)簡(jiǎn)單的二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)的定義，我們寫(xiě)出訪問(wèn)（參見(jiàn)Listing 7）左右子節(jié)點(diǎn)和根值的方法。

Listing 7

def getRightChild(self):
    return self.rightChild

def getLeftChild(self):
    return self.leftChild

def setRootVal(self,obj):
    self.key = obj

def getRootVal(self):
    return self.key

既然我們已經(jīng)有了所有創(chuàng)建和操作二叉樹(shù)的方法，讓我們?cè)龠M(jìn)一步檢查它的結(jié)構(gòu)。讓我們把每一個(gè)節(jié)點(diǎn)比作一個(gè)簡(jiǎn)單的樹(shù)的根，并添加節(jié)點(diǎn) B 和 C 作為子節(jié)點(diǎn)。 下面的代碼就是創(chuàng)建樹(shù)，并存儲(chǔ)一些鍵值，為左右子節(jié)點(diǎn)賦值。注意，左右子節(jié)點(diǎn)和根都是同一個(gè)二叉樹(shù)類的不同對(duì)象。正如我們之前樹(shù)的定義中說(shuō)的，我們能夠把一個(gè)二叉樹(shù)的任何子節(jié)點(diǎn)當(dāng)成二叉樹(shù)來(lái)做處理。

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    def getRightChild(self):
        return self.rightChild

    def getLeftChild(self):
        return self.leftChild

    def setRootVal(self,obj):
        self.key = obj

    def getRootVal(self):
        return self.key


r = BinaryTree("a")
print(r.getRootVal())
print(r.getLeftChild())
r.insertLeft("b")
print(r.getLeftChild())
print(r.getLeftChild().getRootVal())
r.insertRight("c")
print(r.getRightChild())
print(r.getRightChild().getRootVal())
r.getRightChild().setRootVal("hello")
print(r.getRightChild().getRootVal())