数据结构作业(2).doc

5.7 编写一个递归函数计算二叉树的高度。int height(BinNode* subroot) if (subroot = NULL) return 0; return 1+max(height(subroot-left(),height(subroot-right(); /树的高度等于最深结点的深度加15.8 编写一个递归函数计算二叉树的叶结点数。int count(BinNode* subroot) if (subroot = NULL) return 0; / 空树 if (subroot-isLeaf() return 1; / 只有一个根结点 else return 1 + count(subroot-left() + count(subroot-right();编写函数将二叉树中所有结点的左、右子树相互交换。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); 编写前序周游二叉树的非递归函数。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(); / 回到父亲节点 root = root-right; 5.6 编写一个算法，传入参数为二叉树根结点的指针，并按照层次顺序将结点的值打印出来。层次顺序首先打印根节点，接着是第一层的所有结点，再接着是第二层的所有结点，依此类推。提示：前序周游利用栈递归调用。考虑使用其他数据结构实现层次顺序周游。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(); 试写一个判断给定二叉树是否为二叉检索树的算法, 设此二叉树以链式结构存储。 (根比左子树的最大值大，比右子树最小值小)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 使用重量权衡合并规则与路径压缩，对下列从0到15之间的数的等价对进行归并，并给出所得树的父指针表示法的数组表示。在初始情况下，集合中的每个元素分别在独立的等价类中。当两棵树规模同样大时，使结点值较大的根结点作为值较小的根结点的子结点。（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 使用重量权衡合并规则与路径压缩，对下列从0到15之间的数的等价对进行归并，并给出所得树的父指针表示法的数组表示。在初始情况下，集合中的每个元素分别在独立的等价类中。当两棵树规模同样大时，使结点值较大的根结点作为值较小的根结点的子结点。（2,3）（4,5）（6,5）（3,5）（1,0）（7,8）（1,8）（3，8）（9,10）（1