二叉搜索树检查-ag捕鱼王app官网

二叉树是一种非线性数据结构。它被称为二叉树，因为每个节点最多有两个子节点。这些子节点被称为左子和右子。一个二叉树要想成为 bst，必须满足以下属性。

• 左侧子树的所有节点都比根节点小。
• 右侧子树中的所有节点都比根节点大。
• 左子树和右子树也必须是二元搜索树。

二叉树是否为二叉搜索树的检验算法

算法 1

在这种方法中，我们通过将每个节点视为其子树的根，来检查左子树是否包含任何大于根值的元素，以及右子树是否包含小于根值的元素。为了找到最大和最小元素，我们必须使用两个独立的函数 getmin() 和 getmax()。

getmin()

• 初始化 temp 为 root。
• 当 temp 有一个 left 时，执行以下操作。
  • 设置 temp 为 temp->left，即向左移动找到最小的元素。
• 返回 temp->val 作为该子树的最小值。

getmax()

• 初始化 temp 为 root。
• 当 temp 有一个 right 时，执行以下操作。
  • 设置 temp 为 temp->right，即向右移动找到最大的元素。
• 返回 temp->val 作为该子树的最大值。

isbst(root)

• 如果 root 是 null，返回 true。
• 通过调用 getmax(root->left)在左边子树中找到最大元素 maxm。
• 通过调用 getmin(root->right)在右侧子树中查找最小元素 minm。
• 如果根元素小于 maxm 或大于 minm，返回 false。
• 通过调用 isbst(root->left) 和 isbst(root->right) 递归检查所有节点。如果两个递归调用都返回 true，那么这棵树就是 bst，返回 true，否则返回 false。

上面的算法告诉我们一棵树是否是 bst，但速度极慢。函数 getmin() 和 getmax() 在最坏情况下的时间复杂度为 o(n)，它们是为 n 节点调用的，使得总的时间复杂度为 o(n²)。

算法 2

该算法在前一种算法的基础上进行改进，不做重复计算。前一种方法对每个节点都调用 getmin() 和 getmax()。这个方法在上面的方法上做了改进，在我们遍历节点的时候，一直跟踪最小值和最大允许值。

isbst(root)

• 初始化两个变量 min 为 int_min，max 为 int_max。
• 调用 isbst(root,min,max)。

isbst(root, min, max)

• 如果 root 是 null，返回 true。
• 如果 min>root->data，则违反 bst 属性，返回 false。
• 如果 max<root->data，则违反 bst 属性，返回 false。
• 通过调用 isbst(root->left, min, root->data-1) 递归检查左子树（传递 min 和 root->data - 1 作为参数改变左子树中 bst 的有效范围），通过调用 isbst(root->right, root->data 1, max) 递归检查右子树（传递 root->data 1 和 max 作为参数改变右子树中 bst 的有效范围）。
• 如果两个递归调用都返回 true，则树为 bst，返回 true。

此算法的时间复杂度为 o(n)，比前一种方法有很大的改进。

算法 3

这个算法避免了上面算法中使用 int_min 和 int_max，用两个指针 l 和 r 代替。

isbst(root)

• 初始化两个节点 l 和 r 为 null。
• 调用 isbst(root, l, r)。(重载函数调用)

isbst(root, l, r)

• 如果 root 是 null，返回 true。
• 如果 l 不是 null 并且 l->data>= root->data，则违反 bst 属性，返回 false。
• 如果 r 不是 null 并且 r->data<= root->data，那么 bst 属性被违反，返回 false。
• 通过调用 isbst(root->left, left, root)（将 root 作为第三个参数传递，改变子树的最小值限制）和调用 isbst(root->right, root, right)（将 root 作为第二个参数传递，改变子树的最大值限制）来递归检查左边的子树。
• 如果两个递归调用都返回 true，则该树为 bst，返回 true。

算法 4:

二叉搜索树的 inorder 遍历按排序顺序返回元素。我们可以利用这个特性来检查一棵二叉树是否为 bst。如果无序遍历中的所有元素都不是按升序排列，那么给定的树就不是二叉搜索树。

isbst(root)

• 将变量 prev 初始化为 int_min。prev 用于检查当前节点是否大于 prev，从而按照排序顺序进行。
• 调用 isbst(root, prev)。(重载函数 call)。

isbst(root,prev)

• 如果 root 是 null，返回 true。
• 通过 isbst(root->left, prev) 递归检查左子树。如果返回 false，则返回 false。
• 如果 root->data<=prev，违反了升序，返回 false。
• 将 prev->data 更新为 root->data。
• 通过 isbst(root->right, prev) 递归检查右子树。如果返回 false，则返回 false。
• 否则，返回 true。

