【正文】 ta = item。 } //將結點中的子樹指針修改為 ptr void setNsinbilg ( GenTreeNode * ptr ) { nextSibling = ptr。 class GenTree { //廣義樹類定義 private: GenTreeNode *first。 //建樹時的停止輸入標志 GenTreeNode *Copy ( GenTreeNode * ptr )。 //對 ptr 為根的子樹遍歷并輸出 void Remove ( GenTreeNode *ptr )。 //比較以 s 和 t 為根的樹是否相等 public: GenTree ( )。 t )。 //析構函數(shù) friend int operator == ( GenTreeamp。 t2 )。 operator ( istreamamp。 t )。 operator ( ostreamamp。 t )。 operator ( istreamamp。 t ) { //友元函數(shù) , 從輸入流對象 in 接受用廣義表表示的樹，建立廣義表的存儲表示 t。 return in。 in, charamp。 Stack GenTreeNode* st (maxSubTreeNum)。 Type ch。 //廣義樹停止輸入標志數(shù)據(jù) cin ch。 //建立整個樹的根結點 cin ch。 //接著應是 ‘(’, 進棧 cin ch。 //建立子樹 , pfirstChild = q r = ( )。 //從棧中退出前一結點 rnextSibling = p。 ( q )。 case ‘)’ : qnextSibling = NULL。 //子樹建成 , 封閉鏈 , 退到上層 if ( ( ) == 0 ) q = ( )。 //?？?, 無上層鏈 , 算法結束 break。 default : p = q。 //大寫字母 , 建根結點 else q = new GenTreeNode ( 1, ch )。 //鏈接 } cin ch。 t ) { //共有函數(shù) first = Copy ( )。 if ( ptr != NULL ) { q = new GenTreeNode ( ptrutype, NULL )。 break。 break。 break。 //復制同一層下一 結點為頭的表 } return q。 t1, GenTreeamp。 return Equal ( , )。 if ( t1 == NULL amp。 t2 == NULL ) return 1。amp。amp。 //根數(shù)據(jù)結點 break。 //子女數(shù)據(jù)結點 break。 //遞歸比較其子樹 } if ( x ) return Equal ( t1nextSibling, t2nextSibling )。 不等 , 不再遞歸比較 } return 0。 operator ( ostreamamp。 t ) { //友元函數(shù) , 將樹 t 輸出到輸出流對象 out。 return out。 out, GenTreeNode * ptr ) { //私有函數(shù) , 廣義樹的遍歷算法 if ( ptr != NULL ) { if ( ptrutype == 0 ) out ptrRootData ‘(’。 if ( ptrnextSibling != NULL ) out ‘,’。 //向子樹方向搜索 if ( ptrnextSibling != NULL ) out ‘,’。 //向同一層下一兄弟搜索 } else out ‘)’。 } void GenTree :: Remove ( GenTreeNode *ptr ) { GenTreeNode * p。 if ( putype == 2 ) Remove ( pfirstChild )。 delete ( p )。 【解答】 include template class Type class BinaryTree { private: template class Type class BinTreeNode { public: BinTreeNodeType *leftChild, *rightChild。 } Type RefValue。 BinTreeNodeType *Parent ( BinTreeNodeType *start, BinTreeNodeType *current )。 item )。 item ) const。 void Traverse ( BinTreeNodeType *current, ostreamamp。 public: BinaryTree ( ) : root ( NULL ) { } BinaryTree ( Type value ) : RefValue ( value ), root ( NULL ){ } ~BinaryTree ( ) { destroy (root)。 GetData ( ) const { return data。 } BinTreeNodeType* GetRight ( ) const { return rightChild。 item ){ data = item。 } void SetRight ( BinTreeNodeType *R ){ RightChild =R。 } BinTreeNodeType *Parent ( BinTreeNodeType *current ) { return root == NULL || root == current ? NULL : Parent ( root, current )。 } BinTreeNodeType * RighttChild ( BinTreeNodeType *current ) { return current != NULL ? currentrightChild : NULL。 item )。 item )。 } friend istreamamp。 in, BinaryTreeTypeamp。 //輸入二叉樹 friend ostreamamp。 out, BinaryTreeTypeamp。 //輸出二叉樹 } 65 在結點個數(shù)為 n (n1)的各棵樹中，高度最小的樹的高度是多少？它有多少個葉結點？多少個分支結點？高度最大的樹的高度是多少？它有多少個葉結點？多少個分支結點？ 【解答】結點個數(shù)為 n 時，高度最小的樹的高度為 1，有 2 層；它有 n1個葉結點， 1個分支結點；高度最大的樹的高度為 n1，有 n 層；它有 1 個葉結點， n1 個分支結點。 【解答】 總結點數(shù) n = n0 + n1 + n2 + … + nm 總分支數(shù) e = n1 = n0 + n1 + n2 + … + nm1 = m*nm + (m1)*nm1 + … + 2*n2 + n1 則有 1)1(2