Comprobar si un árbol binario es BST (Binary Tree de búsqueda) o no

Aquí, vamos a aprender a comprobación de si un árbol dar binario es un árbol binario de búsqueda (BST) o no ?

Descripción:

En este artículo se describe cómo para comprobar si un determinado árbol es BST o no ? Este problema vino en octavos de Microsoft codificación.

Planteamiento del problema:

Dada una revisión de árbol binario si se trata de un árbol de búsqueda binaria o no.

Solución

Algoritmo:

De la definición de BST, puede parecer que para un árbol binario para ser BST, que es suficiente para comprobar para cada nodo if el nodo en su izquierda es más pequeña y nodo en su derecho es mayor. Pero esto es en realidad un enfoque equivocado, ya que dará salida equivocada para muchos casos de prueba.

El algoritmo correcto es comprobar para cada nodo si el máximo de la subárbol izquierdo es menor que el nodo y el mínimo de la subárbol derecho es mayor que el nodo. Este algoritmo funciona perfecto, pero no es eficiente en términos de complejidad tiempo.

La intuición dice que el recorrido en el orden de los resultados de BST en una lista ordenada de nodos y usamos esto en nuestro algoritmo.

1.  Set prev to INT_MIN.
2. From main function call checkBST(root, prev)
//passing prev by reference to update it every time
checkBST(root, &prev)
3. if(root==NULL)
return 1; //null tree is BST
4. do in-order traversal and checking whether all tree node
data is sorted or not
if(!(checkBST(root->left,prev))) //check left subtree
return 0;
//root->data must be greater than prevsince BST results in
//sorted list after in-order traversal.
5. if(root->data<prev)
return 0;
6. prev=root->data; //update prev value
7. return checkBST(root->right,prev);//check right subtree

Ejemplo 1:

Es evidente que el ejemplo 1 es un árbol binario de búsqueda. Vamos a revisar más a través de nuestra función.

Ejemplo 2:

Claramente Ejemplo 2 no es un árbol binario. Nos será comprobar a través de nuestra función.

C implementación de la clase ++ para el árbol

// tree node is defined
class tree{
public:
int data;
tree *left;
tree *right;
};

C ++ función checkBST para la implementación

//passing reference of prev
int checkBST(tree* root,int &prev){
//null tree is BST
if(root==NULL)
return 1;
//doing inorder traversal and checking whether
//all tree node data is sorted or not
if(!(checkBST(root->left,prev)))
return 0;
if(root->data<prev)
return 0;
prev=root->data; //update prev value
return checkBST(root->right,prev);
}

implementación en C ++ para crear árbol de nodos

// creating new node
tree* newnode(int data)
{
tree* node = (tree*)malloc(sizeof(tree));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}

función del controlador de

Main para example1

#include <bits/stdc++.h>
using namespace std;
int main()
{
//**same tree is builted as shown in example**
int c,prev=INT_MIN;//prev initialized to INT_MIN
cout<<"Tree is built like the example 1 aforesaid"<<endl;
tree *root=newnode(8);
root->left= newnode(3);
root->right= newnode(10);
root->right->right=newnode(14);
root->right->right->left=newnode(13);
root->left->left=newnode(1);
root->left->right=newnode(6);
root->left->right->left=newnode(4);
root->left->right->right=newnode(7);
cout<<"builting the binary tree like example 1......"<<endl;
c=checkBST(root,prev);
if(c)
cout<<"This binary tree is binary search tree"<<endl;
else
cout<<"This is not a binary search tree";
return 0;
}

función controlador para example2

#include <bits/stdc++.h>
using namespace std;
int main()
{
//**same tree is builted as shown in example**
int c,prev=INT_MIN;//prev initialized to INT_MIN
cout<<"Tree is built like the example 2 aforesaid"<<endl;
tree *root=newnode(2);
root->left= newnode(7);
root->right= newnode(5);
root->right->right=newnode(9);
root->right->right->left=newnode(4);
root->left->left=newnode(2);
root->left->right=newnode(6);
root->left->right->left=newnode(5);
root->left->right->right=newnode(11);
cout<<"builting the binary tree like example 2......"<<endl;
c=checkBST(root,prev);
if(c)
cout<<"This binary tree is binary search tree"<<endl;
else
cout<<"This is not a binary search tree";
return 0;
}

de salida 1

Tree is built like the example 1 aforesaid 
builting the binary tree like example 1......
This binary tree is binary search tree

de salida 2

Tree is built like the example 2 aforesaid 
builting the binary tree like example 2......
This is not a binary search tree


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *