Comment mettre en œuvre une première traversée large ?

Question

C'est ce que j'ai. Je pensais que la précommande était la même et je l'ai mélangée à la profondeur d'abord !

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

Largeur de la première recherche

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

La largeur d'abord est une file d'attente, la profondeur d'abord est une pile.

Pour la largeur d'abord, ajoutez tous les enfants à la file d'attente, puis tirez la tête et faites une première recherche de largeur sur elle, en utilisant la même file d'attente.

Pour la profondeur d'abord, ajouter tous les enfants à la pile, puis pop et faire une profondeur d'abord sur ce nœud, en utilisant la même pile.

Answer 3

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);
    }
}

Et le Nœud :

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;
    }
}

Answer 4

//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);
        }
    }
}

}