java - example - depth first search c

¿Cómo implementar un primer cruce transversal?

Question

Esto es lo que tengo. ¡Pensé que el preordenar era el mismo y lo mezclé primero con la profundidad!

import java.util.LinkedList;
import java.util.Queue;

public class Exercise25_1 {
  public static void main(String[] args) {

    BinaryTree tree = new BinaryTree(new Integer[] {10, 5, 15, 12, 4, 8 });

    System.out.print("/nInorder: ");
    tree.inorder();
    System.out.print("/nPreorder: ");
    tree.preorder();
    System.out.print("/nPostorder: ");
    tree.postorder();

    //call the breadth method to test it

    System.out.print("/nBreadthFirst:");
    tree.breadth();

  }
}

class BinaryTree {
  private TreeNode root;


  /** Create a default binary tree */
  public BinaryTree() {
  }

  /** Create a binary tree from an array of objects */
  public BinaryTree(Object[] objects) {
    for (int i = 0; i < objects.length; i++) {
      insert(objects[i]);
    }
  }

  /** Search element o in this binary tree */
  public boolean search(Object o) {
    return search(o, root);
  }

  public boolean search(Object o, TreeNode root) {
    if (root == null) {
      return false;
    }
    if (root.element.equals(o)) {
      return true;
    }
    else {
      return search(o, root.left) || search(o, root.right);
    }
  }

  /** Return the number of nodes in this binary tree */
  public int size() {
    return size(root);
  }

  public int size(TreeNode root) {
    if (root == null) {
      return 0;
    }
    else {
      return 1 + size(root.left) + size(root.right);
    }
  }

  /** Return the depth of this binary tree. Depth is the
  * number of the nodes in the longest path of the tree */
  public int depth() {
    return depth(root);
  }

  public int depth(TreeNode root) {
    if (root == null) {
      return 0;
    }
    else {
      return 1 + Math.max(depth(root.left), depth(root.right));
    }
  }

  /** Insert element o into the binary tree
  * Return true if the element is inserted successfully */
  public boolean insert(Object o) {
    if (root == null) {
      root = new TreeNode(o); // Create a new root
    }
    else {
      // Locate the parent node
      TreeNode parent = null;
      TreeNode current = root;
      while (current != null) {
        if (((Comparable)o).compareTo(current.element) < 0) {
          parent = current;
          current = current.left;
        }
        else if (((Comparable)o).compareTo(current.element) > 0) {
          parent = current;
          current = current.right;
        }
        else {
          return false; // Duplicate node not inserted
        }
      }

      // Create the new node and attach it to the parent node
      if (((Comparable)o).compareTo(parent.element) < 0) {
        parent.left = new TreeNode(o);
      }
      else {
        parent.right = new TreeNode(o);
      }
    }

    return true; // Element inserted
  }

  public void breadth() {
  breadth(root);
  }

//  Implement this method to produce a breadth first

//  search traversal
  public void breadth(TreeNode root){
      if (root == null)
          return;

      System.out.print(root.element + " ");
      breadth(root.left);
      breadth(root.right);
 }


  /** Inorder traversal */
  public void inorder() {
    inorder(root);
  }

  /** Inorder traversal from a subtree */
  private void inorder(TreeNode root) {
    if (root == null) {
      return;
    }
    inorder(root.left);
    System.out.print(root.element + " ");
    inorder(root.right);
  }

  /** Postorder traversal */
  public void postorder() {
    postorder(root);
  }

  /** Postorder traversal from a subtree */
  private void postorder(TreeNode root) {
    if (root == null) {
      return;
    }
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.element + " ");
  }

  /** Preorder traversal */
  public void preorder() {
    preorder(root);
  }

  /** Preorder traversal from a subtree */
  private void preorder(TreeNode root) {
    if (root == null) {
      return;
    }
    System.out.print(root.element + " ");
    preorder(root.left);
    preorder(root.right);

  }

  /** Inner class tree node */
  private class TreeNode {
    Object element;
    TreeNode left;
    TreeNode right;

    public TreeNode(Object o) {
      element = o;
    }
  }

}

