首先,我真的很抱歉,如果这个问题在你们大多数人看来是愚蠢的,它可能。
不过,我对编程和Java基本上还不太熟悉,我在这里要做的是对我正在处理的一些项目使用通用树。
规则是任何父节点都可以有尽可能多的子节点。
我还想按宽度生成树,这对我来说是个问题。
有没有什么好的树库来实现这个功能,或者我应该实现自己的adt?
我需要它来解决一些基本的人工智能问题,比如农民、狐狸、粮食、鸡肉的问题。
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;
}
}
这就是我现在所拥有的我只需要找出如何以广度优先的方式添加节点。
请注意,我只需要能够添加数据我现在不在乎删除和根目录切换。
最佳答案
几年前,我也在做一个类似的程序,使用多个孩子进行广度优先搜索。您需要做的是将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();
}
}