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