Answer 1

Ampliar la primera búsqueda

Queue<TreeNode> queue = new LinkedList<BinaryTree.TreeNode>() ;
public void breadth(TreeNode root) {
    if (root == null)
        return;
    queue.clear();
    queue.add(root);
    while(!queue.isEmpty()){
        TreeNode node = queue.remove();
        System.out.print(node.element + " ");
        if(node.left != null) queue.add(node.left);
        if(node.right != null) queue.add(node.right);
    }

}

Answer 2

Este código que usted ha escrito, no está produciendo el cruce BFS correcto: (Este es el código que afirmó que es BFS, ¡pero de hecho es DFS!)

//  search traversal
  public void breadth(TreeNode root){
      if (root == null)
          return;

      System.out.print(root.element + " ");
      breadth(root.left);
      breadth(root.right);
 }

Answer 3

La amplitud primero es una cola, la profundidad primero es una pila.

Para amplitud primero, agregue todos los elementos secundarios a la cola, luego tire de la cabeza y realice una primera búsqueda de ancho, utilizando la misma cola.

Para la profundidad primero, agregue todos los elementos secundarios a la pila, luego pop y haga una profundidad primero en ese nodo, usando la misma pila.

Answer 4

No parece que estés pidiendo una implementación, así que trataré de explicar el proceso.

Use una cola. Agregue el nodo raíz a la cola. Ejecute un ciclo hasta que la cola esté vacía. Dentro del ciclo dequeue el primer elemento e imprímalo. A continuación, agregue todos sus hijos al final de la cola (por lo general, yendo de izquierda a derecha).

Cuando la cola está vacía, cada elemento debería haberse impreso.

Además, hay una buena explicación de la primera búsqueda de ancho en wikipedia: http://en.wikipedia.org/wiki/Breadth-first_search

Answer 5

Para implementar la primera búsqueda de amplitud, debe usar una cola. Debe empujar los elementos secundarios de un nodo a la cola (izquierda y derecha) y luego visitar el nodo (imprimir datos). Entonces, deberías eliminar el nodo de la cola. Debe continuar este proceso hasta que la cola quede vacía. Puede ver mi implementación del BFS aquí: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java

Answer 6

//traverse
public void traverse()
{
    if(node == null)
        System.out.println("Empty tree");
    else
    {
        Queue<Node> q= new LinkedList<Node>();
        q.add(node);
        while(q.peek() != null)
        {
            Node temp = q.remove();
            System.out.println(temp.getData());
            if(temp.left != null)
                q.add(temp.left);
            if(temp.right != null)
                q.add(temp.right);
        }
    }
}

}

Answer 7

public static boolean BFS(ListNode n, int x){
        if(n==null){
           return false;
       }
Queue<ListNode<Integer>> q = new Queue<ListNode<Integer>>();
ListNode<Integer> tmp = new ListNode<Integer>(); 
q.enqueue(n);
tmp = q.dequeue();
if(tmp.val == x){
    return true;
}
while(tmp != null){
    for(ListNode<Integer> child: n.getChildren()){
        if(child.val == x){
            return true;
        }
        q.enqueue(child);
    }

    tmp = q.dequeue();
}
return false;
}

Answer 8

public void breadthFirstSearch(Node root, Consumer<String> c) {
    List<Node> queue = new LinkedList<>();

    queue.add(root);

    while (!queue.isEmpty()) {
        Node n = queue.remove(0);
        c.accept(n.value);

        if (n.left != null)
            queue.add(n.left);
        if (n.right != null)
            queue.add(n.right);
    }
}

Y el Nodo:

public static class Node {
    String value;
    Node left;
    Node right;

    public Node(final String value, final Node left, final Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}