介绍
二叉搜索树（Binary Search Tree，BST）是二叉树的一种特殊形式，它的左子树中所有的节点的值小于它的根节点的值，而右子树中所有的节点的值大于（或等于）它的根节点的值。这种数据结构的优点是在进行查找、插入、删除等操作时时间复杂度较小，为O(log n)。
在本篇文章中，我们将介绍一个用C语言编写的程序，用于检查一个二叉树是否是二叉搜索树。
二叉搜索树的定义
二叉搜索树是一棵二叉树，具有以下特点：
如果它的左子树非空，则左子树上所有节点的值都小于根节点的值。
如果它的右子树非空，则右子树上所有节点的值都大于或等于根节点的值。
它的左右子树都是二叉搜索树。
它没有重复的节点。
树的结构体定义
在程序中，我们需要定义一个二叉树的结构体。这个结构体包含三个成员：
value：节点的值。
left：左子树。
right：右子树。
结构体定义如下：
struct Node {
int value;
struct Node *left;
struct Node *right;
};
判断一个二叉树是否为二叉搜索树
判断一个二叉树是否为二叉搜索树的方法是，对于树的每一个节点，它的左子树中所有节点的值都小于它的值，右子树中所有节点的值都大于它的值。我们可以使用递归的方法来解决这个问题。
判断函数的定义
我们定义一个函数isBST来判断一个二叉树是否为二叉搜索树。这个函数的返回值是一个bool值。
bool isBST(struct Node *root);
递归实现
我们可以采取以下方法递归实现判断函数：
如果节点为空，则返回true。
如果左子树不为空，并且左子树中最大的节点的值大于根节点的值，则返回false。
如果右子树不为空，并且右子树中最小的节点的值小于或等于根节点的值，则返回false。
递归调用左子树和右子树，如果都是二叉搜索树，则返回true，否则返回false。
具体实现如下：
bool isBST(struct Node *root) {
if (root == NULL)
return true;
if (root->left != NULL && maximum(root->left) > root->value)
return false;
if (root->right != NULL && minimum(root->right) <= root->value)
return false;
if (!isBST(root->left) || !isBST(root->right))
return false;
return true;
}
int maximum(struct Node *root) {
if (root->right == NULL)
return root->value;
return maximum(root->right);
}
int minimum(struct Node *root) {
if (root->left == NULL)
return root->value;
return minimum(root->left);
}
时间复杂度
时间复杂度为O(n)，其中n是树中节点的个数。这是因为对每个节点最多只访问一次。
空间复杂度
空间复杂度为O(h)，其中h是树的高度。这是因为在递归调用的过程中会使用栈空间，栈的深度为h。最坏的情况下，树的结构类似于一个链表，高度为n，空间复杂度为O(n)。
测试程序
为了测试判断函数的正确性，我们需要一个能够构造任意二叉树的程序。我们可以设计一个函数construct来构造一棵二叉树，这个函数接受一个数组作为参数，数组中的元素代表二叉树的每个节点的值。函数返回值为根节点。
struct Node *construct(int a[], int n) {
if (n <= 0)
return NULL;
struct Node *root = (struct Node *) malloc(sizeof(struct Node));
root->value = a[n / 2];
root->left = construct(a, n / 2);
root->right = construct(a + n / 2 + 1, n - n / 2 - 1);
return root;
}
构造一棵树的代码如下：
int a[] = {4, 2, 5, 1, 3};
struct Node *root = construct(a, 5);
接下来，我们可以调用isBST函数来判断这棵树是否是二叉搜索树：
if (isBST(root))
printf("This is a BST.\n");
else
printf("This is not a BST.\n");
完整程序
将所有代码汇总，得到完整的程序如下：
#include <stdio.h>
#include <stdlib.h>
struct Node {
int value;
struct Node *left;
struct Node *right;
};
bool isBST(struct Node *root);
int maximum(struct Node *root);
int minimum(struct Node *root);
struct Node *construct(int a[], int n);
int main() {
int a[] = {4, 2, 5, 1, 3};
struct Node *root = construct(a, 5);
if (isBST(root))
printf("This is a BST.\n");
else
printf("This is not a BST.\n");
return 0;
}
bool isBST(struct Node *root) {
if (root == NULL)
return true;
if (root->left != NULL && maximum(root->left) > root->value)
return false;
if (root->right != NULL && minimum(root->right) <= root->value)
return false;
if (!isBST(root->left) || !isBST(root->right))
return false;
return true;
}
int maximum(struct Node *root) {
if (root->right == NULL)
return root->value;
return maximum(root->right);
}
int minimum(struct Node *root) {
if (root->left == NULL)
return root->value;
return minimum(root->left);
}
struct Node *construct(int a[], int n) {
if (n <= 0)
return NULL;
struct Node *root = (struct Node *) malloc(sizeof(struct Node));
root->value = a[n / 2];
root->left = construct(a, n / 2);
root->right = construct(a + n / 2 + 1, n - n / 2 - 1);
return root;
}
总结
本篇文章介绍了一个用C语言编写的程序，用于检查一个二叉树是否为二叉搜索树。我们实现了一个判断函数isBST，采用了递归的方式实现。我们还编写了一个能够构造任意二叉树的函数construct，并使用这个函数来构造了一个二叉树，测试了isBST函数的正确性。最终得出的完整程序可供读者参考。