我创建了一个基于根节点的简单参数化树结构。每个节点都保存其子节点的数组列表以及指向其父节点的链接。很简单。
现在有一个我无法解决的问题(在不久的将来):
我想在这棵树上编写广度优先搜索。我想借助(已实现的)迭代器接口(interface)来实现此功能。但我真的无法让它发挥作用: 问题是同样可迭代的列表结构。我不知道如何实现 hasNext()、next() 和 remove() 函数:/
你有什么想法吗？
问候
代码:
public class Tree<T> implements Iterator<T>{
private Node<T> root;
/**
* Default constructor.
*/
public Tree() {
super();
}
/**
* Return the root Node of the tree.
* @return the root element.
*/
public Node<T> getRoot() {
return this.root;
}
/**
* Set the root Element for the tree.
* @param Root the root element to set.
*/
public void setRoot(Node<T> Root) {
this.root = Root;
}
...
和
公共(public)类节点{
public List<Node<T>> children;
public Node<T> parent;
public T data;
/**
* Default constructor.
*/
public Node() {
super();
}
/**
* Create a Node<T> with an instance of T.
* @param data an instance of T.
*/
public Node(T nodeData) {
this();
setData(nodeData);
}
/**
* Create a Node<T> with an instance of T.
* @param data an instance of T.
*/
public Node(T nodeData, Node<T> parentNode) {
this();
setData(nodeData);
setParent(parentNode);
}
...
最佳答案
您的iterator()方法将创建一个 Iterator<Node<T>> ，将使用 Queue<Node<T>> 进行初始化仅包含根。
Iterator.next()将从堆栈中取出第一个元素，将其所有子元素插入堆栈并返回它。 [别忘了也弹出它]
Iterator.remove()将从其父级 children 列表中删除最后一个元素[您可以使用 parent 访问父级字段。
另请注意，从语法上讲，您应该实现 Iterable<T> 而不是Iterator<T> 。您将创建的迭代器[如上所述]将实现 Iterator<T>
关于Java 树结构和广度优先搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9194954/