數(shù)據(jù)結(jié)構(gòu)作業(yè)(2).doc

5.7 編寫(xiě)一個(gè)遞歸函數(shù)計(jì)算二叉樹(shù)的高度。int height(BinNode* subroot) if (subroot = NULL) return 0; return 1+max(height(subroot-left(),height(subroot-right(); /樹(shù)的高度等于最深結(jié)點(diǎn)的深度加15.8 編寫(xiě)一個(gè)遞歸函數(shù)計(jì)算二叉樹(shù)的葉結(jié)點(diǎn)數(shù)。int count(BinNode* subroot) if (subroot = NULL) return 0; / 空樹(shù) if (subroot-isLeaf() return 1; / 只有一個(gè)根結(jié)點(diǎn) else return 1 + count(subroot-left() + count(subroot-right();編寫(xiě)函數(shù)將二叉樹(shù)中所有結(jié)點(diǎn)的左、右子樹(shù)相互交換。void exchange(bitree t) /左、右子樹(shù)交換bitree p; if(t!=NULL) p=t-lchild; t-lchild=t-rchild; t-rchild=p exchange(t-lchild); exchange(t-rchild); 編寫(xiě)前序周游二叉樹(shù)的非遞歸函數(shù)。void preOrder1(TNode* root) Stack S; while (root != NULL) | !S.empty() if (root != NULL) Visit(root); S.push(root); / 先訪問(wèn)，再入棧 root = root-left; / 依次訪問(wèn)左子樹(shù) else root = S.pop(); / 回到父親節(jié)點(diǎn) root = root-right; 5.6 編寫(xiě)一個(gè)算法，傳入?yún)?shù)為二叉樹(shù)根結(jié)點(diǎn)的指針，并按照層次順序?qū)⒔Y(jié)點(diǎn)的值打印出來(lái)。層次順序首先打印根節(jié)點(diǎn)，接著是第一層的所有結(jié)點(diǎn)，再接著是第二層的所有結(jié)點(diǎn)，依此類(lèi)推。提示：前序周游利用棧遞歸調(diào)用?？紤]使用其他數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)層次順序周游。void level(BinNode* subroot) AQueueBinNode*Q; Q.enqueue(subroot); while(!Q.isEmpty() BinNode* temp; Q.dequeue(temp); if(temp != NULL) Print(temp); Q.enqueue(temp-left(); Q.enqueue(temp-right(); 試寫(xiě)一個(gè)判斷給定二叉樹(shù)是否為二叉檢索樹(shù)的算法, 設(shè)此二叉樹(shù)以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)。 (根比左子樹(shù)的最大值大，比右子樹(shù)最小值小)int IsSearchTree(const BTNode *t) if(!t) return 1; /空二叉樹(shù)情況 else if(!(t-lchild) & !(t-rchild)return 1; /左右子樹(shù)都無(wú) else if(t-lchild) & !(t-rchild)/只有左子樹(shù)情況 if(t-lchild-datat-data) return 0; else return IsSearchTree(t-lchild); else if(t-rchild) & !(t-lchild) /只有右子樹(shù)情況 if(t-rchild-datadata) return 0; else return IsSearchTree(t-rchild); else/左右子樹(shù)全有情況 if(t-lchild-datat-data) |(t-rchild-datadata) return 0; else return IsSearchTree(t-lchild) & IsSearchTree(t-rchild); 6.6 使用重量權(quán)衡合并規(guī)則與路徑壓縮，對(duì)下列從0到15之間的數(shù)的等價(jià)對(duì)進(jìn)行歸并，并給出所得樹(shù)的父指針表示法的數(shù)組表示。在初始情況下，集合中的每個(gè)元素分別在獨(dú)立的等價(jià)類(lèi)中。當(dāng)兩棵樹(shù)規(guī)模同樣大時(shí)，使結(jié)點(diǎn)值較大的根結(jié)點(diǎn)作為值較小的根結(jié)點(diǎn)的子結(jié)點(diǎn)。（0,2）（1,2）（3,4）（3,1）（3,5）（9,11）（12,14）（3,9）（4,14）（6,7）（8,10）（8,7）（7,0）（10,15）（10,13） 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 0 0 0 0 0 0 6 0 0 0 9 0 0 12 06.7 使用重量權(quán)衡合并規(guī)則與路徑壓縮，對(duì)下列從0到15之間的數(shù)的等價(jià)對(duì)進(jìn)行歸并，并給出所得樹(shù)的父指針表示法的數(shù)組表示。在初始情況下，集合中的每個(gè)元素分別在獨(dú)立的等價(jià)類(lèi)中。當(dāng)兩棵樹(shù)規(guī)模同樣大時(shí)，使結(jié)點(diǎn)值較大的根結(jié)點(diǎn)作為值較小的根結(jié)點(diǎn)的子結(jié)點(diǎn)。（2,3）（4,5）（6,5）（3,5）（1,0）（7,8）（1,8）（3，8）（9,10）（1