數(shù)據(jù)結(jié)構(gòu)樹(shù)的測(cè)試題(二)-免費(fèi)閱讀
【正文】 }(4) 找結(jié)點(diǎn)的后序前驅(qū)結(jié)點(diǎn)BiTNode *SuccPre (BiTNode *p)/*在后序線索二叉樹(shù)中查找p的后序前驅(qū)結(jié)點(diǎn)，并用pre指針?lè)祷亟Y(jié)果*/{ if (pLtag= =1) pre = pLChild。 /*直接利用線索*/ else {/*在p的右子樹(shù)中查找“最左下端”結(jié)點(diǎn)*/ for ( q=pRChild。c)。} //父結(jié)點(diǎn)的左子女置空else Enqueue (Q,plchild)。 }// DeleteXTree //釋放被刪結(jié)點(diǎn)所占的存儲(chǔ)空間void Search(B:Tree bt,ElemType x)//在二叉樹(shù)上查找所有以x為元素值的結(jié)點(diǎn)，并刪除以其為根的子樹(shù){BiTree Q[]。 //中序遍歷左子樹(shù) prerchild=null。 //全局變量LinkedList InOrder(BiTree bt)//中序遍歷二叉樹(shù)bt，將葉子結(jié)點(diǎn)從左到右鏈成一個(gè)單鏈表，表頭指針為head {if(bt){InOrder(btlchild)。 btdata=tdata。while(p || top0) {while(p) {s[++top]=p。S,p)。 enqueue (q, plchild)。 //退棧if (top!=0)｛s[top].tag=1。i0。 s[top].tag=0。//棧，容量夠大BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉樹(shù)上結(jié)點(diǎn)p和q的最近的共同祖先結(jié)點(diǎn)r。本題要找p和q 的最近共同祖先結(jié)點(diǎn)r ,不失一般性，設(shè)p在q的左邊。 !tag) QueueIn(Q,prchild)。 //初始化隊(duì)列，根結(jié)點(diǎn)指針入隊(duì)while (!QueueEmpty(Q)){p=QueueOut(Q)。 btlchild=creat()。其哈夫曼編碼如下A:1，B:000，C:01，D:0011359000111五、算法設(shè)計(jì)題1．[題目分析]二叉樹(shù)是遞歸定義的，以遞歸方式建立最簡(jiǎn)單。設(shè)n 為結(jié)點(diǎn)i的子女，則關(guān)系式(i1)k+2=n=ik+1成立，因i是整數(shù)，故結(jié)點(diǎn)n的雙親i的編號(hào)為235。log2i√12．將一棵樹(shù)轉(zhuǎn)成二叉樹(shù)，根結(jié)點(diǎn)沒(méi)有左子樹(shù)。3. 二叉樹(shù)的遍歷只是為了在應(yīng)用中找到一種線性次序。5．將下列由三棵樹(shù)組成的森林轉(zhuǎn)換為二叉樹(shù)。5．樹(shù)的主要遍歷方法有________、________、________等三種。( )10. 用鏈表(llinkrlink)存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n1個(gè)空指針。( )2．對(duì)于有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為log2n。習(xí)題六 樹(shù)和二叉樹(shù)一、單項(xiàng)選擇題1． 以下說(shuō)法錯(cuò)誤的是 ( A )A．樹(shù)形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前趨B．線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼C．樹(shù)形結(jié)構(gòu)可以表達(dá)(組織)更復(fù)雜的數(shù)據(jù)D．樹(shù)(及一切樹(shù)形結(jié)構(gòu))是一種分支層次結(jié)構(gòu)E．任何只含一個(gè)結(jié)點(diǎn)的集合是一棵樹(shù)2．下列說(shuō)法中正確的是 ( D )A．任何一棵二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2B．任何一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度都為2C．任何一棵二叉樹(shù)中的度肯定等于2D．任何一棵二叉樹(shù)中的度可以小于23．討論樹(shù)、森林和二叉樹(shù)的關(guān)系，目的是為了（ A ）A．借助二叉樹(shù)上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹(shù)的一些運(yùn)算B．將樹(shù)、森林按二叉樹(shù)的存儲(chǔ)方式進(jìn)行存儲(chǔ)C．將樹(shù)、森林轉(zhuǎn)換成二叉樹(shù)D．體現(xiàn)一種技巧，沒(méi)有什么實(shí)際意義4．樹(shù)最適合用來(lái)表示 ( C )A．有序數(shù)據(jù)元素 B．無(wú)序數(shù)據(jù)元素C．元素之間具有分支層次關(guān)系的數(shù)據(jù) D．元素之間無(wú)聯(lián)系的數(shù)據(jù)5．若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ B ）A．9 B．11 C．15 D．不確定 6．設(shè)森林F中有三棵樹(shù)，第一，第二，第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。( )3. 二叉樹(shù)的遍歷只是為了在應(yīng)用中找到一種線性次序。( )11．樹(shù)形結(jié)構(gòu)中元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。6．一個(gè)深度為k的，具有最少結(jié)點(diǎn)數(shù)的完全二叉樹(shù)按層次，（同層次從左到右）用自然數(shù)依此對(duì)結(jié)點(diǎn)編號(hào)，則編號(hào)最小的葉子的序號(hào)是__ _；編號(hào)是i的結(jié)點(diǎn)所在的層次號(hào)是_ __（根所在的層次號(hào)規(guī)定為1層）。（只要求給出轉(zhuǎn)換結(jié)果）NPGHJMOLIKEDFBAC√4. 一棵一般樹(shù)的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹(shù)的結(jié)點(diǎn)前序遍歷和后序遍歷是一致的。13．度為二的樹(shù)就是二叉樹(shù)。+17．48．任何結(jié)點(diǎn)至多只有右子女的二叉樹(shù)。n2)/k判定是否是完全二叉
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1