java - completo - arboles binarios ejemplos

comprobar si un árbol es un árbol de búsqueda binario

Question

He escrito el siguiente código para verificar si un árbol es un árbol de búsqueda binario. Por favor, ayúdame a verificar el código:

¡Bueno! El código está editado ahora. Esta solución simple fue sugerida por alguien en las publicaciones a continuación:

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
     if(node == null)
         return true;
     if(node.element > MIN 
         && node.element < MAX
         && IsValidBST(node.left,MIN,node.element)
         && IsValidBST(node.right,node.element,MAX))
         return true;
     else 
         return false;
}

Answer 1

Hacemos un recorrido en profundidad por el árbol, comprobando la validez de cada nodo a medida que avanzamos. Un nodo dado es válido si es mayor que todos los nodos ancestrales en el subárbol derecho de y es menor que todos los nodos ancestrales en el subárbol izquierdo de. En lugar de hacer un seguimiento de cada antepasado para verificar estas desigualdades, simplemente comprobamos que el número más grande debe ser mayor que (su Límite inferior) y el número más pequeño debe ser menor que (su Límite superior).

 import java.util.Stack;

final int MIN_INT = Integer.MIN_VALUE;
final int MAX_INT = Integer.MAX_VALUE;

public class NodeBounds {

BinaryTreeNode node;
int lowerBound;
int upperBound;

public NodeBounds(BinaryTreeNode node, int lowerBound, int upperBound) {
    this.node = node;
    this.lowerBound = lowerBound;
    this.upperBound = upperBound;
}
}

public boolean bstChecker(BinaryTreeNode root) {

// start at the root, with an arbitrarily low lower bound
// and an arbitrarily high upper bound
Stack<NodeBounds> stack = new Stack<NodeBounds>();
stack.push(new NodeBounds(root, MIN_INT, MAX_INT));

// depth-first traversal
while (!stack.empty()) {
    NodeBounds nb = stack.pop();
    BinaryTreeNode node = nb.node;
    int lowerBound = nb.lowerBound;
    int upperBound = nb.upperBound;

    // if this node is invalid, we return false right away
    if ((node.value < lowerBound) || (node.value > upperBound)) {
        return false;
    }

    if (node.left != null) {
        // this node must be less than the current node
        stack.push(new NodeBounds(node.left, lowerBound, node.value));
    }
    if (node.right != null) {
        // this node must be greater than the current node
        stack.push(new NodeBounds(node.right, node.value, upperBound));
    }
}

// if none of the nodes were invalid, return true
// (at this point we have checked all nodes)
return true;
}

Answer 2

Realmente no tiene mucho sentido devolver INTEGER.MIN, INTEGER.MAX como los valores para un árbol vacío. Tal vez use un Entero y devuelva nulo en su lugar.

Answer 3

Un árbol de búsqueda binario tiene las siguientes propiedades donde la clave para el nodo izquierdo debe ser <= la clave del nodo raíz y la clave del nodo derecha debe ser mayor que la raíz.

Entonces, el problema que tenemos es que si las claves en el árbol no son únicas y se realizó un cruce en orden podríamos obtener una situación de dos en orden cruzando produciendo la misma secuencia, donde 1 sería una bst válida y la otra no, esto sucedería si tuviéramos un árbol donde el nodo izquierdo = root (bst válido) y el nodo derecho = root (inválido no es un bst).

Para evitar esto, necesitamos mantener un rango mínimo / máximo válido de que la clave que se está ''visitando'' debe estar entre ellos, y pasamos este rango a medida que recurrimos a otros nodos.

#include <limits>

int min = numeric_limits<int>::min();
int max = numeric_limits<int>::max();

The calling function will pass the above min and max values initially to isBst(...)

bool isBst(node* root, int min, int max)
{
    //base case
    if(root == NULL)
        return true;

    if(root->val <= max && root->val >= min)
    {
        bool b1 = isBst(root->left, min, root->val);
        bool b2 = isBst(root->right, root->val, max);
        if(!b1 || !b2)
            return false;
        return true;
    }
    return false;
}

Answer 4

