數(shù)據(jù)結(jié)構(gòu)樹的測試題(二)-預(yù)覽頁
【正文】 ）。( )2．對于有N個結(jié)點的二叉樹，其高度為log2n。( )6．中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列。( )10. 用鏈表(llinkrlink)存儲包含n個結(jié)點的二叉樹，結(jié)點的2n個指針區(qū)域中有n1個空指針。( )三、填空題1．在二叉樹中，指針p所指結(jié)點為葉子結(jié)點的條件是___ ___。5．樹的主要遍歷方法有________、________、________等三種。9．一個無序序列可以通過構(gòu)造一棵___ ___樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進行排序的過程。5．將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹。（2）寫出按前序、中序、后序遍歷該二叉樹所得到的結(jié)點序列。3. 二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序?！?. 二叉樹只能用二叉鏈表表示?！?2．將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點沒有左子樹?！?6．哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。log2i2．【解答】具有3個結(jié)點的樹 具有3個結(jié)點的二叉樹 3．解答：先根序列：A B C D E F G H I J。設(shè)n 為結(jié)點i的子女，則關(guān)系式(i1)k+2=n=ik+1成立，因i是整數(shù)，故結(jié)點n的雙親i的編號為235。(4) 根據(jù)以上分析，結(jié)點n有右兄弟的條件是，它不是雙親的從右數(shù)的第一子女，即 (n1)%k!=0，其右兄弟編號是n+1。其哈夫曼編碼如下A:1，B:000，C:01，D:0011359000111五、算法設(shè)計題1．[題目分析]二叉樹是遞歸定義的，以遞歸方式建立最簡單。x)。 btlchild=creat()。 BiTree p=bt, Q[]。 //初始化隊列，根結(jié)點指針入隊while (!QueueEmpty(Q)){p=QueueOut(Q)。 //左子女入隊 else {if (plchild) return 0。 !tag) QueueIn(Q,prchild)。 } //JudgeComplete[算法討論]完全二叉樹證明還有其它方法。本題要找p和q 的最近共同祖先結(jié)點r ,不失一般性，設(shè)p在q的左邊。typedef struct {BiTree t。//棧，容量夠大BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉樹上結(jié)點p和q的最近的共同祖先結(jié)點r。amp。 s[top].tag=0。i++) s1[i]=s[i]。i0。j)if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp)。 //退棧if (top!=0)｛s[top].tag=1。void layorder (bitreptr T) {initqueue (q) /*隊列初始化*/ if(T!=NULL) {printf(“%f”, Tdata)。 enqueue (q, plchild)。S)。S,p)。p)。while(p || top0) {while(p) {s[++top]=p。 p=prchild。 btdata=tdata。 }//結(jié)束Copy7.[題目分析]葉子結(jié)點只有在遍歷中才能知道，這里使用中序遞歸遍歷。 //全局變量LinkedList InOrder(BiTree bt)//中序遍歷二叉樹bt，將葉子結(jié)點從左到右鏈成一個單鏈表，表頭指針為head {if(bt){InOrder(btlchild)。 pre=bt。 //中序遍歷左子樹 prerchild=null。本題要求刪除樹中每一個元素值為 x的結(jié)點的子樹，因此要遍歷完整棵二叉樹。 }// DeleteXTree //釋放被刪結(jié)點所占的存儲空間void Search(B:Tree bt,ElemType x)//在二叉樹上查找所有以x為元素值的結(jié)點，并刪除以其為根的子樹{BiTree Q[]。 QueueIn(Q,bt)。} //父結(jié)點的左子女置空else Enqueue (Q,plchild)。// 右子女入隊列 }//while }//if(bt) }//search9．int BTLC(BiTree T,int *c)//對二叉樹T的結(jié)點計數(shù){if(T) {*c++。c)。 q=qRChild)。 /*直接利用線索*/ else {/*在p的右子樹中查找“最左下端”結(jié)點*/ for ( q=pRChild。 } return (succ)。 }(4) 找結(jié)點的后序前驅(qū)結(jié)點BiTNode *SuccPre (BiTNode *p)/*在后序線索二叉樹中查找p的后序前驅(qū)結(jié)點，并用pre指針返回結(jié)果*/{ if (pLtag= =1) pre = pLC
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1