數(shù)據(jù)結(jié)構(gòu)樹(shù)的測(cè)試題(二)(已改無(wú)錯(cuò)字)
2023-04-25 03:01:32 本頁(yè)面
【正文】 null amp。amp。 bt!=p amp。amp。 bt!=q) //結(jié)點(diǎn)入棧{s[++top].t=bt。 s[top].tag=0。 bt=btlchild。} //沿左分枝向下if(bt==p) //不失一般性，假定p在q的左側(cè),遇結(jié)點(diǎn)p時(shí)，棧中元素均為p的祖先結(jié)點(diǎn){for(i=1。i=top。i++) s1[i]=s[i]。 top1=top。 }//將棧s的元素轉(zhuǎn)入輔助棧s1 保存if(bt==q) //找到q 結(jié)點(diǎn)。for(i=top。i0。i)//；將棧中元素的樹(shù)結(jié)點(diǎn)到s1去匹配{pp=s[i].t。for (j=top1。j0。j)if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp)。}｝while(top!=0 amp。amp。 s[top].tag==1) top。 //退棧if (top!=0)｛s[top].tag=1。bt=s[top].trchild。｝ //沿右分枝向下遍歷}//結(jié)束while(bt!=null ||top0)return(null)。//ｑ、p無(wú)公共祖先｝//結(jié)束Ancestor3．解答：本算法要借用隊(duì)列來(lái)完成，其基本思想是，只要隊(duì)列不為空，就出隊(duì)列，然后判斷該結(jié)點(diǎn)是否有左孩子和右孩子，如有就依次輸出左、右孩子的值，然后讓左、右孩子進(jìn)隊(duì)列。void layorder (bitreptr T) {initqueue (q) /*隊(duì)列初始化*/ if(T!=NULL) {printf(“%f”, Tdata)。 enqueue (q, T)。 /*入隊(duì)列*/ while (not emptyqueue (q) ) /*若隊(duì)列非空*/ {outqueue (q, p) 。 /*出隊(duì)*/ if (plchild!=NULL) {printf(“%f”, plchilddata)。 enqueue (q, plchild)。 /*入隊(duì)列*/ } if (prchild!=NULL) {printf(“%”, prchilddata)。 enqueue (q, prchild)。 /*入隊(duì)列*/ } } } }4．【解答】Void PreOrder(BiTree root) /*先序遍歷二叉樹(shù)的非遞歸算法*/{ InitStack(amp。S)。 p=root。 while(p!=NULL || !IsEmpty(S) ) { if(p!=NULL) {Visit(pdata)。push(amp。S,p)。p=pLchild。 }else { Pop(amp。S,amp。p)。 p=pRChild。}}}5．．void InOrder(BiTree bt) {BiTree s[],p=bt。 //s是元素為二叉樹(shù)結(jié)點(diǎn)指針的棧，容量足夠大int top=0。while(p || top0) {while(p) {s[++top]=p。 bt=plchild。} //中序遍歷左子樹(shù) if(top0){p=s[top]。 printf(pdata)。 p=prchild。} //退棧，訪問(wèn)，轉(zhuǎn)右子樹(shù)} }6．BiTree Copy(BiTree t)//復(fù)制二叉樹(shù)t{BiTree bt。 if (t==null) bt=null。 else{bt=(BiTree)malloc(sizeof(BiNode))。 btdata=tdata。btlchild=Copy(tlchild)。btrchild=Copy(trchild)。} return(bt)。 }//結(jié)束Copy7.[題目分析]葉子結(jié)點(diǎn)只有在遍歷中才能知道，這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點(diǎn)指針pre，初始為空。第一個(gè)葉子結(jié)點(diǎn)由指針head指向，遍歷到葉子結(jié)點(diǎn)時(shí)，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點(diǎn)的rchild為空。LinkedList head,pre=null。 //全局變量LinkedList InOrder(BiTree bt)//中序遍歷二叉樹(shù)bt，將葉子結(jié)點(diǎn)從左到右鏈成一個(gè)單鏈表，表頭指針為head {if(bt){InOrder(btlchild)。 //中序遍歷左子樹(shù) if(btlchild==null amp。amp。 btrchild==null) //葉子結(jié)點(diǎn) if(pre==null) {head=b
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1