高效算法判定二叉搜索树：层序遍历实现

本文将介绍一种利用层序遍历判定二叉搜索树是否有效的算法。我们将使用 C 语言代码示例进行说明，并解释其设计思想和实现细节。

一、基本设计思想

层序遍历二叉树： 使用队列存储待遍历的节点，按照层级顺序访问每个节点。
记录节点信息： 在层序遍历过程中，记录每个节点的值和对应的下标。
判断二叉搜索树条件： 对于每个节点，判断其左子节点和右子节点的值是否满足二叉搜索树的条件。如果存在不满足条件的情况，则判定该树不是二叉搜索树。

二、C语言描述算法关键部分

#include <stdbool.h> // 引入bool类型

// 定义二叉树的结构体
typedef struct BinaryTreeNode {
    int data; // 节点的值
    struct BinaryTreeNode* left; // 左子节点
    struct BinaryTreeNode* right; // 右子节点
} BinaryTreeNode;

// 定义队列的结构体
typedef struct QueueNode {
    BinaryTreeNode* node; // 节点指针
    int index; // 节点的下标
} QueueNode;

// 定义队列的操作函数
typedef struct Queue {
    int front; // 队头指针
    int rear; // 队尾指针
    int size; // 队列的大小
    QueueNode* nodes; // 存储队列元素的数组
} Queue;

// 初始化队列
void initQueue(Queue* queue, int size) {
    queue->front = 0;
    queue->rear = 0;
    queue->size = size;
    queue->nodes = (QueueNode*)malloc(size * sizeof(QueueNode));
}

// 入队
void enqueue(Queue* queue, BinaryTreeNode* node, int index) {
    if ((queue->rear + 1) % queue->size == queue->front) {
        // 队列已满
        return;
    }
    queue->nodes[queue->rear].node = node;
    queue->nodes[queue->rear].index = index;
    queue->rear = (queue->rear + 1) % queue->size;
}

// 出队
void dequeue(Queue* queue) {
    if (queue->front == queue->rear) {
        // 队列为空
        return;
    }
    queue->front = (queue->front + 1) % queue->size;
}

// 判断队列是否为空
bool isEmpty(Queue* queue) {
    return queue->front == queue->rear;
}

// 层序遍历判定二叉搜索树
bool isBST(BinaryTreeNode* root) {
    if (root == NULL) {
        return true; // 空树是二叉搜索树
    }
    
    Queue queue;
    int size = 100; // 假设二叉树的节点个数不超过100个
    initQueue(&queue, size);
    
    enqueue(&queue, root, 0);
    
    while (!isEmpty(&queue)) {
        BinaryTreeNode* node = queue.nodes[queue.front].node;
        int index = queue.nodes[queue.front].index;
        dequeue(&queue);
        
        if (node->left != NULL) {
            // 判断左子节点是否小于当前节点的值
            if (node->left->data >= node->data) {
                return false;
            }
            // 入队
            enqueue(&queue, node->left, 2 * index + 1);
        }
        
        if (node->right != NULL) {
            // 判断右子节点是否大于等于当前节点的值
            if (node->right->data < node->data) {
                return false;
            }
            // 入队
            enqueue(&queue, node->right, 2 * index + 2);
        }
    }
    
    return true;
}

以上代码使用队列实现层序遍历，并在遍历过程中判断每个节点的左子节点和右子节点是否满足二叉搜索树的条件。

三、算法复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点个数。因为每个节点都访问一次，且每个节点最多进行一次判断。
空间复杂度：O(w)，其中 w 是二叉树的最大宽度。因为队列中最多存储 w 个节点。

四、总结

该算法通过层序遍历和简单的条件判断，实现了对二叉搜索树的有效判定。它简洁高效，易于理解和实现。

注意： 由于本算法仅考虑了二叉搜索树的定义，没有对输入数据的合法性进行检查。在实际应用中，需要根据具体情况进行相应的处理。