如何实现广度优先遍历？

Question

这就是我所拥有的。我以为预购是一样的，把它和深度优先混在一起了！

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

广度优先搜索

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

宽度优先是队列，深度优先是堆栈。

对于广度优先，将所有子项添加到队列中，然后拉出头并使用相同的队列对其进行广度优先搜索。

对于深度优先，将所有子节点添加到堆栈中，然后使用相同的堆栈弹出并在该节点上执行深度优先。

Answer 3

您似乎并没有要求实施，所以我将尝试解释该过程。

使用队列。将根节点添加到队列中。循环运行直到队列为空。在循环内将第一个元素出列并将其打印出来。然后将其所有子级添加到队列的后面（通常从左到右）。

当队列为空时，每个元素都应该被打印出来。

另外，维基百科上对广度优先搜索有很好的解释： http://en.wikipedia.org /wiki/广度优先搜索

Answer 4

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

和节点：

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 5

//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 6

您编写的这段代码不会产生正确的 BFS 遍历：
（这是你声称是BFS的代码，但实际上这是DFS！）

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

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

Answer 7

为了实现广度优先搜索，您应该使用队列。您应该将节点的子节点推送到队列（先左后右），然后访问该节点（打印数据）。然后，您应该从队列中删除该节点。您应该继续此过程，直到队列变空。你可以在这里看到我的 BFS 实现： https:/ /github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java

Answer 8

使用以下算法进行广度优先搜索的遍历 -

1. 首先使用 put 方法将根节点添加到队列中。
2. 当队列不为空时进行迭代。
3. 获取队列中的第一个节点，然后打印其值。
4. 将左子节点和右子节点都添加到队列中（如果当前
   节点有孩子）。
5. 完毕。我们将逐级打印每个节点的值
   弹出/删除元素

代码写在下面-

    Queue<TreeNode> queue= new LinkedList<>();
    private void breadthWiseTraversal(TreeNode root) {
        if(root==null){
            return;
        }
        TreeNode temp = root;
        queue.clear();
        ((LinkedList<TreeNode>) queue).add(temp);
        while(!queue.isEmpty()){
            TreeNode ref= queue.remove();
            System.out.print(ref.data+" ");
            if(ref.left!=null) {
                ((LinkedList<TreeNode>) queue).add(ref.left);
            }
            if(ref.right!=null) {
                ((LinkedList<TreeNode>) queue).add(ref.right);
            }
        }
    }

Answer 9

以下是使用 java 8 语法的 BinaryTree 的简单 BFS 实现。

void bfsTraverse(Node node, Queue<Node> tq) {
    if (node == null) {
        return;
    }
    System.out.print(" " + node.value);
    Optional.ofNullable(node.left).ifPresent(tq::add);
    Optional.ofNullable(node.right).ifPresent(tq::add);
    bfsTraverse(tq.poll(), tq);
}

然后使用根节点和 Java 队列实现调用它。

bfsTraverse(root, new LinkedList<>());

如果它是常规树，则更好，可以使用以下行代替，因为不仅有左节点和右节点。

Optional.ofNullable(node.getChildern()).ifPresent(tq::addAll);

Answer 10

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