數(shù)據(jù)結(jié)構(gòu)樹的測試題(二)(存儲版)
【正文】 樹，可以使用隊(duì)列，在遍歷中利用完全二叉樹“若某結(jié)點(diǎn)無左子女就不應(yīng)有右子女”的原則進(jìn)行判斷。 btrchild=creat()。 //出隊(duì) if (plchild amp。 //右子女入隊(duì) else if (prchild) return 0。后序遍歷必然先遍歷到結(jié)點(diǎn)p，棧中元素均為p的祖先。{top=0。 bt=btlchild。i)//；將棧中元素的樹結(jié)點(diǎn)到s1去匹配{pp=s[i].t。bt=s[top].trchild。 /*入隊(duì)列*/ } if (prchild!=NULL) {printf(“%”, prchilddata)。p=pLchild。 bt=plchild。btlchild=Copy(tlchild)。 //中序遍歷左子樹 if(btlchild==null amp。 //設(shè)置鏈表尾 } return(head)。//Q是存放二叉樹結(jié)點(diǎn)指針的隊(duì)列，容量足夠大 if(bt) {if(btdata==x) {DeleteXTree(bt)。// 左子女入隊(duì)列if(prchild) // 若右子女非空 if(prchilddata==x) //右子女結(jié)點(diǎn)值為 x,應(yīng)刪除當(dāng)前結(jié)點(diǎn)的右子樹 {DeleteXTree(prchild)。 //統(tǒng)計(jì)右子樹結(jié)點(diǎn) } }//結(jié)束Count,調(diào)用時(shí)*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。 qLtag= =0。 else pre= pRChild。 return (succ)。 }（2）找結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)BiTNode *InSucc (BiTNode *p)/*在中序線索二叉樹中查找p的中序后繼結(jié)點(diǎn)，并用succ指針返回結(jié)果*/{ if (pRtag= =1) succ = pRChild。 //統(tǒng)計(jì)左子樹結(jié)點(diǎn) BTLC(Trchild,amp。 plchild=null。//刪除bt的左子樹、右子樹 free(bt)。 } //將葉子結(jié)點(diǎn)鏈入鏈表 InOrder(btrchild)。LinkedList head,pre=null。 else{bt=(BiTree)malloc(sizeof(BiNode))。 //s是元素為二叉樹結(jié)點(diǎn)指針的棧，容量足夠大int top=0。push(amp。 /*出隊(duì)*/ if (plchild!=NULL) {printf(“%f”, plchilddata)。 s[top].tag==1) top。for(i=top。 bt!=q) //結(jié)點(diǎn)入棧{s[++top].t=bt。stack s[],s1[]。采用后序非遞歸算法，棧中存放二叉樹結(jié)點(diǎn)的指針，當(dāng)訪問到某結(jié)點(diǎn)時(shí)，棧中所有元素均為該結(jié)點(diǎn)的祖先。amp。 QueueIn(Q,p)。btdata=x。7．字符A，B，C，D出現(xiàn)的次數(shù)為9,1,5,3。4．(1)kh1(h為層數(shù))（2）因?yàn)樵摌涿繉由暇蠯h1個結(jié)點(diǎn)，從根開始編號為1，則結(jié)點(diǎn)i的從右向左數(shù)第２個孩子的結(jié)點(diǎn)編號為ki。 prchlid==null 2.(1)2k1 (2)2k13．644. 2n n1 n+1 5． 先序遍歷 后序遍歷 中序遍歷 6．.(1)2k2+1（第k層1個結(jié)點(diǎn)，總結(jié)點(diǎn)個數(shù)是2H1，其雙親是2H1/2=2k2）(2) 235。11．樹形結(jié)構(gòu)中元素之間存在一個對多個的關(guān)系。2. 對于有N個結(jié)點(diǎn)的二叉樹，其高度為log2n。3．分別給出下圖所示二叉樹的先根、中根和后根序列。,一共有________個指針域,其中只有________個用來指向結(jié)點(diǎn)的左右孩子，其余的________個指針域?yàn)镹ULL。( )9. 給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。A．左子結(jié)點(diǎn) B．右子結(jié)點(diǎn) C．左子結(jié)點(diǎn)和右子結(jié)點(diǎn) D．左子結(jié)點(diǎn)，右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)20．由3 個結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（ D ）A．2 B．3 C．4 D．5 22. 一棵有n個結(jié)點(diǎn)的二叉樹，按層次從上到下，同一層從左到右順序存儲在一維數(shù)組A[1..n]中，則二叉樹中第i個結(jié)點(diǎn)（i從1開始用上述方法編號）的右孩子在數(shù)組A中的位置是（ D ）A．A[2i](2i=n) B．A[2i+1](2i+1=
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1