Pregunta Árbol que satisface la propiedad de BST Pero creo que no es BST?


Hoy estoy haciendo un problema en Binary Trees durante el cual encontré una estructura de BSTree que es una propiedad satisfactoria: "Cada nodo tiene un valor menor en su hijo izquierdo y mayor valor en su hijo derecho". Pero no es una BST (en mi opinión) porque la raíz tiene un valor menor que uno de su gran hijo. Por favor, explíqueme todo esto.

Árbol binario :

      7
     /  \
    4    10
   / \
  2   8

Dime, ¿es esta BST o no? Explique .


5
2017-09-07 04:30


origen


Respuestas:


Una definición más correcta de un BST se puede encontrar aquí:

  • La izquierda subárbol de un nodo contiene solo nodos con claves menores que la clave del nodo.
  • El derecho subárbol de un nodo contiene solo nodos con claves superiores o iguales a la clave del nodo.
  • Tanto la izquierda como la derecha subárboles También debe haber árboles binarios de búsqueda.

Entonces, aunque su árbol satisface el caso específico de cada nodo que tiene un valor menor a su izquierda y un valor mayor a su derecha, no satisface el caso más general que involucra los subárboles izquierdo y derecho, y por lo tanto no es una BST.


4
2017-09-07 04:49



No lo es, 8> 7 pero 8 está en el lado izquierdo de 7.


4
2017-09-07 04:33



No es una BST, ya que un recorrido de inorder del árbol no proporcionará una salida ordenada. El principal culpable es el nodo con valor 8. Se encuentra en el subárbol izquierdo del nodo raíz pero es mayor que el nodo raíz que es 4.


0
2017-09-07 08:53