線性數(shù)學(xué)試題解答6-wenkub
2022-09-15 21:16:20 本頁面
【正文】 s 和 t 為根的樹是否相等 public: GenTree ( )。 //建樹時(shí)的停止輸入標(biāo)志 GenTreeNode *Copy ( GenTreeNode * ptr )。 } //將結(jié)點(diǎn)中的子樹指針修改為 ptr void setNsinbilg ( GenTreeNode * ptr ) { nextSibling = ptr。 } //返回?cái)?shù)據(jù)結(jié)點(diǎn)的值 GenTreeNode * GetFchild ( ) { return firstChild。 //utype=2, 指向第一個(gè)子女的指針 } public: GenTreeNode ( int tp, char item ) : utype (tp), nextSibling (NULL) { if ( tp == 0 ) RootData = item。 //utype=0, 指向第一個(gè)子女 。 //GenTree 類的前視聲明 class GenTreeNode { //廣義樹結(jié)點(diǎn)類的聲明 friend class GenTree。61 寫出用廣義表表示法表示的樹的類聲明，并給出如下成員函數(shù)的實(shí)現(xiàn)： (1) operator ( ) 接收用廣義表表示的樹作為輸入，建立廣義表的存儲表示； (2) 復(fù)制構(gòu)造函數(shù) 用另一棵表示為廣義表的樹初始化一棵樹； (3) operator == ( ) 測試用廣義表表示的兩棵樹是否相等； (4) operator ( ) 用廣義表的形式輸出一棵樹； (5) 析構(gòu)函數(shù) 清除一棵用廣義表表示的樹。 private: int utype。 //utype=1 或 2, 指向同一層下一兄弟 union { //聯(lián)合 char RootData。 else ChildData = item。 } //返回子樹結(jié)點(diǎn)的地址 GenTreeNode * GetNsibling ( ) { return nextSibling。 } }。 //復(fù)制一個(gè) ptr 指示的子樹 void Traverse ( GenListNode * ptr )。 //構(gòu)造函數(shù) GenTree ( GenTreeamp。 t1, GenTreeamp。 in, GenTreeamp。 out, GenTreeamp。 in, GenTreeamp。 } void GenTree :: ConstructTree ( istreamamp。 //用于建表時(shí)記憶回退地址 GenTreeNode * p, q, r。 first = q = new GenTreeNode ( 0, ch )。 while ( ch != value ) { //逐個(gè)結(jié)點(diǎn)加入 switch ( ch ) { case ‘(’ : p = new GenTreeNode Type ( q )。 //插在前一結(jié)點(diǎn) r 之后 ( p )。 ( )。 case ‘,’ : break。 //非大寫字母 , 建數(shù)據(jù)結(jié)點(diǎn) pnextSibling = q。 } GenTreeNode* GenTree :: Copy ( GenTreeNode *ptr ) { //私有函數(shù)，復(fù)制一個(gè) ptr 指示的用廣義表表示的子樹 GenTreeNode *q = NULL。 //傳送根結(jié)點(diǎn)數(shù)據(jù) case 1 : qChildData = ptrChildData。 //遞歸傳送子樹信息 } qnextSibling = Copy ( ptrnextSibling )。 t2 ) { //友元函數(shù) : 判兩棵樹 t1 與 t2 是否相等 , 若兩表完全相等 , 函數(shù)返回 1, 否則返回 0。amp。 t2 != NULL amp。 case 1 : x = ( t1ChildData == t2ChildData ) ? 1 : 0。 //相等 , 遞歸比較同一層的下一個(gè)結(jié)點(diǎn) 。 out, GenTreeamp。 } void GenTree :: traverse ( ostreamamp。 } else { //子樹結(jié)點(diǎn) traverse ( ptrfirstChild )。 } (5) 析構(gòu)函數(shù) 清除一棵用廣義表表示的樹 GenTree :: ~ GenTree ( ) { //用廣義表表示的樹的析構(gòu)函數(shù) , 假定 first ≠ NULL Remove ( first )。 //在子樹中刪除 ptrnextSibling = pnextSibling。 Type data。 int Insert ( BinTreeNodeType *current, const Typeamp。 void destroy ( BinTreeNodeType *current )。 } BinTreeNode ( ) : leftChild ( NULL ), rightChild ( NULL ) { } BinTreeNode ( Type item ) : data ( item ), leftChild ( NULL ), rightChild ( NULL ) { } Typeamp。 } void SetData ( const Typeamp。 } int IsEmpty ( ) { return root == NULL ? 1 : 0。 } int Insert ( const Typeamp。 BinTreeNodeType * GetRoot ( ) const { return root。 Tree )。 Tree )。 (2) 二叉樹的中序序列與后序序列相同 。 (2) 以二叉樹為參數(shù)，交換每個(gè)結(jié)點(diǎn)的左子女和右子女。 ptrrightChild == NULL ) return 1。 ptrleftChild = ptrrightChild。 } } 610 一棵高度為 h 的滿 k 叉樹有如下性質(zhì) : 第 h 層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn) , 其余各層上每個(gè)結(jié)點(diǎn)都有 k 棵非空子樹 , 如果按層次自頂向下 , 同一層自左向右 , 順序從 1 開始對全部結(jié)點(diǎn)進(jìn)行編號 , 試問 : (1) 各層的結(jié)點(diǎn)個(gè)數(shù)是多少 ? (2) 編號為 i 的結(jié)點(diǎn)的父結(jié)點(diǎn) (若存在 )的編號是多少 ? (3) 編號為 i 的結(jié)點(diǎn)的第 m 個(gè)孩子結(jié)點(diǎn) (若存在 )的編號是多少 ? (4) 編號為 i 的結(jié)點(diǎn)有右兄弟的條件是什么 ? 其右兄弟結(jié)點(diǎn)的編號是多少 ? 【解答】 (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。 while ( pleftThread == 1 ) p = pleftChild。 while ( prightThread == 1 amp。 else 的后繼為 prightChild ( p = parent (q ) ) == NULL ? = q 的后繼為 p ≠ pright
公司管理相關(guān)推薦
鄂ICP備17016276號-1