C语言经典算法之判断二叉树

目录

前言

A.建议

B.简介

一 代码实现

二 时空复杂度

A.时间复杂度

B.空间复杂度

三 优缺点

A.优点：

B.缺点：

四 现实中的应用

---

前言

A.建议

1.学习算法最重要的是理解算法的每一步，而不是记住算法。

2.建议读者学习算法的时候，自己手动一步一步地运行算法。

tips：文中的对数均以2为底数

写递归算法的诀窍：1.找到算法的结束条件（结束条件可能是一个也可能是多个）

???????????????????????????????? 2.写出一般状态（非结束条件）下的处理过程，有一下两步

??????????????????????????????????????????????? 2.1 ：写出递归处理

??????????????????????????????????????????????? 2.2：写出本层的非递归处理（这一步可能有也可能无）

B.简介

这个过程利用了二叉搜索树的性质，即左子树上的所有节点值都小于根节点的值，右子树上的所有节点值都大于根节点的值。通过递归地更新值范围，可以确保整个树都符合这一性质，从而判断是否为二叉搜索树。

一 代码实现

二叉树节点的结构（此处采用二叉链表结构）如下：

#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

算法主体：

#include <stdbool.h>
#include <limits.h>

bool isBSTUtil(Node* root, int min, int max) {
    // 空树是BST
    if (root == NULL)
        return true;

    // 当前节点的值必须在 (min, max) 范围内
    if (root->data <= min || root->data >= max)
        return false;

    // 递归检查左子树和右子树
    return isBSTUtil(root->left, min, root->data) && isBSTUtil(root->right, root->data, max);
}

bool isBinarySearchTree(Node* root) {
    // 使用 INT_MIN 和 INT_MAX 作为初始的最小值和最大值
    return isBSTUtil(root, INT_MIN, INT_MAX);
}

这个算法中，isBSTUtil 函数用于递归地检查当前节点及其子树是否满足BST的条件。对于每个节点，它需要确保其值在一个范围内 (min, max)，其中 min 和 max 是其父节点的值范围。最初调用 isBinarySearchTree 函数时，将使用整个 int 范围。

二 时空复杂度

假设树上有 n 个节点。

A.时间复杂度

最坏情况下的时间复杂度： 在最坏情况下，算法需要遍历树的所有节点一次，因此时间复杂度是 。

平均情况下的时间复杂度： 平均情况下，算法仍然需要遍历树的所有节点，所以平均时间复杂度也是 。

B.空间复杂度

递归调用栈： 递归函数的调用会使用栈空间。在最坏情况下，树是平衡的，递归深度是 ，因此空间复杂度是 。在最坏情况下，树是斜向的，递归深度是，空间复杂度是 。

其他辅助空间： 除了递归调用栈，算法本身使用的额外空间很小，主要是一些常量大小的辅助空间。因此，这一部分的空间复杂度可以视为 。

三 优缺点

A.优点：

简单直观： 算法使用递归的方式，直观清晰，容易理解。

时间复杂度低： 在最坏情况下，算法的时间复杂度是 O(n)，这在大多数情况下是很高效的。

空间复杂度较低： 在平衡树的情况下，空间复杂度是 O(log n)，在实际应用中通常能够满足性能要求。

B.缺点：

不适用于所有情况： 该算法在平衡树上表现良好，但在不平衡的二叉树上可能会导致递归深度较大，增加空间复杂度。在最坏情况下，当树是线性的（类似链表）时，递归深度为 O(n)，空间复杂度为 O(n)。

不具备提前停止的能力： 一旦发现某个节点不符合条件，算法仍然会继续递归检查其左右子树。在某些情况下，可以提前停止递归，但该算法未对此进行优化。

对节点值的要求： 该算法对节点值的要求较高，要求节点值不能与最小值和最大值相等。如果树上允许存在相同值的节点，可能需要对算法进行修改。

四 现实中的应用

数据库索引结构： 数据库中的索引通常采用二叉搜索树（如平衡二叉树或者其它变种）来实现。在插入或删除数据时，需要保持索引的有序性，这就要求索引树是一棵二叉搜索树。

文件系统： 文件系统中的目录结构通常可以用二叉搜索树来表示。通过该算法，可以确保目录树的有序性，提高文件的查找效率。

编译器： 在编译器的语法分析阶段，可能需要构建抽象语法树（Abstract Syntax Tree，AST）来表示源代码结构。该树的节点可以按照某种顺序进行排列，以便进行语法分析和生成中间代码。

网络路由表： 在网络路由中，路由表通常以二叉搜索树的形式组织，以便高效地查找最优的路由路径。

算法设计： 在一些算法设计中，需要对数据进行有序存储和检索。二叉搜索树是一种常见的数据结构，通过该算法可以验证数据结构是否满足二叉搜索树的性质。

编码面试中的应用： 该算法是编码面试中经常遇到的问题，面试者可能会被要求编写判断二叉树是否为二叉搜索树的代码。