數(shù)據(jù)結(jié)構(gòu)樹的測試題(二)(參考版)
2025-03-28 03:01本頁面
【正文】 } 。 else pre= pRChild。 return (succ)。 }(3) 找結(jié)點(diǎn)的先序后繼結(jié)點(diǎn)BiTNode *PreSucc (BiTNode *p)/*在先序線索二叉樹中查找p的先序后繼結(jié)點(diǎn)，并用succ指針返回結(jié)果*/{ if (pLtag= =0) succ = pLChild。 succ= q。 qLtag= =0。 }（2）找結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)BiTNode *InSucc (BiTNode *p)/*在中序線索二叉樹中查找p的中序后繼結(jié)點(diǎn)，并用succ指針返回結(jié)果*/{ if (pRtag= =1) succ = pRChild。 pre = q。 qRtag= =0。 //統(tǒng)計右子樹結(jié)點(diǎn) } }//結(jié)束Count,調(diào)用時*c=010．（1）找結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)BiTNode *InPre (BiTNode *p)/*在中序線索二叉樹中查找p的中序前驅(qū)結(jié)點(diǎn)，并用pre指針返回結(jié)果*/{ if (pLtag= =1) pre = pLChild。 //統(tǒng)計左子樹結(jié)點(diǎn) BTLC(Trchild,amp。BTLC(Tlchild,amp。} //父結(jié)點(diǎn)的右子女置空else Enqueue (Q,prchild)。// 左子女入隊列if(prchild) // 若右子女非空 if(prchilddata==x) //右子女結(jié)點(diǎn)值為 x,應(yīng)刪除當(dāng)前結(jié)點(diǎn)的右子樹 {DeleteXTree(prchild)。 plchild=null。 while(!QueueEmpty(Q)){p=QueueOut(Q)。}//若根結(jié)點(diǎn)的值為x，則刪除整棵樹 {QueueInit(Q)。//Q是存放二叉樹結(jié)點(diǎn)指針的隊列，容量足夠大 if(bt) {if(btdata==x) {DeleteXTree(bt)。//刪除bt的左子樹、右子樹 free(bt)。void DeleteXTree(BiTree bt) //刪除以bt為根的子樹 {DeleteXTree(btlchild)。刪除值為x結(jié)點(diǎn)，意味著應(yīng)將其父結(jié)點(diǎn)的左(右)子女指針置空，用層次遍歷易于找到某結(jié)點(diǎn)的父結(jié)點(diǎn)。 //設(shè)置鏈表尾 } return(head)。 } //將葉子結(jié)點(diǎn)鏈入鏈表 InOrder(btrchild)。} //處理第一個葉子結(jié)點(diǎn) else{prerchild=bt。 btrchild==null) //葉子結(jié)點(diǎn) if(pre==null) {head=bt。 //中序遍歷左子樹 if(btlchild==null amp。LinkedList head,pre=null。設(shè)置前驅(qū)結(jié)點(diǎn)指針pre，初始為空。} return(bt)。btlchild=Copy(tlchild)。 else{bt=(BiTree)malloc(sizeof(BiNode))。} //退棧，訪問，轉(zhuǎn)右子樹} }6．BiTree Copy(BiTree t)//復(fù)制二叉樹t{BiTree bt。 printf(pdata)。 bt=plchild。 //s是元素為二叉樹結(jié)點(diǎn)指針的棧，容量足夠大int top=0。 p=pRChild。S,amp。p=pLchild。push(amp。 p=root。 /*入隊列*/ } } } }4．【解答】Void PreOrder(BiTree root) /*先序遍歷二叉樹的非遞歸算法*/{ InitStack(amp。 /*入隊列*/ } if (prchild!=NULL) {printf(“%”, prchilddata)。 /*出隊*/ if (plchild!=NULL) {printf(“%f”, plchilddata)。 enqueue (q, T)。//ｑ、p無公共祖先｝//結(jié)束Ancestor3．解答：本算法要借用隊列來完成，其基本思想是，只要隊列不為空，就出隊列，然后判斷該結(jié)點(diǎn)是否有左孩子和右孩子，如有就依次輸出左、右孩子的值，然后讓左、右孩子進(jìn)隊列。bt=s[top].trchild。 s[top].tag==1) top。}｝while(top!=0 amp。j0。i)//；將棧中元素的樹結(jié)點(diǎn)到s1去匹配{pp=s[i].t。for(i=top。 top1=top。i=top。 bt=btlchild。 bt!=q) //結(jié)點(diǎn)入棧{s[++top].t=bt。 b
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1