数据结构：折半查找与二叉排序树判别算法

"数据结构相关的课程作业答案，包含第九章的必做和选做题目，主要涉及折半查找算法的递归实现以及判断二叉树是否为二叉排序树的算法。" 在数据结构的学习中，查找算法是基础且重要的部分，而折半查找（Binary Search）因其高效的性能在有序数组中广泛应用。第九章的一个练习是将折半查找算法改写为递归形式。原算法使用迭代方式完成查找，而递归版本则更侧重于逻辑的自顶向下处理。下面是对递归版折半查找算法的详细解释： ```c int BinSearch(SSTable s, int low, int high, KeyType k) { int mid; if (low <= high) { mid = (low + high) / 2; if (s.elem[mid].key == k) return mid; if (s.elem[mid].key < k) return BinSearch(s, mid + 1, high, k); if (s.elem[mid].key > k) return BinSearch(s, low, high - 1, k); } return 0; } ``` 在这个递归函数中，首先计算中间索引`mid`，然后比较中间元素的键值与目标键值`k`。如果找到匹配项，返回索引；如果目标键值较大，则在右半部分递归查找；如果目标键值较小，则在左半部分递归查找。当搜索范围为空时（即`low > high`），表示未找到目标，返回0。 另一个练习涉及到二叉排序树（Binary Search Tree，BST）。BST是一种特殊的二叉树，其每个节点的左子树上的所有节点的键值都小于当前节点，而右子树上的所有节点的键值都大于当前节点。给定一个二叉树，我们需要编写一个函数来判断它是否符合二叉排序树的性质。以下是该函数的实现： ```c Status IsBSTree(BiTree t) { if (t) { // 非空节点 if (t->lchild && (t->data.key < t->lchild->data.key)) // 左孩子不空，左孩子的key比本身的小 return FALSE; if (t->rchild && (t->data.key > t->rchild->data.key)) // 右孩子不空，右孩子的key比本身的小 return FALSE; if (!IsBSTree(t->lchild)) // 判断左子树 return FALSE; if (!IsBSTree(t->rchild)) // 判断右子树 return FALSE; } return TRUE; // 如果所有条件都满足，返回TRUE } ``` 这个函数通过递归地检查每个节点及其左右子树来完成验证。首先检查当前节点的左右子节点是否满足BST的性质，然后分别对左右子树进行同样的检查。如果在任何阶段发现不满足条件，立即返回`FALSE`，表示不是二叉排序树。如果所有节点都满足条件，最后返回`TRUE`。 这两个练习涵盖了数据结构中的核心概念，不仅锻炼了编程技巧，也加深了对二分查找和二叉排序树理解。对于学习数据结构的学生来说，理解和掌握这些算法是非常有益的。