數(shù)據(jù)結(jié)構(gòu)第6章二叉樹作業(yè)及答案教材-資料下載頁(yè)
2025-06-22 17:06本頁(yè)面
【正文】 EnQueue(Q,T)。 //建立工作隊(duì)列 while(!QueueEmpty(Q)) { { DeQueue(Q,p)。 if(!p) flag=1。 else if(flag) return 0。 else { EnQueue(Q,plchild)。 EnQueue(Q,prchild)。 //不管孩子是否為空,都入隊(duì)列 } }//while return 1。 }//IsFull_Bitree 分析:,作了一個(gè)修改,不管當(dāng)前結(jié)點(diǎn) 是否有左右孩子,遍歷時(shí)得到是一個(gè)連續(xù)的不包含空 ,則序列中會(huì)含有空指針. 答：這是找結(jié)點(diǎn)后繼的程序。共有3處錯(cuò)誤。注：當(dāng)rtag＝1時(shí)說明內(nèi)裝后繼指針，可直接返回，第一句無(wú)錯(cuò)。當(dāng)rtag＝0時(shí)說明內(nèi)裝右孩子指針，但孩子未必是后繼，需要計(jì)算。中序遍歷應(yīng)當(dāng)先左再根再右，所以應(yīng)當(dāng)找左子樹直到葉子處。r=rlchild。 直到LTag=1； 應(yīng)改為：while(!rLtag)r=rLchild。BiTree InSucc(BiTree q){//已知q是指向中序線索二叉樹上某個(gè)結(jié)點(diǎn)的指針，//本函數(shù)返回指向*q的后繼的指針。r=qrchild。 //應(yīng)改為r=q；if(!rrtag) while(!rrtag)r=rrchild。 //應(yīng)改為 while(!rLtag) r=rLchild。return r。 //應(yīng)改為return rrchild；}//ISucc閱讀下列算法，若有錯(cuò)，改正之。閱讀下面程序，并回答有關(guān)問題。其中BSTree為用二叉鏈表表示的二叉排序樹類型。（1） 簡(jiǎn)要說明程序功能。（5分）（2） n個(gè)結(jié)點(diǎn)的滿二叉樹的深度h是多少？（3分）（3） 假設(shè)二叉排序樹*bst是有n個(gè)結(jié)點(diǎn)的滿二叉樹,給出算法的時(shí)間復(fù)雜度。（2分）int Proc (BSTree *bst, KeyType K){ BSTree f, q, s。s=(BSTree)malloc(sizeof(BSTNode))。 s key = K。 s lchild = NULL。 s rchild = NULL。 if ( *bst == NULL ) { *bst = s。 return 1。 } f = NULL。 q = *bst。 while( q != NULL ) { if ( K q key ) { f = q。 q = q lchild。 }else { f = q。 q = q rchild。 }}if ( K f key ) f lchild = s。 else f rchild = s。 return 1。 }解：（1） 在二叉排序樹中插入關(guān)鍵字為K的結(jié)點(diǎn)（2） h = log2 ( n+1 ) 或 h = [ log2 n ] + 1 （方括號(hào)表示向下取整）（3） O ( log2 ( n+1 ) ) 或 O ( log2 n )試設(shè)計(jì)算法計(jì)算一棵給定二叉樹上所有結(jié)點(diǎn)數(shù)目。假設(shè)二叉樹的存儲(chǔ)結(jié)構(gòu)描述如下： typedef struct BiTNode{TElemType data。 struct BiTNode *lchild。*rchild。 /*左右孩子指針*/}BiTNode,*BiTree；解：int CountNode(BinTree bt) {if (bt==Null) return(0)。else {num1=CountNode(rootlchild)。num2=CountNode(rootrchild)。 return(num1+num2+1)。}} 計(jì)算二叉樹上單分支結(jié)點(diǎn)數(shù)目。假設(shè)二叉樹的存儲(chǔ)結(jié)構(gòu)描述如下： typedef struct BiTNode{TElemType data。 struct BiTNode *lchild。*rchild。 /*左右孩子指針*/} BiTNode,*BiTree；解：FUNC nodes1(t:bitre):integer。 if t=Null then nodes1:=0 else if (tlchild= Null) and (trchild= Null) then nodes1:=0else if (tlchild= Null) or (trchild= Null)then nodes1:=1+nodes1(tlchild)+nodes1(trchild) else nodes1:=nodes1(tlchild)+nodes1(trchild) ENDF。13
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1