Un método solo debería hacer una cosa a la vez. También la forma en que haces las cosas suele ser rara. Te daré un pseudocódigo casi Java . Perdón por eso, pero no he tocado Java por algún tiempo. Espero que ayude. ¡Mira los comentarios que hice sobre la Pregunta y espero que lo resuelvas!

Llame a su isBST así:

public boolean isBst(BNode node)
{
    return isBinarySearchTree(node , Integer.MIN_VALUE , Integer.MIN_VALUE);
}

Internamente:

public boolean isBinarySearchTree(BNode node , int min , int max)
{
    if(node.data < min || node.data > max)
        return false;
    //Check this node!
    //This algorithm doesn''t recurse with null Arguments.
    //When a null is found the method returns true;
    //Look and you will find out.
    /*
     * Checking for Left SubTree
     */
    boolean leftIsBst = false;
    //If the Left Node Exists
    if(node.left != null)
    {
        //and the Left Data are Smaller than the Node Data
        if(node.left.data < node.data)
        {
            //Check if the subtree is Valid as well
            leftIsBst = isBinarySearchTree(node.left , min , node.data);
        }else
        {
            //Else if the Left data are Bigger return false;
            leftIsBst = false;
        }
    }else //if the Left Node Doesn''t Exist return true;
    {
        leftIsBst = true;
    }

    /*
     * Checking for Right SubTree - Similar Logic
     */
    boolean rightIsBst = false;
    //If the Right Node Exists
    if(node.right != null)
    {
        //and the Right Data are Bigger (or Equal) than the Node Data
        if(node.right.data >= node.data)
        {
            //Check if the subtree is Valid as well
            rightIsBst = isBinarySearchTree(node.right , node.data+1 , max);
        }else
        {
            //Else if the Right data are Smaller return false;
            rightIsBst = false;
        }
    }else //if the Right Node Doesn''t Exist return true;
    {
        rightIsBst = true;
    }

    //if both are true then this means that subtrees are BST too
    return (leftIsBst && rightIsBst);
}

Ahora: si quiere encontrar los valores Min y Max de cada subárbol, debe usar un contenedor (utilicé una lista de ArrayList ) y almacenar un triplete de Node, Min, Max que representa el nodo raíz y los valores (obviamente).

p.ej.

/*
 * A Class which is used when getting subTrees Values
 */
class TreeValues
{
    BNode root; //Which node those values apply for
    int Min;
    int Max;
    TreeValues(BNode _node , _min , _max)
    {
        root = _node;
        Min = _min;
        Max = _max;
    }
}

Y a:

/*
 * Use this as your container to store Min and Max of the whole
 */
ArrayList<TreeValues> myValues = new ArrayList<TreeValues>;

Ahora este es un método que encuentra los valores Min y Max de un nodo dado:

/*
 * Method Used to get Values for one Subtree
 * Returns a TreeValues Object containing that (sub-)trees values
 */ 
public TreeValues GetSubTreeValues(BNode node)
{
    //Keep information on the data of the Subtree''s Startnode
    //We gonna need it later
    BNode SubtreeRoot = node;

    //The Min value of a BST Tree exists in the leftmost child
    //and the Max in the RightMost child

    int MinValue = 0;

    //If there is not a Left Child
    if(node.left == null)
    {
        //The Min Value is this node''s data
        MinValue = node.data;
    }else
    {
        //Get me the Leftmost Child
        while(node.left != null)
        {
            node = node.left;
        }
        MinValue = node.data;
    }
    //Reset the node to original value
    node = SubtreeRoot; //Edit - fix
    //Similarly for the Right Child.
    if(node.right == null)
    {
        MaxValue = node.data;
    }else
    {
        int MaxValue = 0;
        //Similarly
        while(node.right != null)
        {
            node = node.right;
        }
        MaxValue = node.data;
    }
    //Return the info.
    return new TreeValues(SubtreeRoot , MinValue , MaxValue);   
}

Pero esto arroja valores para un solo nodo, así que vamos a usar esto para encontrar todo el árbol:

public void GetTreeValues(BNode node)
{
    //Add this node to the Container with Tree Data 
    myValues.add(GetSubTreeValues(node));

    //Get Left Child Values, if it exists ...
    if(node.left != null)
        GetTreeValues(node.left);
    //Similarly.
    if(node.right != null)
        GetTreeValues(node.right);
    //Nothing is returned, we put everything to the myValues container
    return; 
}

