【文章內(nèi)容簡介】 如果用布爾數(shù)組 x存放 x0, x1,…, x n1，則借助例 BinaryAddOne的思想，可生成 n個變量的 2n種取值組合。 計算公式的值可通過后序遍歷相應的二叉樹實現(xiàn)。 為便于得到變量當前取值，樹的葉結點改為存放變量的下標。如下一頁所示。 JYP 56 JYP 57 為了簡化設計，分別用 – 3， –2和 –1表示 ?， ?和 ?，于是樹結點和樹可定義如下： enum Boolean {FALSE, TRUE}。 class SatTree。 // 向前聲明 class SatNode { friend class SatTree。 private: SatNode *LeftChild。 int data。 SatNode * RightChild。 }。 JYP 58 class SatTree { public: Boolean Satisfiability( )。 // 公式可滿足則返回 TRUE，并打 // 印變量的取值組合，否則返回 FALSE private: SatNode *root。 Boolean *x。 int n。 // 變量個數(shù) Boolean PostOrderEval(SatNode *)。 Boolean NextCombination( )。 }。 JYP 59 函數(shù) NextCombination生成變量的下一個取值組合，當變量取值已全部為 TRUE時，返回 FALSE，否則返回 TRUE。 Boolean SatTree::NextCombination( ) { int i = n1。 while (x[i] = = TRUE amp。amp。 i = 0) { x[i] = FALSE。 i。 } if ( i = 0 ) { x[i] = TRUE。 return TRUE。 } else return FALSE。 // 變量取值已經(jīng)全部為 TRUE } JYP 60 函數(shù) Satisfiability 對 x=(FALSE, FALSE, … , FALSE)， 計算公式的值 ， 若為 TRUE則成功返回 。否則繼續(xù)生成下一個取值組合 ， 直到計算完取值組合 (TRUE, TRUE, … , TRUE)為止 。 Boolean SatTree::Satisfiability( ) { int i。 x = new Boolean[n]。 for (i = 0。 i n。 i++) x[i] = FALSE。 do { // 由于 n≥1，所以此循環(huán)至少迭代 2次 if (PostOrderEval(root) == TRUE) { for (i = 0。 i n。 i++) cout x[i]。 // 輸出取值組合 delete [ ] x。 x = 0。 return TRUE。 // 滿足 } } while (NextCombination( ))。 JYP 61 delete [ ] x。 x = 0。 return FALSE。 // 不可滿足 } JYP 62 函數(shù) PostOrderEval后序遍歷計算公式的值。 Boolean SatTree::PostOrderEval(SatNode *s) { Boolean leftValue, rightValue。 if (s) { leftValue = PostOrderEval(s?LeftChild)。 rightValue = PostOrderEval(s?RightChild)。 switch (s?data) { case 3: return ! rightValue。 // 操作符 ? case 2: return leftValue amp。amp。 rightValue。 // 操作符 ? case 1: return leftValue || rightValue。 // 操作符 ? default: return x[s?data]。 // 變量下標 } } return FALSE。 // 空樹的值為 FALSE } JYP 63 由于有 2n種取值組合，每次計算公式的時間為O(n)，生成下一個取值組合的平均時間為 O(1)，所以最壞情況下，算法的時間復雜性是 O(n2n)。 作業(yè)： P149—9 JYP 64 線索二叉樹 線索 在二叉樹的鏈接表示中， 0指針的個數(shù)為 2n0 + n1 = n + 1，占總指針數(shù) 2n的一半還多。 可用一種稱為 線索 的指向樹中其它結點的指針取代 0指針。這些線索的構造規(guī)則為： （ 1） 若結點 p的 RightChild字段值為 0，則令其指向p的中序后繼； （ 2） 若結點 p的 LeftChild字段值為 0，則令其指向 p的中序前趨。 將二叉樹中的 0指針替換為線索（用虛線表示）后得到 線索二叉樹 。 JYP 65 下面是一個線索二叉樹的例子，其中結點 E的左線索和右線索分別指向其中序前趨 B和中序后繼 A。 圖 JYP 66 為了區(qū)分線索和普通指針，在結點中增加兩個Boolean字段： ? LeftThread ? RightThread 對于結點 t，若 t?LeftThread == TRUE，則t?LeftChild存放線索，否則存放左子女指針。 右子女情況也類似。 JYP 67 線索二叉樹及其結點和中序游標的類定義： class ThreadedTree。 class ThreadedInorderIterator。 class ThreadedNode { friend class ThreadedTree。 friend class ThreadedInorderIterator。 private: Boolean LeftThread。 ThreadedNode * LeftChild。 char data。 ThreadedNode * RightChild。 Boolean RightThread。 }。 JYP 68 class ThreadedTree { friend class ThreadedInorderIterator。 public: // 樹操作 … private: ThreadedNode *root。 }。 JYP 69 class ThreadedInorderIterator { public: char *Next( )。 void Inorder( )。 ThreadedInorderIterator(ThreadedTree tree):t(tree) {CurrentNode = 。}。 private: ThreadedTree t。 ThreadedNode *CurrentNode。 }。 JYP 70 由于中序第一結點沒有前趨，最后一個結點沒有后繼，致使這兩個結點的左、右線索無定義，如圖 H和 G所示。 為此，引入一個頭結點，使原樹作為其左子樹，并使頭結點的 RightChild作為普通指針指向其本身。 圖 。 JYP 71 圖 : JYP 72 不難看出，原樹的中序 第一個結點 是頭結點的后繼， 最后一個結點 是頭結點的前趨。 JYP 73 中序遍歷線索二叉樹 通過線索，可以不用?；蜻f歸實現(xiàn)中序遍歷。 對于二叉樹的任何結點 x，若x?RightThread == TRUE，則 x的中序后繼是 x?RightChild。 否則， x的中序后繼可沿 x的右子女的 LeftChild鏈尋找，找到字段LeftThread == TRUE的結點即可。如圖所示。 x JYP 74 函數(shù) Next返回線索二叉樹中結點 CurrentNode的中序后繼： char *ThreadedInorderIterator::Next( ) { ThreadedNode *temp = CurrentNode?RightChild。 if (! CurrentNode?RightThread) while (!temp?LeftThread) temp = temp?LeftChild。 CurrentNode = temp。 if (CurrentNode == ) return 0。 // 頭結點 else return amp。CurrentNode?data。 } JYP 75 利用 Next函數(shù) ， 并注意到原樹的中序第一個結點是頭結點的后繼 ， 很容易得到線索二叉樹的中序遍歷函數(shù) Inorder： void ThreadedInorderIterator::Inorder( ) { CurrentNode = 。 for (char *ch = Next( )。 ch。 ch = Next( )) // 注意，當 // CurrentNode == , Next()返回中序第一元素 cout *ch endl。 } 由于每個結點最多被訪問兩次，所以對于 n個結點的線索二叉樹，中序遍歷的計算時間是 O(n)。 JYP 76 作業(yè)： P150—17 JYP 77 將結點插入 線索二叉樹 插入結點是構造線索二叉樹的主要途徑。 此處將只研究將結點 r作為結點 s的右子女插入的情況。這又分兩種情況： （ 1） s的右子樹為空，插入比較簡單，如下圖： JYP 78 （ 2） s的右子樹不空，插入后該右子樹成為 r的右子樹。 s原來的中序后繼變?yōu)?r的中序后繼，如下圖： JYP 79 假設函數(shù) InorderSucc(r)返回 r的中序后繼，函數(shù)InsertRight實現(xiàn)了上述插入過程： void ThreadedTree::InsertRight(ThreadedNode *s, ThreadedNode *r) { // r作為 s的右子女插入 r?RightChild = s?RightChild。// 見前圖 (1) ，注意 s != r?RightThread = s?RightThread。 r?LeftChild = s。 r?LeftThread = TRUE。 // 見前圖 (2) s?RightChild = r。 s?RightThread = FALSE。 // 見前圖 (3) if (!r?RightThread) { ThreadedNode *temp = InorderSucc(r)。 // 見前圖 (4) temp?LeftChild = r。 } } JYP 80 選擇樹 歸并段 是記錄的有限序列，且這些記錄按關鍵字的非遞減順序排列。 假設需要將 k個歸并段歸并為一個，這可通過反復輸出關鍵字最小的記錄完成。 最小關鍵字可能在 k個歸并段的前端記錄的任何一個之中，因此需要從 k種可能中選出最小。最直接的方法是作 k – 1次比較。但對于 k 2，如果利用上一次比較獲得的知識，就可以使本次及以后比較的次數(shù)減少。 選擇樹就是一種能夠記載上一次比較獲得的知識的數(shù)據(jù)結構。 選擇樹 是一棵完全二叉樹，有 勝者樹和 敗者樹 兩種。 JYP 81 勝者樹 勝者樹的構造與 錦標賽 類似，勝者是關鍵字較小的記錄。每個非葉結點表示比賽的勝者，根結點表示總勝者，即樹中關鍵字最小的結點。 作為完全樹，勝者樹可用順序方法表示。每個葉結點表示相應歸并段的第一個記錄。 由于記錄一般較大，每個結點實際存放的是其所表示記錄的緩沖區(qū)下標。 設 buf[i]存放歸并段 i（ 0≤i k）的第一個記錄，則buf[i]對應的葉結點編號是 k + i，這意味著葉結點存放的下