數(shù)據(jù)結(jié)構(gòu)課后習(xí)題及解析第六章-在線瀏覽
2025-05-12 03:02本頁面
【正文】 則該樹中有多少個葉子結(jié)點(diǎn)？【解答】設(shè)樹中結(jié)點(diǎn)總數(shù)為n,則n=n0 + n1 + …… + nk樹中分支數(shù)目為B,則B=n1 + 2n2 + 3n3 + …… + knk因?yàn)槌Y(jié)點(diǎn)外，每個結(jié)點(diǎn)均對應(yīng)一個進(jìn)入它的分支，所以有n= B + 1即n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1由上式可得葉子結(jié)點(diǎn)數(shù)為：n0 = n2 + 2n3 + …… + (k1)nk + 1，則該二叉樹的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個？【解答】n0表示葉子結(jié)點(diǎn)數(shù)，n2表示度為2的結(jié)點(diǎn)數(shù)，則n0 = n2+1 試分別找出滿足以下條件的所有二叉樹:(1) 前序序列與中序序列相同。(3) 前序序列與后序序列相同?！窘獯稹?構(gòu)造哈夫曼樹如下：I2：11110 I6： 10I3：1110 I4：1101。，實(shí)現(xiàn)在中序線索二叉樹T中查找給定結(jié)點(diǎn)*p在中序序列中的前驅(qū)與后繼。在后序線索二叉樹T中，查找給定結(jié)點(diǎn)*p在后序序列中的前驅(qū)。（1）找結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)BiTNode *p)/*在中序線索二叉樹中查找p的中序前驅(qū)結(jié)點(diǎn)，并用pre指針返回結(jié)果*/{ if (pLtag= =1) /*直接利用線索*/ qRtag= =0。return (pre)。 *InSucc (BiTNode succ = pRChild。else {/*在p的右子樹中查找“最左下端”結(jié)點(diǎn)*/ for ( q=pRChild。 q=qLChild)。 succ= q。 } }(3) 找結(jié)點(diǎn)的先序后繼結(jié)點(diǎn)BiTNode *p)/*在先序線索二叉樹中查找p的先序后繼結(jié)點(diǎn)，并用succ指針返回結(jié)果*/{ if (pLtag= =0) }(4) 找結(jié)點(diǎn)的后序前驅(qū)結(jié)點(diǎn)BiTNode *p)/*在后序線索二叉樹中查找p的后序前驅(qū)結(jié)點(diǎn)，并用pre指針返回結(jié)果*/{ if (pLtag= =1) }，利用棧的基本操作寫出先序遍歷非遞歸形式的算法。 PreOrder(BiTree /*先序遍歷二叉樹的非遞歸算法*/{S)。 p=root。 while(p!=NULL || !IsEmpty(S) ) {Visit(pdata)。S,p)。{ Pop(amp。p)。}}}，編寫算法，將二叉樹左右子樹進(jìn)行交換。exchange ( BiTree p=root。 if ( pLChild != NULL || pRChild != NULL )pLChild = pRChild。 exchange ( pLChild )。 exchange ( BiTree p=root。 if ( pLChild != NULL || pRChild != NULL ) exchange ( pRChild )。 temp = pLChild。 pRChild = temp。 } }第六章 習(xí)題解析1．試分別畫出具有3個結(jié)點(diǎn)的樹和3個結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。3．已知一棵度
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1