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