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