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

判断一棵二叉树是否为二叉搜索树，是数据结构中常见的算法问题。本文将介绍一种高效的算法，利用中序遍历来解决这个问题，并提供C语言代码示例。

算法设计思想

中序遍历： 根据二叉搜索树的性质，中序遍历得到的序列必然是一个递增序列。
序列判断： 对中序遍历得到的序列进行判断，如果该序列是递增序列，则说明该树是二叉搜索树；否则，该树不是二叉搜索树。

C语言代码实现

#include <stdbool.h>

// 判断一棵树是否为二叉搜索树
bool isBinarySearchTree(TreeNode *tree) {
    int* seq = (int*)malloc(tree->elemNum * sizeof(int)); // 用于存储中序遍历序列的数组
    int index = 0; // 中序遍历序列的当前索引

    // 中序遍历二叉树，将结果存储到seq数组中
    inOrderTraversal(tree, seq, &index);

    // 判断中序遍历序列是否为递增序列
    for (int i = 0; i < tree->elemNum - 1; i++) {
        if (seq[i] >= seq[i + 1]) {
            free(seq);
            return false;
        }
    }

    free(seq);
    return true;
}

// 中序遍历二叉树，将结果存储到seq数组中
void inOrderTraversal(TreeNode *tree, int* seq, int *index) {
    if (tree == NULL) {
        return;
    }

    // 遍历左子树
    inOrderTraversal(tree->left, seq, index);

    // 将当前节点的值存储到seq数组中
    seq[*index] = tree->value;
    (*index)++;

    // 遍历右子树
    inOrderTraversal(tree->right, seq, index);
}

注：

假设已经定义了二叉树节点的结构体，其中包含了左子节点和右子节点的指针，以及节点的值。
inOrderTraversal函数是用于中序遍历二叉树，并将结果存储到seq数组中的辅助函数。

总结

本文介绍了利用中序遍历判定一棵二叉树是否为二叉搜索树的算法，并提供了C语言代码示例。该算法简单易懂，易于理解和实现，适用于各种二叉树的判断。在实际应用中，可以根据具体需求选择合适的算法来判断二叉树的类型。