C语言实现二叉搜索树判定算法：高效中序遍历方法

本文介绍了一种利用中序遍历判定二叉树是否为二叉搜索树的算法，该算法通过C语言代码实现，并提供详细的注释说明。

基本设计思想

中序遍历二叉树，得到一个有序的节点值序列。
判断该序列是否为递增序列，如果是则返回'true'，否则返回'false'。

C语言描述算法

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 定义辅助函数，用于中序遍历二叉树，并将节点值存入数组
void inorderTraversal(TreeNode* root, int* arr, int* index) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left, arr, index);
    arr[*index] = root->val;
    (*index)++;
    inorderTraversal(root->right, arr, index);
}

// 主函数，判断二叉树是否为二叉搜索树
bool isValidBST(TreeNode* root) {
    int arr[1000]; // 假设二叉树最多有1000个节点
    int index = 0; // 记录节点值存入数组的下标

    inorderTraversal(root, arr, &index);

    // 判断数组是否为递增序列
    for (int i = 0; i < index - 1; i++) {
        if (arr[i] >= arr[i + 1]) {
            return false;
        }
    }
    return true;
}

**注意：**以上代码只给出了关键部分，实际使用时还需要根据具体情况完善其他部分的代码，例如创建二叉树的函数、释放二叉树的函数等。

该算法的优点：

时间复杂度为O(n)，其中n为二叉树的节点数。
空间复杂度为O(n)，用于存储中序遍历得到的节点值序列。

应用场景：

判断二叉树是否为二叉搜索树
对二叉搜索树进行验证和调试
其他需要判断二叉树结构的应用场景