數(shù)據(jù)結(jié)構(gòu)樹的測試題(二)(編輯修改稿)
2025-04-21 03:01 本頁面
【文章內(nèi)容簡介】 樹有左右子樹之分，即使在只有一個分枝的情況下， 也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空（個別書上允許為空）。二叉樹不是樹的特例。2．【解答】具有3個結(jié)點的樹 具有3個結(jié)點的二叉樹 3．解答：先根序列：A B C D E F G H I J。中根序列：B C D A F E H J I G。后根序列：D C B F J I H G E A。4．(1)kh1(h為層數(shù))（2）因為該樹每層上均有Kh1個結(jié)點，從根開始編號為1，則結(jié)點i的從右向左數(shù)第２個孩子的結(jié)點編號為ki。設(shè)n 為結(jié)點i的子女，則關(guān)系式(i1)k+2=n=ik+1成立，因i是整數(shù)，故結(jié)點n的雙親i的編號為235。n2)/k+1。 (3) 結(jié)點n(n1)的前一結(jié)點編號為n1（其最右邊子女編號是(n1)*k+1），故結(jié)點 n的第 i個孩子的編號是(n1)*k+1+i。(4) 根據(jù)以上分析，結(jié)點n有右兄弟的條件是，它不是雙親的從右數(shù)的第一子女，即 (n1)%k!=0，其右兄弟編號是n+1。HGDACJIBFEMPONKOL5.6．（l）圖略；（2）前序序列：ＡＢＣＥＤＦＨＧＩJ 中序序列： E C B H F D J I G A 后序序列： ＥＣＨＦＪＩＧＤＢＡ（3）圖略。7．字符A，B，C，D出現(xiàn)的次數(shù)為9,1,5,3。其哈夫曼編碼如下A:1，B:000，C:01，D:0011359000111五、算法設(shè)計題1．[題目分析]二叉樹是遞歸定義的，以遞歸方式建立最簡單。判定是否是完全二叉樹，可以使用隊列，在遍歷中利用完全二叉樹“若某結(jié)點無左子女就不應(yīng)有右子女”的原則進(jìn)行判斷。BiTree Creat() //建立二叉樹的二叉鏈表形式的存儲結(jié)構(gòu){ElemType x；BiTree bt。scanf(“%d”,amp。x)。 //本題假定結(jié)點數(shù)據(jù)域為整型if(x==0) bt=null。else if(x0) {bt=(BiNode *)malloc(sizeof(BiNode))。btdata=x。 btlchild=creat()。 btrchild=creat()。 } else error(“輸入錯誤”)；return(bt)。}//結(jié)束 BiTreeint JudgeComplete(BiTree bt) //判斷二叉樹是否是完全二叉樹,如是，返回1，否則，返回0{int tag=0。 BiTree p=bt, Q[]。 // Q是隊列，元素是二叉樹結(jié)點指針，容量足夠大if(p==null) return (1)。QueueInit(Q)。 QueueIn(Q,p)。 //初始化隊列，根結(jié)點指針入隊while (!QueueEmpty(Q)){p=QueueOut(Q)。 //出隊 if (plchild amp。amp。 !tag) QueueIn(Q,plchild)。 //左子女入隊 else {if (plchild) return 0。 //前邊已有結(jié)點為空，本結(jié)點不空 else tag=1。 //首次出現(xiàn)結(jié)點為空 if (prchild amp。amp。 !tag) QueueIn(Q,prchild)。 //右子女入隊 else if (prchild) return 0。 else tag=1。 } //whilereturn 1。 } //JudgeComplete[算法討論]完全二叉樹證明還有其它方法。判斷時易犯的錯誤是證明其左子樹和右子數(shù)都是完全二叉樹，由此推出整棵二叉樹必是完全二叉樹的錯誤結(jié)論。2.[題目分析]后序遍歷最后訪問根結(jié)點，即在遞歸算法中，根是壓在棧底的。采用后序非遞歸算法，棧中存放二叉樹結(jié)點的指針，當(dāng)訪問到某結(jié)點時，棧中所有元素均為該結(jié)點的祖先。本題要找p和q 的最近共同祖先結(jié)點r ,不失一般性，設(shè)p在q的左邊。后序遍歷必然先遍歷到結(jié)點p，棧中元素均為p的祖先。將?？饺肓硪惠o助棧中。再繼續(xù)遍歷到結(jié)點q時，將棧中元素從棧頂開始逐個到輔助棧中去匹配，第一個匹配（即相等）的元素就是結(jié)點p 和q的最近公共祖先。typedef struct {BiTree t。int tag。//tag=0 表示結(jié)點的左子女已被訪問，tag=1表示結(jié)點的右子女已被訪問}stack。stack s[],s1[]。//棧，容量夠大BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉樹上結(jié)點p和q的最近的共同祖先結(jié)點r。{top=0。 bt=ROOT。 while(bt!=null ||top0){while(bt!=
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1