检查二叉树是否为二叉搜索树的算法实现方法

算法 1

#include using namespace std;
class node {
public:
    int data;
    node *left, *right;
    node(int x) {
        this->data = x;
        this->left = this->right = null;
    }
};
int getmin(node* root)
{
    while (root->left) {
        root = root->left;
    }
    return root->data;
}
int getmax(node* root)
{
    while (root->right) {
        root = root->right;
    }
    return root->data;
}
bool isbst( node* root)
{
    if (root == null)
        return true;
    if (root->left != null && getmax(root->left) > root->data)
        return false;
    if (root->right != null && getmin(root->right) < root->data)
        return false;
    if (!isbst(root->left) || !isbst(root->right))
        return false;
    return true;
}
int main()
{
    node *root = new node(6);
    root -> left = new node(3);
    root -> right = new node(9);
    root -> left -> left = new node(1);
    root -> left -> right = new node(5);
    root -> right -> left = new node(7);
    root -> right -> right = new node(11);
    if (isbst(root)) {
        cout << "this binary tree is a bst." << endl;
    }
    else {
        cout << "this binary tree is not a bst." << endl;
    }
    return 0;
}

算法 2

#include using namespace std;
class node {
public:
    int data;
    node *left, *right;
    node(int x) {
        this->data = x;
        this->left = this->right = null;
    }
};
bool isbst(node* root, int min, int max)
{
    if (root == null)
        return 1;
    if (root->data < min || root->data > max)
        return 0;
    return
        isbst(root->left, min, root->data - 1) &&
        isbst(root->right, root->data  1, max);
}
bool isbst( node* root)
{
    return isbst(root, int_min, int_max);
}
int main()
{
    node *root = new node(6);
    root -> left = new node(3);
    root -> right = new node(9);
    root -> left -> left = new node(1);
    root -> left -> right = new node(5);
    root -> right -> left = new node(7);
    root -> right -> right = new node(11);
    if (isbst(root)) {
        cout << "this binary tree is a bst." << endl;
    }
    else {
        cout << "this binary tree is not a bst." << endl;
    }
    return 0;
}

算法 3

#include using namespace std;
class node {
public:
    int data;
    node *left, *right;
    node(int x) {
        this->data = x;
        this->left = this->right = null;
    }
};
bool isbst(node* root, node* l, node* r)
{
    if (root == null)
        return true;
    if (l != null and root->data <= l->data)
        return false;
    if (r != null and root->data >= r->data)
        return false;
    return isbst(root->left, l, root) && isbst(root->right, root, r);
}
bool isbst( node* root)
{
    node* l = null;
    node* r = null;
    return isbst(root, l, r);
}
int main()
{
    node *root = new node(6);
    root -> left = new node(3);
    root -> right = new node(9);
    root -> left -> left = new node(1);
    root -> left -> right = new node(5);
    root -> right -> left = new node(7);
    root -> right -> right = new node(11);
    if (isbst(root)) {
        cout << "this binary tree is a bst." << endl;
    }
    else {
        cout << "this binary tree is not a bst." << endl;
    }
    return 0;
}

算法 4

#include using namespace std;
class node {
public:
    int data;
    node *left, *right;
    node(int x) {
        this->data = x;
        this->left = this->right = null;
    }
};
bool isbst(node* root, int& prev)
{
    if (!root) return true;
    if (!isbst(root->left, prev))
        return false;
    if (root->data <= prev)
        return false;
    prev = root->data;
    return isbst(root->right, prev);
}
bool isbst(node* root)
{
    int prev = int_min;
    return isbst(root, prev);
}
int main()
{
    node *root = new node(6);
    root -> left = new node(3);
    root -> right = new node(9);
    root -> left -> left = new node(1);
    root -> left -> right = new node(5);
    root -> right -> left = new node(7);
    root -> right -> right = new node(11);
    if (isbst(root)) {
        cout << "this binary tree is a bst." << endl;
    }
    else {
        cout << "this binary tree is not a bst." << endl;
    }
    return 0;
}

复杂度分析

时间复杂度

• 平均情况

为了检查给定的二叉树是否是 bst，我们必须遍历所有 n 节点，因为一个不符合属性的节点将导致该树不是 bst。因此，时间复杂度是 [big theta]：o(n)。

• 最佳情况

最佳情况下的时间复杂度为 o(n)。它与平均情况下的时间复杂度相同。

• 最坏情况

最坏情况下的时间复杂度为 o(n)。它与最佳情况下的时间复杂度相同。

空间复杂度

由于递归调用所需的额外空间，该算法的空间复杂度为 o(n)。