目標(biāo)
- 學(xué)習(xí)樹數(shù)據(jù)結(jié)構(gòu)的相關(guān)術(shù)語。
- 了解樹數(shù)據(jù)結(jié)構(gòu)適用的各種應(yīng)用程序。
- 能夠使用鏈接或者數(shù)組來實現(xiàn)樹結(jié)構(gòu)，并且熟悉基于樹的基本算法。
- 了解二叉搜索樹結(jié)構(gòu)以及它的各種操作的效率。
- 通過更多的練習(xí)來提高對遞歸算法的理解。
7.1 概要
到目前為止，我們主要處理的都是像列表、堆棧和隊列這樣的線性數(shù)據(jù)結(jié)構(gòu)，它們一般被用來表示序列中的各個元素。在本章中，我們將對之前講的內(nèi)容進行拓展，來考慮一個被稱為樹（tree）的非線性數(shù)據(jù)結(jié)構(gòu)。樹是按照層級的方式來存儲數(shù)據(jù)的，因此，它非常便于對現(xiàn)實世界的層次結(jié)構(gòu)進行建模。例如，你肯定對表示親屬信息的家譜的概念非常熟悉。其他一些關(guān)于樹的例子有分類學(xué)以及公司的匯報結(jié)構(gòu)。
比如說，我們可以使用樹來表示生物學(xué)家使用的生物類群里的動物。動物可以細(xì)分為脊椎動物和無脊椎動物；脊椎動物可以細(xì)分為爬行動物、魚類、哺乳動物等。這個樹看起來就會如圖7.1所示。層次關(guān)系在我們的生活中隨處可見，因此，樹在許多的應(yīng)用程序里都被用來作為數(shù)據(jù)的自然表示。
圖7.1 生物學(xué)家的生物類群的一部分
可能會讓你驚訝的是，事實證明，在實現(xiàn)之前提到普通的序列數(shù)據(jù)的時候，樹也非常有用。在這一章里，我們將看到被稱為二叉搜索樹（binary search tree）的樹結(jié)構(gòu)。它被用來實現(xiàn)一個允許高效插入和刪除（類似于鏈表）的集合，但它同時也能夠進行高效的搜索（類似于有序數(shù)組）。基于樹的數(shù)據(jù)結(jié)構(gòu)和算法對于高效處理大量的數(shù)據(jù)（如數(shù)據(jù)庫和文件系統(tǒng)）來說至關(guān)重要。
7.2 樹的術(shù)語
計算機科學(xué)家們用一個包含節(jié)點的集合（類似于鏈表中的節(jié)點）以及用來連接它們的邊（edge）來表示樹。圖7.2所示為一個包含7個節(jié)點的樹，其中每個節(jié)點都包含著一個整數(shù)。圖中最頂端的節(jié)點被稱為根（root）。在這個樹里，根包含的數(shù)據(jù)值是2。一個樹只能有一個根。因此，你可以跟隨從根開始的邊（箭頭）到達樹里面的任何一個其他節(jié)點。
圖7.2 二叉樹示例
樹里的每個節(jié)點都可以通過邊與它的子節(jié)點（child）相連接。在一個普通的樹里，一個節(jié)點可以有任意數(shù)量的子節(jié)點，但在這里，讓我們先只關(guān)注二叉樹（binary tree）。在二叉樹里，每個節(jié)點最多只能有兩個子節(jié)點。就像圖7.2所示的那樣，這里所描繪的樹就是二叉樹。樹里面的關(guān)系是用家庭和樹相關(guān)的術(shù)語混合起來描述的。根節(jié)點有兩個子節(jié)點：包含7的節(jié)點是它的左子節(jié)點（left child）；包含6的節(jié)點是它的右子節(jié)點（right child）。這兩個節(jié)點也被稱為兄弟節(jié)點（sibling）。同樣地，包含8和4的兩個節(jié)點也是兄弟節(jié)點。那么節(jié)點5的父節(jié)點（parent）是節(jié)點7。同樣節(jié)點3是節(jié)點7的后代（descendant），節(jié)點7是節(jié)點3的祖先（ancestor）。最后，沒有任何子節(jié)點的節(jié)點則被叫作葉節(jié)點（leaf）。節(jié)點的深度（depth）代表它與根節(jié)點之間的邊數(shù)。對于根節(jié)點來說，它的深度為零。節(jié)點7和6的深度為1，節(jié)點3的深度則為3。樹的高度（height）或者說樹的深度（depth）是所有節(jié)點里的最大深度。
在滿二叉樹（full binary tree）中，每個深度級別的每一個可能的位置都有一個節(jié)點。在最下面一層，所有的節(jié)點都是葉節(jié)點（也就是說，所有的葉節(jié)點都處于相同的深度，并且每個非葉節(jié)點都具有兩個子節(jié)點）。而完全二叉樹是在最深層之外的每一個可能位置都有一個節(jié)點，并且在最深的那一層，節(jié)點按照從左到右的位置進行排列。可以從滿二叉樹開始，然后在下一層從左到右添加節(jié)點，或者是從右到左刪除最后一層的節(jié)點來創(chuàng)建完全二叉樹。它們兩個的示例如圖7.3所示。
圖7.3 左側(cè)是完全二叉樹，右側(cè)是滿二叉樹
樹的每個節(jié)點及其后代都可以被視為一個子樹（subtree）。比如說，在圖7.2里，節(jié)點7、5和3組合在一起可以被認(rèn)為是整個樹的一個子樹，其中，節(jié)點7是這個子樹的根節(jié)點。通過這種方式來看的話，很明顯地，樹可以被當(dāng)作遞歸結(jié)構(gòu)。一個二叉樹可以是空樹，也可以是根節(jié)點和（可能為空的）左右子樹組合起來的樹。
和列表類似，樹的一個非常有用的操作是遍歷。給定一個樹，我們需要有一種合適的方式來系統(tǒng)地“走過”這個樹的每一個節(jié)點。但是和列表不同的是，并沒有一個很清晰的遍歷樹的方法。可以看到，樹里的每一個節(jié)點都由3部分組成：數(shù)據(jù)、左子樹和右子樹。因此，根據(jù)我們的側(cè)重點來決定處理這些數(shù)據(jù)，我們可以有3種不同的遍歷順序來進行選擇。如果我們先在根節(jié)點處理數(shù)據(jù)，然后再去處理左右子樹的話，我們將會執(zhí)行被稱為前序遍歷（preorder traversal）的遍歷方法。這個遍歷方法之所以叫這個名字，是因為我們首先需要考慮的是根節(jié)點里的數(shù)據(jù)。前序遍歷可以很容易地被表示成一個遞歸算法：
def traverse(tree):
if tree is not empty:
process data at tree’s root # preorder traversal
traverse(tree’s left subtree)
traverse(tree’s right subtree)
把這個算法應(yīng)用于圖7.2里的樹的話，節(jié)點將會按照2、7、5、3、6、8、4這樣的順序進行處理。
當(dāng)然，我們也可以通過簡單地移動實際處理數(shù)據(jù)的位置來修改遍歷算法。中序遍歷（inorder traversal）將會在處理兩個子樹之間的時候處理根節(jié)點的數(shù)據(jù)。對于我們那個例子里的樹，中序遍歷將會按照7、3、5、2、8、6、4的序列來處理節(jié)點。你現(xiàn)在可能已經(jīng)猜到了，后序遍歷（postorder traversal）會在處理完兩個子樹之后再去處理根節(jié)點，這就給了我們這樣一個順序：3、5、7、8、4、6、2。
7.3 示例應(yīng)用程序：表達式樹
樹在計算機科學(xué)中的一個重要應(yīng)用是存儲程序的內(nèi)部結(jié)構(gòu)。當(dāng)解釋器或編譯器分析程序的時候，它會構(gòu)造一個用來提取程序結(jié)構(gòu)的解析樹（parse tree）。例如，考慮這樣一個簡單的表達式：(2 + 3) * 4 + 5 * 6。這個表達式可以用圖7.4所示的樹的形式來表現(xiàn)。可以仔細(xì)看看，樹的層次結(jié)構(gòu)是怎么消除對括號的需要的。表達式的基本操作數(shù)是樹的葉節(jié)點，而運算符是樹的內(nèi)部節(jié)點。在樹的低層級里的操作必須要被優(yōu)先執(zhí)行，只有這樣它的結(jié)果才能夠被用在更高層級的表達式里。很明顯，加法2 + 3必須是第一個需要執(zhí)行的操作，這是因為它出現(xiàn)在了樹的最底層。
圖7.4 數(shù)學(xué)表達式的樹呈現(xiàn)
將表達式表現(xiàn)為樹結(jié)構(gòu)之后，我們就能夠做很多有趣的事情了。編譯器將遍歷這個結(jié)構(gòu)來生成執(zhí)行計算的一系列機器指令。解釋器也會使用這個結(jié)構(gòu)來執(zhí)行這個表達式。它可以獲取兩個子節(jié)點的值，再使用這個操作來計算出每個節(jié)點的值。如果其中的一個或兩個子節(jié)點本身是一個運算符，那么就必須要先對這個子節(jié)點進行計算。一個簡單的樹的后序遍歷就能夠被用來計算表達式：
def evaluateTree(tree):
if tree’s root is an operand:
return root data
else: # root contains an operator
leftValue = evaluateTree(tree’s left subtree)
rightValue = evaluateTree(tree’s right subtree)
result = Apply operator at root to leftValue and rightValue
return result
如果你夠仔細(xì)的話，你會發(fā)現(xiàn)這個算法其實是一個用來計算表達式的后綴版本的遞歸算法。簡單地進行后序遍歷，這個表達式樹會產(chǎn)生這個序列：2 3 + 4 * 5 6 * +。而這正好是我們最初的表達式的后綴表示法。在第5章里，我們用了一個堆棧的算法來計算后綴方程。在這里，通過利用遞歸隱式地使用計算機的運行時堆棧，我們也完成了相同的任務(wù)。順便說一句，你也可以通過執(zhí)行恰當(dāng)?shù)谋闅v，來獲取表達式的前綴版本和中綴版本。當(dāng)這一切的知識都相互交織在一起的時候，難道不令人著迷嗎？
7.4 樹的存儲方式
現(xiàn)在，你已經(jīng)了解了樹可以做什么，接下來考慮一下樹可能的具體存儲方式。構(gòu)建樹的一種簡單明了的方法是使用鏈接來表示。和我們處理鏈表一樣，我們可以創(chuàng)建一個類來表示樹的節(jié)點。每個節(jié)點都有一個實例變量來保存對節(jié)點數(shù)據(jù)的引用，同時還有用來引用左右子節(jié)點的變量。我們將使用None對象來表示空子樹。于是，我們有了這樣一個Python的類：
# TreeNode.py
class TreeNode(object):
def __init__(self, data = None, left=None, right=None):
"""creates a tree node with specified data and references to left
and right children"""
self.item = data
self.left = left
self.right = right
使用這個TreeNode類，就能夠很方便地直接像鏡像一樣創(chuàng)建我們已經(jīng)看到過的二叉樹圖的鏈?zhǔn)浇Y(jié)構(gòu)。比如，下面這段代碼就可以構(gòu)建一個包含3個節(jié)點的簡單樹：
left = TreeNode(1)
right = TreeNode(3)
root = TreeNode(2, left, right)
通過簡單地對TreeNode類的構(gòu)造函數(shù)進行組合調(diào)用，我們也可以用一行代碼來達到相同的目的：
root = TreeNode(2, TreeNode(1), TreeNode(3))
更進一步，我們甚至可以利用這種方法來創(chuàng)建各個樹的節(jié)點，從而構(gòu)建出任意復(fù)雜度的樹結(jié)構(gòu)。下面這段代碼可以創(chuàng)建出類似于圖7.2這樣的樹結(jié)構(gòu)：
root = TreeNode(2,
TreeNode(7,
None,
TreeNode(5,
TreeNode(3),
None
)
)
TreeNode(6,
TreeNode(8),
TreeNode(4)
)
)
這里使用了縮進來幫助我們直觀地讓表達式的布局與樹的結(jié)構(gòu)相匹配。比如說，從例子里我們可以看到，在根節(jié)點（2）的下面，有兩個縮進的子樹（7和6）。如果你覺得這樣并不是很直觀的話，可以試著把頭側(cè)著看這段代碼。
當(dāng)然，通常來說，我們并不希望像這樣通過直接操作TreeNodes類來構(gòu)建復(fù)雜結(jié)構(gòu)。與之相反的是，我們一般會創(chuàng)建一個更高級別的容器類，通過這個容器類來封裝樹構(gòu)建的細(xì)節(jié)，并且提供一組方便的API來操作樹結(jié)構(gòu)。容器類的具體設(shè)計將取決于我們需要使用樹去完成的任務(wù)。在下一節(jié)里，我們將會看到這方面的例子。
我們應(yīng)該提到過可以用鏈接來存儲樹。但是，這并不是二叉樹唯一的實現(xiàn)方式。在某些情況下，使用基于數(shù)組/列表的方法來實現(xiàn)樹結(jié)構(gòu)也很方便。因為，我們可以通過數(shù)組中的位置來隱式地維護節(jié)點之間的關(guān)系，而不是用顯式的鏈接來存儲子節(jié)點。
在通過數(shù)組來實現(xiàn)樹的方案里，我們將會先假設(shè)我們總是有一個完整的樹。然后，我們可以逐級地將節(jié)點放置到數(shù)組里去。所以，數(shù)組中的第一個單元格將會存儲根節(jié)點，后面的兩個位置將會用來存儲根節(jié)點的子節(jié)點，再接下來的4個位置用來存儲孫節(jié)點，后面的也以此類推。按照這種方法，對于位置i的節(jié)點，總是有：它的左子節(jié)點位于位置2*i + 1，它的右子節(jié)點將會位于位置2*i + 2；節(jié)點i的父節(jié)點會位于(i − 1)//2。在這里有一點需要注意的是，對于這些公式來說，每個節(jié)點都始終有兩個子節(jié)點這個假設(shè)將會非常重要。為了滿足這個假設(shè)，你將需要用一些特殊的標(biāo)記值（例如None）來表示空節(jié)點。圖7.2中的示例二叉樹將會被存儲為這樣的數(shù)組：[2, 7, 6, None, 5, 8, 4, None, None, 3]。如果你想計算簡單一點，你可以把數(shù)組里的第一個位置（索引0）留空，然后把根節(jié)點放在索引1的位置。這樣的話，對于位置i的節(jié)點，左子節(jié)點將會位于2*i，右子節(jié)點則會位于2*i + 1，而父節(jié)點將會在位置i//2。
樹基于數(shù)組的實現(xiàn)方法的優(yōu)點是：它不需要使用內(nèi)存來顯式地存儲子節(jié)點的鏈接。但是，它卻需要我們?yōu)榭展?jié)點浪費單元格。如果樹非常稀疏的話，數(shù)組/列表里將會有大量的None元素，而且我們曾經(jīng)提到過，數(shù)組/列表的實現(xiàn)也并不能有效地利用內(nèi)存。因此，基于這些問題，通過鏈接來實現(xiàn)樹將會更加合適。
7.5 應(yīng)用：二叉搜索樹
在這一節(jié)里，我們將會為有序序列構(gòu)建另一個容器類，通過創(chuàng)建這個容器類，我們會了解到樹的一種實現(xiàn)技術(shù)。在4.7節(jié)里我們討論過應(yīng)該如何權(quán)衡序列的鏈接和數(shù)組的實現(xiàn)。雖然鏈表提供了高效的插入和刪除操作（因為不用移動元素），但它們不具備高效的搜索操作。而同時，一個有序的數(shù)組將能夠提供高效的搜索操作（通過二分搜索算法），但是插入和刪除操作將會需要Θ (n)的時間。然而在這里，通過使用一種特殊結(jié)構(gòu)的樹——二叉搜索樹，我們將能夠結(jié)合這兩者的優(yōu)點。
7.5.1 二分查找屬性
二叉搜索樹只是一個二叉樹，但是這個樹中的每一個節(jié)點都具有這樣一個額外的屬性：任意節(jié)點的左子樹里的值都將小于節(jié)點上的值，而它的右子樹里的值則會大于節(jié)點上的值。圖7.5所示為一個二叉搜索樹的例子。
圖7.5 二叉搜索樹的例子
在一個二叉搜索樹里搜索元素的話，一般來說將會非常高效。我們將會先從樹的根節(jié)點開始，并且檢查這個節(jié)點的數(shù)據(jù)值。如果根節(jié)點的值就是我們要查找的值，那么就完成整個搜索。如果我們搜索的值小于根節(jié)點的值，那么我們就能知道，如果這個值存在于樹里的話，它只可能在左子樹里。類似地，如果我們要搜索的值大于根節(jié)點的值，那說明它應(yīng)該在右子樹里。我們可以到相對應(yīng)的子樹里，用相同的規(guī)則來繼續(xù)這個搜索過程，直到我們找到這個元素，或者會找到一個空子樹的節(jié)點，這說明二叉搜索樹里并沒有這個值，而如果要把這個值插入到二叉搜索樹的話，這個節(jié)點正好是這個值所會在的位置。如果這個樹相當(dāng)“平衡”的話，那么對于每個節(jié)點來說，我們基本上能夠做到將必須要進行比較的元素的數(shù)量減少一半。換句話說，我們正在執(zhí)行二分搜索算法，這也就是為什么它被稱為二叉搜索樹。
7.5.2 實現(xiàn)一個二叉搜索樹
遵循良好的設(shè)計原則，我們將編寫一個BST（Binary Search Tree）類，這個類將會被用來封裝二叉搜索樹的所有細(xì)節(jié)，并且提供一組易于使用的接口。我們的樹結(jié)構(gòu)將會維護一組元素，并且允許我們進行添加、刪除和搜索特定值的操作。在這里，我們將會使用鏈接來練習(xí)引用相關(guān)的知識，當(dāng)然你也可以很簡單地把它轉(zhuǎn)換為之前我們討論過的基于數(shù)組的實現(xiàn)。BST對象將會包含對TreeNode對象的引用，這個TreeNode對象的引用是二叉搜索樹的根節(jié)點。在最初的時候，樹是空樹。因此，這個引用將會是None。于是，有了我們的類的構(gòu)造函數(shù)：
# BST.py
from TreeNode import TreeNode
class BST(object):
def __init__(self):
"""create empty binary search tree
post: empty tree created"""
self.root = None
現(xiàn)在，讓我們來解決把元素添加到二叉搜索樹這個問題。一次只添加一個葉節(jié)點來生成一個樹很容易實現(xiàn)。這個實現(xiàn)的一個關(guān)鍵點是，在給定的現(xiàn)有二叉搜索樹里，有且只有一個位置可以被用來放新插入的元素。讓我們來考慮一個例子。假設(shè)我們想在圖7.6所示的二叉搜索樹中插入5。那么，從根節(jié)點6開始的話，我們可以知道5必須進入左子樹。這個左子樹的根的值是2，所以我們繼續(xù)進入它的右子樹。這個子樹的根的值是4，因此我們將繼續(xù)進入它的右子樹。而這個時候，這個右子樹是空的。也就是說，應(yīng)該在這個地方插入5作為新的葉節(jié)點。
圖7.6 插入二叉搜索樹的示例
我們可以使用迭代或者遞歸的方法來實現(xiàn)這個基本的插入算法。無論使用哪種方式，我們都會從樹的頂部開始，不斷地向下執(zhí)行，并且根據(jù)需要來決定是去左子樹還是右子樹，直到找到新元素應(yīng)該存放的位置。和其他鏈?zhǔn)浇Y(jié)構(gòu)的算法相同的是，我們需要在整個結(jié)構(gòu)為空的時候，特別注意一下特殊情況。這是因為，在這種情況下，相關(guān)的操作需要我們?nèi)ジ母?jié)點的實例變量。這是算法的一個版本，它使用循環(huán)來向下遍歷整個樹結(jié)構(gòu)：
def insert(self, item):
"""insert item into binary search tree
pre: item is not in self
post: item has been added to self"""
if self.root is None: # handle empty tree case
self.root = TreeNode(item)
else:
# start at root
node = self.root
# loop to find the correct spot (break to exit)
while True:
if item == node.item:
raise ValueError("Inserting duplicate item")
if item < node.item: # item goes in left subtree
if node.left is not None: # follow existing subtree
node = node.left
else: # empty subtree, insert here
node.left = TreeNode(item)
break
else: # item goes in right subtree
if node.right is not None: # follow existing subtree
node = node.right
else: # empty subtree, insert here
node.right = TreeNode(item)
break
這段代碼鑒于它的嵌套決策結(jié)構(gòu)，看起來相當(dāng)復(fù)雜。但是，跟蹤代碼的話，你應(yīng)該不會有太多的麻煩。代碼里需要注意的是，我們有一個保證這個元素在這個樹里不存在的先驗條件。一個純粹二叉搜索樹是不允許一個值有多個副本的，因此我們會去檢查這個條件，在這個樹結(jié)構(gòu)里如果已經(jīng)存在了相同的元素就拋出異常。假如想要擴展這個設(shè)計，讓它允許出現(xiàn)多個值的話，只需要輕松地在每個節(jié)點中都保留已添加的值的次數(shù)就可以了。
隨著這個算法的出現(xiàn)，為了能夠讓你記憶得更清晰，我們還可以再考慮一下如何使用遞歸來解決這個問題。我們在前面曾經(jīng)說過，樹結(jié)構(gòu)是一種自然遞歸的數(shù)據(jù)結(jié)構(gòu)，但是我們的BST類并不是一個真正的遞歸結(jié)構(gòu)。但是，樹的互相鏈接節(jié)點本身的結(jié)構(gòu)是遞歸的。因此，我們可以認(rèn)為樹里的任何一個節(jié)點都是它的子樹的根，并且，它本身會包含兩個更小的子樹。當(dāng)然，None值代表著這個子樹為空。有了這樣的點子，我們就能夠很容易地將插入算法轉(zhuǎn)換為對子樹進行操作的遞歸方法。我們將會按照這個設(shè)計，寫一個遞歸的輔助方法，通過調(diào)用這個輔助方法來執(zhí)行插入操作。這樣的話，插入方法本身將會非常小：
def insert_rec(self, item):
"""insert item into binary search tree
pre: item is not in self
post: item has been added to self"""
self.root = self._subtreeInsert(self.root, item)
清楚地了解_subtreeInsert做了什么是非常重要的。可以看到，這個方法將會接收一個節(jié)點和需要被插入的元素（item）；同時，這個節(jié)點將會是被插入的元素所在的子樹的根節(jié)點。在一開始的情況下，這個節(jié)點是完整的樹結(jié)構(gòu)（self.root）。_subtreeInsert將會同時包含執(zhí)行插入的操作，以及會返回可以被用來當(dāng)作結(jié)果的（子）樹的根節(jié)點。這種方法能夠確保我們的插入（insert）操作即使面對的是最初的空樹也能工作。因為，在這種情況下，self.root在開始的時候是None（表示空樹），而在_subtreeInsert返回了包含這個item（元素）的TreeNode之后，這個節(jié)點就會成為這個樹的新的根節(jié)點。
現(xiàn)在，讓我們來編寫遞歸的輔助函數(shù)_subtreeInsert吧。函數(shù)的參數(shù)為我們提供了元素需要被插入的樹結(jié)構(gòu)的根節(jié)點，在最后，這個函數(shù)還需要返回結(jié)果樹的根節(jié)點。整個算法非常簡單：如果這個（子）樹是空的，我們只需返回包含這個元素的TreeNode就行了。而如果這個樹不為空的話，我們遞歸地把這個元素添加到（相應(yīng)的）左子樹或者右子樹里就行了，然后返回這個樹的根節(jié)點來作為新樹的根節(jié)點（因為這個節(jié)點沒有被改變）。下面是完成這些相應(yīng)工作的代碼：
def _subtreeInsert(self, root, item):
if root is None: # inserting into empty tree
return TreeNode(item) # the item becomes the new tree root
if item == root.item:
raise ValueError("Inserting duplicate item")
if item < root.item: # modify left subtree
root.left = self._subtreeInsert(root.left, item)
else: # modify right subtree
root.right = self._subtreeInsert(root.right, item)
return root # original root is root of modified tree
到目前為止，我們可以創(chuàng)建一個BST對象并且添加元素到這個對象里了。因此，我們能夠使用某種方法來查找樹里的元素了。我們曾經(jīng)討論過基本的搜索算法，在這個算法里應(yīng)該能夠很容易地實現(xiàn)。因為它只需要一個循環(huán)來從根節(jié)點向下遍歷整個樹，直到找到這個目標(biāo)元素或者到達整個樹的底部：
def find(self, item):
""" Search for item in BST
post: Returns item from BST if found, None otherwise"""
node = self.root
while node is not None and not(node.item == item):
if item < node.item:
node = node.left
else:
node = node.right
if node is None:
return None
else:
return node.item
你可能會想知道為什么這個方法會從樹結(jié)構(gòu)里返回元素，而不是僅僅返回一個布爾值來表示找到了這個元素。這是為了簡單起見，目前為止我們所用的所有插圖都使用了數(shù)字來代表數(shù)據(jù)值。然而，我們可以在二叉搜索樹里存儲任意類型的對象，對這個類型唯一的要求是對象具有可比性。一般來說，兩個對象可能相等（==），但它們不一定是相同的。稍后，我們將會看到如何利用這個屬性，來將我們的BST轉(zhuǎn)換為類似于字典的對象。
為了抽象數(shù)據(jù)類型的完整，我們還應(yīng)該在BST類里添加一個用來刪除元素的方法。從二叉搜索樹中刪除特定元素有點麻煩，我們有很多不同的情況需要考慮。讓我們從簡單的情況開始：如果要刪除的節(jié)點是葉節(jié)點，我們可以簡單地通過把它的父節(jié)點里的引用設(shè)置為None來將這個節(jié)點從樹結(jié)構(gòu)里刪除。但是，如果要刪除的節(jié)點有子節(jié)點應(yīng)該怎么辦？如果這個需要被刪除的節(jié)點只有一個子節(jié)點的話，我們需要做的工作仍然很簡單。我們可以簡單地在被刪除節(jié)點的父節(jié)點里把用來指向它的引用設(shè)置為它的子節(jié)點就行了。圖7.7所示為被刪除節(jié)點的左子節(jié)點被提升到了它的父節(jié)點的左子節(jié)點的情況。你可能也希望研究下其他只有單個子節(jié)點的情況（還有3個）來向自己證明，這個方式是正確的。
圖7.7 從二叉搜索樹中刪除4
現(xiàn)在，我們繼續(xù)討論被刪除的節(jié)點有兩個子節(jié)點的情況，這個時候應(yīng)該怎么做呢？我們不能隨便選任意一個子節(jié)點來占據(jù)被刪除節(jié)點的位置，因為這可能會讓另一個子節(jié)點的鏈接出現(xiàn)問題。這種困境的一個解決方案是：因為我們需要一個節(jié)點來維護整個樹的結(jié)構(gòu)，所以就簡單地把這個節(jié)點留在那里就行了。我們可以通過替換節(jié)點里的數(shù)據(jù)，而不是刪除這個節(jié)點來達到這個目標(biāo)。因此，我們只需要找到一個可以被方便地刪除的節(jié)點，然后把這個節(jié)點的值傳輸?shù)侥繕?biāo)節(jié)點里；與此同時，讓這個樹還能夠保持樹的二分查找屬性。
讓我們來考慮圖7.8中左邊的這個樹。假設(shè)我們要從這個樹里刪除6。這個樹里還有什么值可以被放在這個位置呢？可以發(fā)現(xiàn)，如果在這個節(jié)點里放置5或7的話，這個二叉搜索樹將會繼續(xù)保持二分查找屬性。一般來說，將被刪除節(jié)點里的元素替換為其直接前序節(jié)點或者直接后序節(jié)點都是正確的操作，這是因為，這些節(jié)點里的值都保證了這個節(jié)點與樹里的其余節(jié)點的關(guān)系保持相同。假設(shè)我們決定使用直接前序，那么，我們將會把這個值放入被刪除的節(jié)點里，然后從樹里刪除這個前序節(jié)點就行了。這樣的操作，將會讓我們得到圖7.8右邊所展示的樹。
圖7.8 從二叉搜索樹中刪除6
在這個時候，你可能會擔(dān)心如何刪除這個前序節(jié)點。難道這個操作不是和刪除原來那個需要被刪除的節(jié)點一樣，還是那么難嗎？幸運的是，事實上，并不會這么困難。前序節(jié)點里的值始終是需要被刪除的節(jié)點的左子樹里的最大值。很明顯，要找到二叉搜索樹里包含最大值的節(jié)點，我們只需要沿著樹，并且始終選擇右子樹那個鏈接就行了。當(dāng)我們用完了所有的鏈接之后，我們就會停在最大節(jié)點上。這也就意味著：前序節(jié)點必然有一個空的右子樹。因此，我們總是可以通過簡單地提升它的左子樹來刪除這個節(jié)點。
我們將再次使用在子樹上的遞歸來實現(xiàn)這個算法。我們的方法將與之前一樣只包含對遞歸輔助函數(shù)的調(diào)用：
def delete(self, item):
"""remove item from binary search tree
post: item is removed from the tree"""
self.root = self._subtreeDelete(self.root, item)
_subtreeDelete方法將會是實現(xiàn)刪除算法的核心。它也必須返回被刪除元素的子樹的根節(jié)點：
def _subtreeDelete(self, root, item):
if root is None: # Empty tree, nothing to do
return None
if item < root.item: # modify left
root.left = self._subtreeDelete(root.left, item)
elif item > root.item: # modify right
root.right = self._subtreeDelete(root.right, item)
else: # delete root
if root.left is None: # promote right subtree
root = root.right
elif root.right is None: # promote left subtree
root = root.left
else:
# overwrite root with max of left subtree
root.item, root.left = self._subtreeDelMax(root.left)
return root
如果你能夠把樹結(jié)構(gòu)理解為遞歸結(jié)構(gòu)的話，這段代碼對你來說應(yīng)該不太難理解。這個算法里，如果需要被刪除的元素是在左子樹或者右子樹里，我們將會遞歸調(diào)用_subtreeDelete方法來生成修改后的子樹。當(dāng)（子）樹的根節(jié)點是這個需要被刪除的節(jié)點的時候，我們將需要處理3種可能的情況：提升右子樹、提升左子樹，或者用前序節(jié)點的元素來替換當(dāng)前元素。最后一種情況實際上可以用另一個遞歸方法_subtreeDelMax來處理。這個方法將會查找這個樹的最大值，然后刪除包含這個值的節(jié)點。這個方法可以像下面的代碼片段這樣來實現(xiàn)：
def _subtreeDelMax(self, root):
if root.right is None: # root is the max
return root.item, root.left # return max and promote left subtree
else:
# max is in right subtree, recursively find and delete it
maxVal, root.right = self._subtreeDelMax(root.right)
return maxVal, root
7.5.3 遍歷整個二叉搜索樹（BST）
現(xiàn)在，我們已經(jīng)對一組元素進行了有用的抽象。我們可以向這個集合里添加元素，查找它們，并且刪除它們；缺少的只是一些用來迭代這個集合的簡單方法。鑒于二叉搜索樹的組織方式，中序遍歷會非常實用，因為它將能夠按照順序來輸出各個元素。然而，我們的BST類的用戶在編寫自己的遍歷算法的時候，并不需要知道這個數(shù)據(jù)結(jié)構(gòu)的內(nèi)部細(xì)節(jié)。好在，我們有多種可能的方法來實現(xiàn)這一目標(biāo)。
一種方法是編寫簡單的遍歷算法，將整個樹里的元素重新組裝成某種序列的形式，比如可以組裝成列表或者是隊列。我們可以通過編寫遞歸中序遍歷這個算法來輕松地生成Python列表。這里的代碼為BST類提供了asList方法：
def asList(self):
"""gets item in in-order traversal order
post: returns list of items in tree in orders"""
items = []
self._subtreeAddItems(self.root, items)
return items
def _subtreeAddItems(self, root, itemList):
if root is not None:
self._subtreeAddItems(root.left, itemList)
itemList.append(root.item)
self._subtreeAddItems(root.right, itemList)
輔助函數(shù)_subtreeAddItems在這里執(zhí)行的是樹的標(biāo)準(zhǔn)的中序遍歷，其中對元素的處理只需要把這個元素附加到itemList。你可以比較一下這段代碼和7.2節(jié)里的通用遍歷算法，從而加深對遍歷算法的理解。我們的asList方法只需創(chuàng)建一個初始列表，然后通過調(diào)用_subtreeAddItems來填充這個列表。通過添加這個方法，我們可以輕松地將BST對象轉(zhuǎn)換為有序列表。當(dāng)然，這也就意味著我們可以通過它來遍歷集合中的所有元素。例如，我們可以按照下面這段代碼來順序輸出BST對象里的內(nèi)容：
for item in myBST.asList():
print item
這個遍歷二叉搜索樹的方案唯一真正的問題在于，它產(chǎn)生的列表和原本的集合是一樣大的。如果這個集合很大，而同時我們也只是想找到一種能夠循環(huán)所有元素的方法，那么生成另一個相同大小的集合并不會是一個很好的主意。
另一個方案是：使用一個被稱為訪問者模式（visitor pattern）的設(shè)計模式來實現(xiàn)。這種模式的思路是：容器將會提供一個方法，這個方法能夠遍歷整個數(shù)據(jù)結(jié)構(gòu)，并且在每個節(jié)點上都能夠執(zhí)行一些客戶端請求的功能。在Python里，我們可以通過一個將任意函數(shù)作為參數(shù)的方法來實現(xiàn)這個模式，這個方法將會把這個函數(shù)應(yīng)用到樹結(jié)構(gòu)里的每個節(jié)點。我們還是使用一個遞歸的輔助方法來實際執(zhí)行整個遍歷過程：
def visit(self, f):
"""perform an in-order traversal of the tree
post: calls f with each TreeNode item in an in-order traversal
order"""
self._inorderVisit(self.root, f)
def _inorderVisit(self, root, f):
if root is not None:
self._inorderVisit(root.left, f)
f(root.item)
self._inorderVisit(root.right, f)
可以看到，這段代碼里，f代表著客戶端想要應(yīng)用于BST對象里的每一個元素的任意函數(shù)。這個函數(shù)通過f(root.item)這一行代碼來執(zhí)行。與之前一樣，這段代碼只是我們的通用遞歸遍歷算法的一個變體而已。
要使用visit方法，我們只需要構(gòu)造一個適用于每個元素的函數(shù)。比如，假設(shè)我們?nèi)匀幌氚凑枕樞騺磔敵稣麄€BST的內(nèi)容，我們現(xiàn)在可以通過訪問者模式來完成：
def prnt(item):
print item
...
myBST.visit(prnt)
這里需要注意的一件事是，在調(diào)用visit方法的時候，prnt后面并沒有跟上一對括號。只有在我們真正單獨調(diào)用這個函數(shù)的時候，才需要加上這對括號。而在此刻，調(diào)用visit方法的時候，我們實際上并沒有直接調(diào)用prnt函數(shù)，而是將這個函數(shù)對象本身傳遞給了將會實際執(zhí)行調(diào)用的visit方法。
訪問者模式為客戶端代碼提供了一種很好的方式來執(zhí)行容器的遍歷，而且還包含了一個不需要查看細(xì)節(jié)的抽象屏障。但是編寫一個恰當(dāng)?shù)暮瘮?shù)來進行處理，在有些時候會很麻煩，并且這樣的代碼并不是很像Python的風(fēng)格。與我們的其他容器類一樣，Python里的理想解決方案是：使用Python的生成器機制來為我們的BST類定義一個迭代器。它的基本思路是：我們將只需要編寫一個通用的中序遍歷，然后一次一個地yield樹結(jié)構(gòu)里的元素。在這個時候，你肯定已經(jīng)非常清楚這段代碼應(yīng)該怎么寫了：
def __iter__(self):
"""in-order iterator for binary search tree"""
return self._inorderGen(self.root)
def _inorderGen(self, root):
if root is not None:
# yield all the items in the left subtree
for item in self._inorderGen(root.left):
yield item
yield root.item
# yield all the items from the right subtree
for item in self._inorderGen(root.right):
yield item
這段代碼唯一與之前不一樣的地方是生成器函數(shù)的遞歸形式。記住，當(dāng)你調(diào)用生成器的時候，你并沒有立刻獲得這個元素，而是獲得了一個按需提供元素的迭代器對象。例如，為了從左子樹里實際得到元素，我們必須要遍歷self._inorderGen(root.left)提供的迭代器，然后輸出每一個元素。
這樣一來，就有了一個可以非常方便地迭代我們的BST容器的方法了。我們按照順序來輸出所有元素的代碼不能更簡單了：
for item in myBST:
print item
順便說一句，既然我們有一個BST類的迭代器，那么我們就不再需要單獨的asList方法了。Python可以通過代碼list(myBST)來使用迭代器從BST對象中生成整個元素的列表。如果能夠創(chuàng)建包含BST里所有元素的列表，在為BST類編寫單元測試的時候?qū)貏e方便，因為它提供了一種在斷言里檢查樹結(jié)構(gòu)的內(nèi)容的簡單方法。當(dāng)然，從BST對象中獲得的有序列表并不能保證樹結(jié)構(gòu)具有正確的形式。為了保證樹結(jié)構(gòu)的正確，用另一種遍歷方法（前置或后置）將會提供不少幫助。通過檢查兩個不同的遍歷序列來推導(dǎo)出二叉樹的真實結(jié)構(gòu)是可行的，因此如果兩個遍歷都正確的話，那么我們就知道樹的結(jié)構(gòu)與我們所期望的結(jié)構(gòu)是相同的了。
7.5.4 二叉搜索樹（BST）的運行時分析
在這一部分內(nèi)容的介紹里，我們提到了二叉搜索樹可以非常高效地維護有序集合。我們已經(jīng)展示了二叉搜索樹是如何為我們提供有序集合的了，但是我們還沒有仔細(xì)檢查各個操作的運行時效率。由于許多和樹結(jié)構(gòu)相關(guān)的算法都是通過遞歸來編寫的，因此分析它們可能會看起來比較麻煩。但是，如果我們只考慮底層結(jié)構(gòu)里發(fā)生的事情的話，那么，分析起來就很容易了。
讓我們先從遍歷整個樹的操作開始考慮。由于我們在每個節(jié)點上必須要完成的工作量是不變的，因此遍歷的時間與樹里的節(jié)點的數(shù)量是成正比的，也就是集合中的元素數(shù)量。因此，那些操作的時間復(fù)雜度將會是Θ (n)，其中n是集合的大小。
對于只會檢查樹的一部分（例如，搜索、插入以及刪除）的算法，我們的分析將會取決于樹結(jié)構(gòu)的形狀。所有的這些方法的最壞情況都需要走一條從樹的根節(jié)點到其“底部”的路徑。很明顯，這樣做所需的步驟數(shù)量將和樹的高度成正比。于是，一個有趣的問題出現(xiàn)了，一個二叉樹有多高？顯然，這取決于樹結(jié)構(gòu)的確切形狀。如果我們假設(shè)這個樹是按照排序的順序來插入的一組數(shù)字的話，這個樹將會是一個鏈表，這是因為每個節(jié)點都被添加為前一個數(shù)字的右子節(jié)點。對于具有n個元素的樹結(jié)構(gòu)來說，插入需要n步才能到達樹的底部。
如果樹結(jié)構(gòu)里的數(shù)據(jù)分布得很好的話，那么我們可以估計：對于任意給定的子樹來說，都有大約一半的元素位于它的左子樹，而剩下的大約一半的元素位于右子樹。我們稱這樣的樹為“平衡”樹。相對平衡的樹將具有l(wèi)og2n的近似高度。在這種情況下，必須在樹中找到特定的節(jié)點的操作將會有Θ (lgn)的復(fù)雜度。好在，如果數(shù)據(jù)是按照隨機的方式插入樹里的話，那么當(dāng)我們從根節(jié)點向下執(zhí)行的時候，對于每一個節(jié)點來說，這個元素具有同樣的可能性進入左子樹或者右子樹。平均來說，這個結(jié)果將會是一個非常平衡的樹。
在實踐中，只要注意插入和刪除數(shù)據(jù)的順序，二叉搜索樹通常都將會提供非常好的性能。對于特別偏執(zhí)的人來說，有一些非常有名的技術(shù)（見13.3節(jié)）可以被用來實現(xiàn)二叉樹，從而保證在插入和刪除操作之后，樹結(jié)構(gòu)依然平衡。
7.6 使用二叉搜索樹（BST）來實現(xiàn)映射（選讀）
上一節(jié)里，我們描述了如何讓BST對象實現(xiàn)類似于有序集合的實現(xiàn)。因此，我們可以插入元素、刪除元素、檢查元素是否存在，以及按照排序順序來獲取里面的元素。樹結(jié)構(gòu)通常來說會在類似于數(shù)據(jù)庫的應(yīng)用程序里被用到。在這樣的程序里，我們不僅會想要知道特定的元素是不是在集合里，而且還要能夠查找出具有某些特定表征的元素。舉一個簡單的例子，我們可能會需要維護俱樂部會員的名單。很明顯，我們需要能夠添加和刪除俱樂部的成員，但我們還需要更多的東西。比如，我們需要一種可以用來為俱樂部的特定成員提供記錄的方法，例如獲取他們的電話號碼。
在這一節(jié)里，我們將會了解如何擴展二叉搜索樹的功能，來實現(xiàn)類似于Python字典那樣通用的映射。在我們的成員列表示例中，我們使用了由成員名稱構(gòu)造的特殊“鍵”值，從而能夠查找它的數(shù)據(jù)記錄。假設(shè)我們有一個合適的membershipList對象，我們可以通過下面這些代碼得到一個人的電話號碼：
...
info = membershipList["VanRossum, Guido"]
print info.home_phone
在這里，我們的membershipList是一個映射對象，它把成員的名稱和他的具體信息的相應(yīng)記錄進行了映射。我們可以使用Python字典來完成這項任務(wù)，但是字典是一種無序的映射。而且，我們也還希望能夠按照一定的順序來高效地輸出我們的（巨大的！）成員列表。
解決這個問題的一種方案是重寫整個BST類，從而能夠讓它的所有方法都有一個額外的參數(shù)，這個參數(shù)被用來獲取鍵。同時，這些方法還需要在執(zhí)行的過程中維護這個鍵值對組成的樹結(jié)構(gòu)。雖然，這比我們真正需要做的工作要多得多，我們還是可以通過使用現(xiàn)有的BST類來實現(xiàn)。我們可以通過一個包裝這個類的包裝器來實現(xiàn)通用映射接口，從而獲得類似的效果。這樣一來，我們在獲得基于樹結(jié)構(gòu)的映射對象的優(yōu)點時，不需要去修改BST類或者復(fù)制出另外一個BST類。一般來說，只要有可能，我們都應(yīng)該擴展現(xiàn)有的代碼，它通常會比復(fù)制或修改現(xiàn)有代碼的效果更好。
那么我們?nèi)绾螌⑦@個BST類從一個集合轉(zhuǎn)變?yōu)橛成淠兀窟@里的關(guān)鍵是利用BST類里已經(jīng)包含了的現(xiàn)成的排序和查找功能。我們的BST類可以被用來存儲任何可以被比較的對象。我們將會把集合里的元素存儲為鍵值對，但訣竅是這些元素將會根據(jù)它的鍵進行排序。因此，第一步是創(chuàng)建一個新的類來表示這些鍵值對元素。我們將這個組合元素稱為KeyPair。同時，為了使我們的KeyPair類可以被比較，我們還需要實現(xiàn)一些與比較相關(guān)的操作。
# KeyPair.py
class KeyPair(object):
def __init__(self, key, value=None):
self.key = key
self.value = value
def __eq__(self, other):
return self.key == other.key
def __lt__(self, other):
return self.key < other.key
def __gt__(self, other):
return self.key > other.key
在這里，我們只實現(xiàn)了6個比較運算符中的3個，這是因為BST類里的所有方法都只會用到這些比較運算符。當(dāng)然，為了安全起見，以防將來BST類的代碼發(fā)生變化，我們還是應(yīng)該盡量地去實現(xiàn)其他3個比較運算符。我們將會把這部分內(nèi)容作為練習(xí)題留給你。
有了這個KeyPair類之后，我們現(xiàn)在就可以定義一個基于BST類的字典映射了。這是我們的類的構(gòu)造函數(shù)：
# TreeMap.py
from BST import BST
from KeyPair import KeyPair
class TreeMap(object):
def __init__(self, items=()):
self.items = BST()
for key, value in items:
self.items.insert(KeyPair(key, value))
在這段代碼里，我們使用了實例變量items來保存將會被用來儲存我們的KeyPair元素的BST對象。正如Python字典可以使用一個序列對其進行初始化一樣，我們也允許TreeMap類的構(gòu)造函數(shù)接受一個序列對。對于這個參數(shù)，我們只需要遍歷這些數(shù)據(jù)對，然后調(diào)用BST類的insert操作來填充我們的樹。當(dāng)然，insert方法將會根據(jù)鍵的數(shù)據(jù)來保持底層二叉搜索樹的順序，而這正是因為我們?yōu)镵eyPair類實現(xiàn)了相互比較的方法。
一旦KeyPair對象進入到了我們的BST對象，我們需要能夠通過它的鍵的數(shù)據(jù)來再次檢索它。這時，我們可以使用BST類的find操作來完成這個任務(wù)。我們將會提供給find操作的參數(shù)是一個新的KeyPair對象，它將會等同于我們正在查找的KeyPair（具有相同的鍵）。因此，像下面這樣的一行代碼，就能夠解決這個問題：
result = self.items.find(KeyPair(key))
要記住，find操作會在二叉搜索樹中搜索相等（==）的目標(biāo)元素。這時，KeyPair(key)將會和BST中具有相同鍵的鍵值對相“匹配”，從而返回這個匹配的KeyPair對象。因此，我們只需要填寫鍵值對的鍵這部分?jǐn)?shù)據(jù)，就能夠檢索這個鍵的實際記錄了。
為了使我們的TreeMap類能夠像Python字典一樣地工作，我們還需要實現(xiàn)Python里用來進行索引操作的常用鉤子函數(shù)：__getitem__和__setitem__。
def __getitem__(self, key):
result = self.items.find(KeyPair(key))
if result is None:
raise KeyError()
else:
return result.value
def __setitem__(self, key, item):
partial = KeyPair(key)
actual = self.items.find(partial)
if actual is None:
# no pair yet for this key, add one
actual = partial
self.items.insert(actual)
actual.value = item
當(dāng)給定的鍵沒有出現(xiàn)在字典里的時候，這些方法都會需要一些額外的工作來處理這個特殊的情況。在這種情況下，__getitem__方法會拋出KeyError異常。但是，當(dāng)__setitem__得到一個新的鍵的時候，它需要將一個新的KeyPair對象插入到BST對象里去。然而，由于我們已經(jīng)在一開始就創(chuàng)建了新的KeyPair對象partial來進行初始搜索，因此把它用來設(shè)置一個新條目將會是一件簡單的事情。
這些代碼就足夠讓我們的TreeMap類啟動并且運行了。當(dāng)然，這個類仍然缺少允許我們按順序來訪問所有元素的迭代器（如用來輸出所有成員的列表）。我們將會把添加這些功能作為練習(xí)題留給你來完成。
7.7 小結(jié)
我們在這一章里介紹了一些用來實現(xiàn)樹結(jié)構(gòu)的基本算法和相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。以下是關(guān)于這些重要亮點的總結(jié)。
- 樹是一個非線性的容器類，它可以被用來存儲分層數(shù)據(jù)或者存儲有組織的線性數(shù)據(jù)，從而能夠有效地去訪問它們。
- 樹結(jié)構(gòu)通常使用鏈?zhǔn)浇Y(jié)構(gòu)來進行存儲，但是它也可以被存儲在數(shù)組里。
- 許多使用樹結(jié)構(gòu)的應(yīng)用程序都使用的是二叉樹，它代表著每個節(jié)點都有零個、一個或兩個子節(jié)點。當(dāng)然，也可以實現(xiàn)具有任意數(shù)量子節(jié)點的樹。
- 二分查找屬性是指，對于每一個節(jié)點，它的左子樹中的每一個節(jié)點的值都會小于或等于當(dāng)前節(jié)點的值；它的右子樹中的每一個節(jié)點的值將會大于當(dāng)前節(jié)點的值。
- 二叉搜索樹的搜索、插入和刪除操作都支持Θ (lgn)時間復(fù)雜度的實現(xiàn)，并且，這些操作還能同時保持每個節(jié)點的二分查找屬性。
- 樹的相關(guān)算法通常都會使用遞歸來編寫，這是因為樹本身就是一個遞歸數(shù)據(jù)結(jié)構(gòu)。
- 3個常見的二叉樹遍歷順序為：前序、中序和后序。二叉搜索樹的中序遍歷將會按照排序的順序來輸出元素。
本文摘自《數(shù)據(jù)結(jié)構(gòu)和算法（Python和C++語言描述）》
