Это то, что у меня есть. Я думал, что предварительный заказ был тем же самым и сначала смешал его с глубиной!
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;
}
}
}
Первый поиск по ширине
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);
}
}
Ширина сначала представляет собой очередь, глубина сначала представляет собой стек.
Для ширины сначала добавьте всех детей в очередь, затем потяните голову и выполните первый поиск по ширине, используя ту же очередь.
Для глубины сначала добавьте всех дочерних элементов в стек, затем поместите и сделайте глубину сначала на этом node, используя тот же стек.
Не похоже, что вы запрашиваете реализацию, поэтому я попытаюсь объяснить процесс.
Использовать очередь. Добавьте корневой каталог node в очередь. Проведите цикл, пока очередь не будет пустой. Внутри цикла удалите первый элемент и распечатайте его. Затем добавьте все его дочерние элементы в обратную сторону очереди (обычно они идут слева направо).
Когда очередь пуста, каждый элемент должен быть распечатан.
Кроме того, есть хорошее объяснение первого поиска по википедии: http://en.wikipedia.org/wiki/Breadth-first_search
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);
}
}
И Node:
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;
}
}
//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);
}
}
}
}
Этот код, который вы написали, не создает правильного обхода 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);
}
Для реализации первого поиска ширины вы должны использовать очередь. Вы должны нажать дочерние элементы node в очередь (слева направо), а затем посетить node (данные печати). Затем yo должен удалить node из очереди. Вы должны продолжить этот процесс, пока очередь не станет пустой. Вы можете увидеть мою реализацию BFS здесь: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java
Используйте следующий алгоритм, чтобы сначала пройти в ширину search-
Код написан below-
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);
}
}
}
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;
}