第7章 排序 习题参考答案

//而i的前面放的都是比基准位小的值，那么基准位 //的值应该放到i所在的位置上 if (i != pivot) {

int temp = ary[i]; ary[i] = ary[pivot]; ary[pivot] = temp; }

if (i - low > 1) {

//此时不排i的原因是i位置上的元素已经确定了，i前面的都是比i小的，i后面的都是比i大的

stack[1][top] = i - 1; stack[0][top] = low; top++; }

//当high-i小于等于1的时候，就不往栈中放了，这就是外层while循环能结束的原因 //如果从i到高位之间的元素个数多于一个，那么需要再次排序 if (high - i > 1) {

//此时不排i的原因是i位置上的元素已经确定了，i前面的都是比i小的，i后面的都是比i大的

stack[1][top] = high; stack[0][top] = i + 1; top++; } } }

5． 试设计算法，判断完全二叉树是否为大顶堆。 参考答案:

boolean checkmax(BiTreeNode t) //判断完全二叉树是否为大顶堆 {

BiTreeNode p = t;

if (p.getLchild() == null && p.getRchild() == null) { return true; } else {

if (p.getLchild() != null && p.getRchild() != null) { if ((((RecordNode)

p.getLchild().getData()).getKey()).compareTo(((RecordNode) p.getData()).getKey()) <= 0 && (((RecordNode) p.getRchild().getData()).getKey()).compareTo(((RecordNode) p.getData()).getKey()) <= 0) {

return checkmax(p.getLchild()) && checkmax(p.getRchild()); } else {

return false; }

} else if (p.getLchild() != null && p.getRchild() == null) { if ((((RecordNode)

p.getLchild().getData()).getKey()).compareTo(((RecordNode) p.getData()).getKey()) <= 0) {

return checkmax(p.getLchild());

} else {

return false; }

} else if (p.getLchild() == null && p.getRchild() != null) { if ((((RecordNode)

p.getRchild().getData()).getKey()).compareTo(((RecordNode) p.getData()).getKey()) <= 0) {

return checkmax(p.getRchild()); } else {

return false; }

} else {

return false; } } }