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

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