【正文】 NULL。 ptr ) { //私有函數(shù) : 將用 T[n]順序存儲(chǔ)的完全二叉 樹 , 以 i 為根的子樹轉(zhuǎn)換成為用二叉鏈表表示的 //以 ptr 為根的完全二叉樹。 return in。 t. ConstructTree( T, n, 0, ptr )。 i n。 Type *A = new Type[n+1]。 cout Please enter the number of node : 。 in, BinaryTreeTypeamp。 【解答】 template class Type //建立二叉樹 istreamamp。 612 已知一棵完全二叉樹存放于一個(gè)一維數(shù)組 T[n]中， T[n]中存放的是各結(jié)點(diǎn)的值。 else 的后繼為 prightChild ( p = parent (q ) ) == NULL ? = q 的后繼為 p ≠ prightThread == 1 || prightChild == q ? = ≠ q 的后繼為 p 的右子樹中后序下的第一個(gè)結(jié)點(diǎn) q 無后繼 可用一段遍歷程序來實(shí)現(xiàn)尋找 p的右子樹中后序下的第一個(gè)結(jié)點(diǎn)：即該子樹第一個(gè)找到的葉結(jié)點(diǎn)。 prightChild != NULL ) p = prightChild。 while ( prightThread == 1 amp。 (3) 搜索指定結(jié)點(diǎn)的在后序下的后繼。 while ( pleftThread == 1 ) p = pleftChild。 設(shè)指針 q 指示中序線索化二叉樹中的指定結(jié)點(diǎn)，指針 p 指示其后繼結(jié)點(diǎn)。 } } 610 一棵高度為 h 的滿 k 叉樹有如下性質(zhì) : 第 h 層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn) , 其余各層上每個(gè)結(jié)點(diǎn)都有 k 棵非空子樹 , 如果按層次自頂向下 , 同一層自左向右 , 順序從 1 開始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào) , 試問 : (1) 各層的結(jié)點(diǎn)個(gè)數(shù)是多少 ? (2) 編號(hào)為 i 的結(jié)點(diǎn)的父結(jié)點(diǎn) (若存在 )的編號(hào)是多少 ? (3) 編號(hào)為 i 的結(jié)點(diǎn)的第 m 個(gè)孩子結(jié)點(diǎn) (若存在 )的編號(hào)是多少 ? (4) 編號(hào)為 i 的結(jié)點(diǎn)有右兄弟的條件是什么 ? 其右兄弟結(jié)點(diǎn)的編號(hào)是多少 ? 【解答】 (1) ki ( i = 0, 1, …… , h ) (2) i kk? ???? ???2 (3) ( i1)*k + m + 1 (4) ( i1 ) mod k ? 0 或 i ? ? ???? ???i kk k2 *時(shí)有右兄弟，右兄弟為 i + 1。 exchange ( ptrleftChild )。 ptrleftChild = ptrrightChild。 } (2) 交換每個(gè)結(jié)點(diǎn)的左子女和右子女 void BinaryTreeType :: exchange ( BinTreeNodeType * ptr ) { BinTreeNodeType * temp。 ptrrightChild == NULL ) return 1。 else if ( ptrleftChild == NULL amp。 (2) 以二叉樹為參數(shù)，交換每個(gè)結(jié)點(diǎn)的左子女和右子女。 【解答】 (1) 二叉樹的前序序列與中序序列相同：空樹或缺左子樹的單支樹； (2) 二叉樹的中序序列與后序序列相同：空樹或缺右子樹的單支樹； (3) 二叉樹的前序序列與后序序列相同：空樹或只有根結(jié)點(diǎn)的二叉樹。 (2) 二叉樹的中序序列與后序序列相同 。 67 如果一棵樹有 n1 個(gè)度為 1的結(jié)點(diǎn) , 有 n2 個(gè)度為 2 的結(jié)點(diǎn) , … , nm 個(gè)度為 m 的結(jié)點(diǎn) , 試問有多少個(gè)度為 0 的結(jié)點(diǎn) ? 試推導(dǎo)之。 Tree )。 operator ( ostreamamp。 Tree )。 operator ( istreamamp。 BinTreeNodeType * GetRoot ( ) const { return root。 BinTreeNodeType * Find ( const Typeamp。 } int Insert ( const Typeamp。 } BinTreeNodeType * LeftChild ( BinTreeNodeType *current ) { return current != NULL ? currentleftChild : NULL。 } int IsEmpty ( ) { return root == NULL ? 1 : 0。 } void SetLeft ( BinTreeNodeType *L ) { leftChild = L。 } void SetData ( const Typeamp。 } BinTreeNodeType* GetLeft ( ) const { return leftChild。 } BinTreeNode ( ) : leftChild ( NULL ), rightChild ( NULL ) { } BinTreeNode ( Type item ) : data ( item ), leftChild ( NULL ), rightChild ( NULL ) { } Typeamp。 out ) const。 void destroy ( BinTreeNodeType *current )。 int Find ( BinTreeNodeType *current, const Typeamp。 int Insert ( BinTreeNodeType *current, const Typeamp。 BinTreeNodeType * root。 Type data。 //釋放結(jié)點(diǎn) p } } 64 用嵌套類寫出用鏈表表示的二叉樹的類聲明。 //在子樹中刪除 ptrnextSibling = pnextSibling。 while ( ptr != NULL ) { p = ptrnextSibling。 } (5) 析構(gòu)函數(shù) 清除一棵用廣義表表示的樹 GenTree :: ~ GenTree ( ) { //用廣義表表示的樹的析構(gòu)函數(shù) , 假定 first ≠ NULL Remove ( first )。 } traverse ( ptrnextSibling )。 } else { //子樹結(jié)點(diǎn) traverse ( ptrfirstChild )。 //根數(shù)據(jù)結(jié)點(diǎn) else if ( ptrutype == 1 ) { //子女?dāng)?shù)據(jù)結(jié)點(diǎn) out ptrChildData。 } void GenTree :: traverse ( ostreamamp。 ( out, )。 out, GenTreeamp。 } (4) operator ( ) 用廣義表的形式輸出一棵樹 ostreamamp。 //相等 , 遞歸比較同一層的下一個(gè)結(jié)點(diǎn) 。 case 2 : x = Equal ( t1firstChild, t2firstChild )。 case 1 : x = ( t1ChildData == t2ChildData ) ? 1 : 0。 t1utype == t2utype ) {