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

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

圖 1: 簡單樹

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

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

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ù)將只是操作列表使之類似于樹。

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

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

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

請注意，插入一個左子節(jié)點，我們首先獲取對應(yīng)于當(dāng)前左子節(jié)點的列表（可能是空的）。然后，我們添加新的左子節(jié)點，將原來的左子節(jié)點作為新節(jié)點的左子節(jié)點。這使我們能夠?qū)⑿鹿?jié)點插入到樹中的任何位置。對于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

為了完善樹的實現(xiàn)（參見Listing3），讓我們寫幾個用于獲取和設(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]

以下是完整的嵌套列表表示樹的代碼

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

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

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

圖 2：使用節(jié)點和引用表示簡單樹

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

Listing 4

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

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

接下來讓我們看一下我們需要構(gòu)建的根節(jié)點以外的函數(shù)。為了添加左子節(jié)點，我們將創(chuàng)建一個新的二叉樹，并設(shè)置根的左屬性以指向這個新對象。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)行插入。第一種情況是，沒有左子節(jié)點。當(dāng)沒有左子節(jié)點時，將新節(jié)點添加即可。第二種情況的特征是，當(dāng)前存在左子節(jié)點。在第二種情況下，我們插入一個節(jié)點并將之前的子節(jié)點降一級。第二種情況是由else語句在Listing 5的第 4 行進(jìn)行處理。

對于insertRight的代碼必須考慮一個對稱的情況。要么沒有右子節(jié)點，要么我們必須插入根和現(xiàn)有的右子節(jié)點之間。插入代碼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

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

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)建和操作二叉樹的方法，讓我們再進(jìn)一步檢查它的結(jié)構(gòu)。讓我們把每一個節(jié)點比作一個簡單的樹的根，并添加節(jié)點 B 和 C 作為子節(jié)點。 下面的代碼就是創(chuàng)建樹，并存儲一些鍵值，為左右子節(jié)點賦值。注意，左右子節(jié)點和根都是同一個二叉樹類的不同對象。正如我們之前樹的定義中說的，我們能夠把一個二叉樹的任何子節(jié)點當(dāng)成二叉樹來做處理。

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