Проверьте BST, используя inorder

Question

Я наткнулся на следующий код, чтобы проверить, является ли дерево BST или нет. Пожалуйста, объясните цель использования указателя prev и связь между корневыми данными и prev-> data.

bool isBST(struct node* root) 
{ 
    static struct node *prev = NULL; 

    // traverse the tree in inorder fashion and keep track of prev node 
    if (root) 
    { 
        if (!isBST(root->left)) 
            return false; 

        // Allows only distinct valued nodes  
        if (prev != NULL && root->data <= prev->data) 
            return false; 

        prev = root; 

        return isBST(root->right); 
    } 

    return true; 
} 

Answer 1

Базовое определение обхода inorder:

1. Обход левого поддерева, т. Е. Вызов Inorder (left-поддерево)
2. Посещение корня.
3. Обходправое поддерево, то есть вызов Inorder (правое поддерево)

Давайте рассмотрим пример BST.

Для приведенного выше дерева обход по порядку будет [2,5,6,8,10,13,15,19].По сути, обход Inorder для BST дает нам элементы в порядке возрастания.

Таким образом, в вашем коде во время обхода предыдущий узел сохраняется, чтобы сравнить его с текущим узлом.При сравнении данные текущего узла должны быть строго больше, чем данные предыдущего узла , поскольку обход дает порядок возрастания.Вот почему используется следующее условие:

 if (prev != NULL && root->data <= prev->data) 
            return false; 

Если данные текущего узла (root-> data) меньше или равны данным предыдущего узла (prev-> data), то дерево не является BST.