【正文】 此樹的帶權(quán)路徑長度 WPL = 375 + 82 + 169 + 18 = 644。設內(nèi)結(jié)點個數(shù)為 n4，外結(jié)點個數(shù)為 n0，則可證明有關(guān)系 n0 = 3 * n4 + 1。 622 假定用于通信的電文僅由 8個字母 c1, c2, c3, c4, c5, c6, c7, c8 組成 , 各字母在電文中出現(xiàn)的頻率分別為 5, 25, 3, 6, 10, 11, 36, 4。 試問利用樹的先根次序遍歷結(jié)果和后根次序遍歷結(jié)果能否唯一確定一棵樹 ? 舉例說明。 39。 【解答】 template class Type void BinaryTreeType :: Double_order ( BinTreeNodeType *current ){ if ( current != NULL ) { cout currentdata 39。 case 1 : V[i].llink = i + 1。 } break。 } break。 i++ ) { switch ( U[i].ltag ) { case 0 : switch ( U[i].rtag ) { case 0 : V[i].llink = V[i].rlink = 1。 } } (2) 森林的雙標記先根次序表示向左子女 右兄弟鏈表先根次序表示的轉(zhuǎn)換 void staticlinkListType :: DtagFLchRsibF ( ) { Stackint st。 //存儲左子女 右兄弟鏈表的向量 DoublyTagNode Type *U。 //結(jié)點數(shù)據(jù) int llink, rlink。如果我們采用靜態(tài)二叉鏈表作為森林的存儲表示，同時按森林的先根次序依次安放森林的所有結(jié)點，則可以在它們的結(jié)點中用只有一個二進位的標志 ltag 代替 llink，用 rtag代替 rlink。 ConstructTree ( T, n, 2*i+2, ptrrightChild )。利用引用型參數(shù) ptr 將形參的值帶回實參。 //以數(shù)組建立一棵二叉樹 delete [ ] A。 for ( int i = 0。 t ) { int n。試設計一個算法，從 T[0]開始順序讀出各結(jié)點的值，建立該二叉樹的二叉鏈表表示。 if ( prightChild ==NULL ) q 無后繼 。 qrightThread == 1? = ≠ qrightChild == NULL ? = q 無后繼 ≠ q 的后繼為 qrightChild q 的后繼為 q 的右子樹中中序下的第一個結(jié)點 qleftThread == 0 ? = q 的后繼為 qleftChild ≠ qrightThread == 0 ? = q 的后繼為 qrightChild ≠ p = q。 找 q 的右子樹中在中序下的第一個結(jié)點的程序為： p = qrightChild。 exchange ( ptrrightChild )。 if ( ptrleftChild != NULL || ptrrightChild != NULL ) { temp = ptrleftChild。amp。 69 若用二叉鏈表作為二叉樹的存儲表示，試針對以下問題編寫遞歸算法： (1) 統(tǒng)計二叉樹中葉結(jié)點的個數(shù)。 【解答】 總結(jié)點數(shù) n = n0 + n1 + n2 + … + nm 總分支數(shù) e = n1 = n0 + n1 + n2 + … + nm1 = m*nm + (m1)*nm1 + … + 2*n2 + n1 則有 1)1(20 ??????? ?? ??mi inin 68 試分別找出滿足以下條件的所有二叉樹 : (1) 二叉樹的前序序列與中序序列相同 。 out, BinaryTreeTypeamp。 in, BinaryTreeTypeamp。 item )。 } BinTreeNodeType * RighttChild ( BinTreeNodeType *current ) { return current != NULL ? currentrightChild : NULL。 } void SetRight ( BinTreeNodeType *R ){ RightChild =R。 } BinTreeNodeType* GetRight ( ) const { return rightChild。 public: BinaryTree ( ) : root ( NULL ) { } BinaryTree ( Type value ) : RefValue ( value ), root ( NULL ){ } ~BinaryTree ( ) { destroy (root)。 item ) const。 BinTreeNodeType *Parent ( BinTreeNodeType *start, BinTreeNodeType *current )。 【解答】 include template class Type class BinaryTree { private: template class Type class BinTreeNode { public: BinTreeNodeType *leftChild, *rightChild。 if ( putype == 2 ) Remove ( pfirstChild )。 //向同一層下一兄弟搜索 } else out ‘)’。 if ( ptrnextSibling != NULL ) out ‘,’。 return out。 operator ( ostreamamp。 //遞歸比較其子樹 } if ( x ) return Equal ( t1nextSibling, t2nextSibling )。 //根數(shù)據(jù)結(jié)點 break。amp。 if ( t1 == NULL amp。 t1, GenTreeamp。 break。 break。 t ) { //共有函數(shù) first = Copy ( )。 //大寫字母 , 建根結(jié)點 else q = new GenTreeNode ( 1, ch )。 //棧空 , 無上層鏈 , 算法結(jié)束 break。 case ‘)’ : qnextSibling = NULL。 //從棧中退出前一結(jié)點 rnextSibling = p。 //接著應是 ‘(’, 進棧 cin ch。 //廣義樹停止輸入標志數(shù)據(jù) cin ch。 Stack GenTreeNode* st (maxSubTreeNum)。 return in。 operator ( istreamamp。 operator ( ostreamamp。 operator ( istreamamp。 //析構(gòu)函數(shù) friend int operator == ( GenTreeamp。 //比較以