Usando estos métodos, su llamada debería verse como

if(isBinarySearchTree(root))
    GetTreeValues(root);
//else ... Do Something

Esto es casi Java. Debería funcionar con algunas modificaciones y arreglos. Encuentra un buen libro OO, te ayudará. Tenga en cuenta que esta solución podría descomponerse en más métodos.

Answer 5

correcto, otra solución simple es hacer una visita inorden

código de Java aquí

Answer 6

ACTUALIZACIÓN: Acabo de ver que esta solución fue sugerida antes. Perdón por estos chicos, tal vez alguien todavía encuentre mi versión útil

Aquí hay una solución que usa Traversal en orden para verificar la propiedad BST. Antes de proporcionar la solución, estoy usando una definición de BST que no permite duplicados. Esto significa que cada valor en el BST es único (esto es solo por simplicidad).

Código para impresión en orden recursiva:

void printInorder(Node root) {
    if(root == null) {                 // base case
        return;
    }
    printInorder(root.left);           // go left
    System.out.print(root.data + " "); // process (print) data
    printInorder(root.right);          // go right
}

Después de este recorrido inorden en una BST, todos los datos deben imprimirse en orden ascendente ordenado. Por ejemplo, el árbol:

   5
 3   7
1 2 6 9

tendría que imprimir en orden:

1 2 3 5 6 7 9

Ahora, en lugar de imprimir el nodo, podemos hacer un seguimiento del valor anterior en la secuencia en orden y compararlo con el valor del nodo actual. Si el valor del nodo actual es menor que el valor anterior, esto significa que la secuencia no está en el orden ascendente ordenado y que se viola la propiedad BST.

Por ejemplo, el árbol:

   5
 3   7
1 8 6 9

Tiene una violación El hijo correcto de 3 es 8 y esto estaría bien si 3 fuera el nodo raíz. Sin embargo, en una BST 8 terminaría como un hijo izquierdo de 9 y no como un hijo derecho de 3 . Por lo tanto, este árbol no es una BST. Entonces, el código que sigue esta idea:

/* wrapper that keeps track of the previous value */
class PrevWrapper {
    int data = Integer.MIN_VALUE;
}

boolean isBST(Node root, PrevWrapper prev) {
    /* base case: we reached null*/
    if (root == null) {
        return true;
    }

    if(!isBST(root.left, prev)) {
        return false;
    }
    /* If previous in-order node''s data is larger than
     * current node''s data, BST property is violated */
    if (prev.data > root.data) {
        return false;
    }

    /* set the previous in-order data to the current node''s data*/
    prev.data = root.data;

    return isBST(root.right, prev);
}

boolean isBST(Node root) {
    return isBST(root, new PrevWrapper());
}

El recorrido en orden para el árbol de muestra no pasaría la comprobación del nodo 5 ya que el orden en orden anterior de 5 es 8 , que es más grande, por lo que se infringe la propiedad BST.

Answer 7

    boolean isBST(TreeNode root, int max, int min) {
        if (root == null) {
            return true;
        } else if (root.val >= max || root.val <= min) {
            return false;
        } else {
            return isBST(root.left, root.val, min) && isBST(root.right, max, root.val);
        }

    }

una forma alternativa de resolver este problema ... similar a tu código

Answer 8

boolean bst = isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

public boolean isBST(Node root, int min, int max) {
    if(root == null) 
        return true;

    return (root.data > min &&
            root.data < max &&
            isBST(root.left, min, root.data) &&
            isBST(root.right, root.data, max));
    }

Answer 9

public void inorder()
     {
         min=min(root);
         //System.out.println(min);
         inorder(root);

     }

     private int min(BSTNode r)
         {

             while (r.left != null)
             {
                r=r.left;
             }
          return r.data;


     }


     private void inorder(BSTNode r)
     {

         if (r != null)
         {
             inorder(r.getLeft());
             System.out.println(r.getData());
             if(min<=r.getData())
             {
                 System.out.println(min+"<="+r.getData());
                 min=r.getData();
             }
             else
             System.out.println("nananan");
             //System.out.print(r.getData() +" ");
             inorder(r.getRight());
             return;
         }
     }