Java 树结构和广度优先搜索

Question

我创建了一个基于根节点的简单参数化树结构。每个节点都保存其子节点的数组列表以及指向其父节点的链接。很简单。

现在有一个我无法解决的问题(在不久的将来):

我想在这棵树上编写广度优先搜索。我想借助(已实现的)迭代器接口(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); 

}
...   

Answer 1

您的iterator()方法将创建一个 Iterator<Node<T>> ，将使用 Queue<Node<T>> 进行初始化仅包含根。

Iterator.next()将从堆栈中取出第一个元素，将其所有子元素插入堆栈并返回它。 [别忘了也弹出它]

Iterator.remove()将从其父级 children 列表中删除最后一个元素[您可以使用 parent 访问父级字段。

另请注意，从语法上讲，您应该实现 Iterable<T> 而不是Iterator<T> 。您将创建的迭代器[如上所述]将实现 Iterator<T>