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

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

圖 1: 簡單樹

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

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

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

讓我們定義一些函數，使我們很容易像使用列表一樣操作樹。請注意，我們不會去定義一個二叉樹類。我們將編寫的函數將只是操作列表使之類似于樹。

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

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

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

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

為了完善樹的實現（參見Listing3），讓我們寫幾個用于獲取和設置根值的函數，以及獲得左邊或右邊子樹的函數。

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

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

使用節點和引用，我們認為該樹的結構類似于圖 2 所示。

圖 2：使用節點和引用表示簡單樹

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

Listing 4

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

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

接下來讓我們看一下我們需要構建的根節點以外的函數。為了添加左子節點，我們將創建一個新的二叉樹，并設置根的左屬性以指向這個新對象。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

我們必須考慮兩種情況進行插入。第一種情況是，沒有左子節點。當沒有左子節點時，將新節點添加即可。第二種情況的特征是，當前存在左子節點。在第二種情況下，我們插入一個節點并將之前的子節點降一級。第二種情況是由else語句在Listing 5的第 4 行進行處理。

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

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

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

既然我們已經有了所有創建和操作二叉樹的方法，讓我們再進一步檢查它的結構。讓我們把每一個節點比作一個簡單的樹的根，并添加節點 B 和 C 作為子節點。 下面的代碼就是創建樹，并存儲一些鍵值，為左右子節點賦值。注意，左右子節點和根都是同一個二叉樹類的不同對象。正如我們之前樹的定義中說的，我們能夠把一個二叉樹的任何子節點當成二叉樹來做處理。

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