数据结构作业解析：折半查找与判断二叉排序树的算法

"这篇资料包含了广东工业大学数据结构课程在AnyView作业系统中的第九章作业答案，主要涉及折半查找的递归实现以及判断二叉树是否为二叉排序树的算法。" 在数据结构的学习中，查找算法是至关重要的部分。折半查找（Binary Search）是一种效率较高的查找方法，它利用了有序数组的特点来快速定位目标元素。在给定的代码中，9.26②题提供了一个折半查找的递归实现。下面详细解释这个算法： ```cpp int BinSearch(SSTable s, int low, int high, KeyType k) { int mid = (low + high) / 2; if (low > high) return 0; if (s.elem[mid].key == k) return mid; else if (s.elem[mid].key > k) return BinSearch(s, low, mid - 1, k); else return BinSearch(s, mid + 1, high, k); } ``` 这段代码首先计算中间索引`mid`，然后比较中间元素的键值`key`与目标键值`k`。如果两者相等，说明找到了目标元素并返回其索引；如果中间元素的键值大于目标键值，那么目标元素必然在中间元素的左侧，于是对左半部分递归进行查找；反之，如果中间元素的键值小于目标键值，递归在右半部分查找。当搜索范围`low`大于`high`时，表示未找到目标元素，返回0。 另一方面，二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，其每个节点的左子树上的所有节点的键值都小于该节点的键值，右子树上所有节点的键值都大于该节点的键值。9.31④题要求编写一个判断给定二叉树是否为二叉排序树的算法。下面给出相应的实现： ```cpp Status IsBSTree(BiTree t) { KeyType k; if (t == NULL) return TRUE; k = t->data.key; if (t->lchild == NULL && t->rchild == NULL) return TRUE; if (t->lchild != NULL && t->lchild->data.key >= k) return FALSE; if (t->rchild != NULL && t->rchild->data.key <= k) return FALSE; if (!IsBSTree(t->lchild)) return FALSE; if (!IsBSTree(t->rchild)) return FALSE; return TRUE; } ``` 这个函数首先检查根节点是否为空，若为空则返回TRUE表示空树是二叉排序树。接着检查根节点的左子树和右子树：左子树的所有节点键值必须小于根节点，右子树的所有节点键值必须大于根节点。如果这些条件不满足，直接返回FALSE表示不是二叉排序树。最后，递归检查左子树和右子树，确保它们也满足二叉排序树的条件。如果递归检查都返回TRUE，则整个二叉树是二叉排序树。 这两个问题的解答揭示了数据结构中查找算法和二叉树性质的应用，对于理解这些基本概念和提高编程能力有着重要作用。