Java树结构和广度优先搜索

Question

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

现在，我没有能够解决（在不久的将来）一个问题：

我想写在这个树广度优先搜索。我想在（实现的）迭代器接口的帮助下实现此功能。但我真的无法把这个工作： 问题是也迭代列表结构。我不知道如何实现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 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()方法CREA te Iterator<Node<T>>，将使用仅包含根的Queue<Node<T>>进行初始化。

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

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

另请注意，在句法上，您应该执行Iterable<T>而不是Iterator<T>。您将创建的迭代器[如上所述]将执行Iterator<T>

Answer 2

您的Node类需要实现Iterable接口而不是`Iterator'接口。

Iterable接口基本上说'这个类可以返回一个迭代器并被迭代'，而Iterator接口说'我可以迭代某些东西并返回这些项目'。 Iterable接口需要执行Iterator才能工作。

下面是一个快速，人为的例子（未经测试，但你应该得到的要点）。

public class MyList implements Iterable<Integer> { 

    public List<Integer> x; 

    public Iterator<Integer> iterator() { 
     return new MyListIterator(this); 
    } 

} 

这里将是该类一个简单的迭代器：

public class MyListIterator implements Iterator<Integer> { 

    private List<Integer> list; 
    private int index; 

    public MyListIterator(MyList list) { 
     this.list = list; 
     this.index = 0; 
    } 

    public boolean hasNext() { 
     return this.index < this.list.x.size() 
    } 

    public Integer next() { 
     Integer i = this.list.x.get(this.index); 
     this.index += 1; 
     return i; 
    } 

    public void remove() { 
     //Not implemented 
    } 

} 

它可以帮助你看到你将如何使用明确的迭代器：

MyList list = new MyList(); 
Iterator<Integer> iterator = list.iterator(); 
while (iterator.hasNext()) { 
    System.out.println(iterator.next()); 
}