Java树生成广度优先？

Question

首先，如果这个问题对你们中的大多数人来说似乎很愚蠢，我真的很抱歉，它可能是这样。但是，我对编程和 Java 总体上有些陌生，我在这里尝试做的是为我正在处理的某个项目使用通用树。

规则是任何父节点都可以有尽可能多的子节点。

我还想按 breadth 生成树，这对我来说是有问题的。有什么好的 Tree 库吗？还是我应该实现自己的 ADT？

我需要它来解决一些基本的 AI 问题，例如 Farmer、Fox、Grain、Chicken 问题。

 public class Tree<T> {
   private Node<T> root;

   public Tree(T rootData) {
    root = new Node<T>();
    root.data = rootData;
    root.children = new ArrayList<Node<T>>();
   }

   public static class Node<T> {
    private T data;
    private Node<T> parent;
    private List<Node<T>> children;
  }
 }

这就是我到目前为止的情况。我只需要弄清楚如何以广度优先的方式添加节点。

请注意，我只需要能够添加数据。我暂时不关心删除和根切换。

Answer 1

几年前我在做一个类似的程序，用于使用多个 child 的广度优先搜索。您需要做的是将 Node 类修改为如下所示:

class BFSNode {
    int val;
    BFSNode parent;
    LinkedList<BFSNode> allChildren = new LinkedList<BFSNode>();
}

链接列表对于将所有子项放在一起很有用。这是完整的代码，它是为查找广度优先搜索算法而编写的(注意它可能是一个非常低效的程序，但它完成了工作)

import java.util.LinkedList;

class BFSNode {
    int val;
    BFSNode parent;
    LinkedList<BFSNode> allChildren = new LinkedList<BFSNode>();
}

public class BFSTree {
    BFSNode root = null;

    public void add(int insertVal, int parentVal) {

        BFSNode newNode = new BFSNode();
        newNode.val = insertVal;
        BFSNode parentNode = null;

        if (root == null) {
            root = newNode;
            System.out.println("Added insertVal :" + insertVal + " at parent :"
                    + root.val);
        } else if (root.val == parentVal) {
            root.allChildren.add(newNode);
            System.out.println("Added insertVal :" + insertVal + " at parent :"
                    + root.val);
        } else {
            parentNode = BFS(parentVal);
            if (parentNode == null) {
                System.out.println("Parent does not exist");
            } else {
                parentNode.allChildren.add(newNode);
                System.out.println("Added insertVal :" + insertVal
                        + " at parent :" + parentNode.val);
            }

        }

    }

    public BFSNode BFS(int parentVal) {
        BFSNode markBfsNode = root;

        LinkedList<BFSNode> childrenQueue = new LinkedList<BFSNode>();

        while (true) {

            for (int i = 0; i < markBfsNode.allChildren.size(); i++) {
                if (markBfsNode.allChildren.get(i).val == parentVal) {
                    return markBfsNode.allChildren.get(i);
                } else {
                    childrenQueue.add(markBfsNode.allChildren.get(i));
                }
            }

            if (childrenQueue.getFirst() == null) {
                System.out.println("Element not found");
                return null;
            } else {
                markBfsNode = childrenQueue.getFirst();
                childrenQueue.poll();
            }

        }
    }

    public void printBFS() {
        BFSNode markBfsNode = root;

        LinkedList<BFSNode> childrenQueue = new LinkedList<BFSNode>();
        System.out.print(root.val + "   ");

        while (true) {

            for (int i = 0; i < markBfsNode.allChildren.size(); i++) {
                childrenQueue.add(markBfsNode.allChildren.get(i));
            }

            try {
                if (childrenQueue.getFirst() == (null)) {
                    return;
                } else {
                    System.out.print(childrenQueue.getFirst().val + "   ");
                    markBfsNode = childrenQueue.getFirst();
                    childrenQueue.poll();
                }
            } catch (Exception e) {
                return;
            }

        }

    }


}

class BFSImplementation {

    public static void main(String args[]) {
        BFSTree obj = new BFSTree();
        obj.add(5, 0);

        obj.add(7, 5);
        obj.add(9, 5);
        obj.add(11, 5);
        obj.add(15, 5);

        obj.add(17, 9);
        obj.add(19, 9);
        obj.add(21, 9);

        obj.add(23, 19);
        obj.add(27, 19);

        obj.add(29, 7);
        obj.add(31, 7);

        obj.add(33, 11);
        obj.add(35, 11);

        obj.add(37, 21);
        obj.add(39, 21);

        obj.add(111, 29);
        obj.add(111, 29);
        obj.add(111, 29);

        System.out.println();
        obj.printBFS();
    }
}