首先，重要的是要提到我要描述的方式和您的方式都不允许“适当的”树遍历。您将始终只获得一个包装在Node对象中的键。如果您想实际遍历树并Node在位置 x 处获得 a，而不是其值，您可以修改您和我的版本，以不返回非叶节点的键，而是返回节点本身。
通过围绕父母堆栈编写自己的迭代器，也可以有不同的选择。当涉及到时间限制时，此选项不一定更好，但您将在没有递归的情况下进行操作，因此不会出现堆栈溢出问题。如果您稍微考虑一下，您会发现，这只是一种“递归”执行操作的非常手动的方式。这是它的要点：
假设最左下角的元素（在图形插图中）是您的第一个元素。让我们称之为A。现在要得到你，A你必须遍历你的树，传递所有的“父母” A（显然它只有一个直接父母，但我指的是父母的父母......）。现在我们可以将每个父级推A到一个Stack<Node>-type 对象上。让我们称之为S。现在，一旦我们到达A，我们将拥有Ain的路径S（如目录路径）。这足以让我们进行缓慢的递归。这种遍历方法将手动执行您的递归方法“自动”执行的操作。在这里，我们实际上在树中移动，而不是使用额外的List.
class TreeIterator implements Iterator
{
Node current, recentChild;
Stack<Node> parentsOfCurrentNode; //our S
TreeIterator(Node root)
{
current = root;
while(current.children.size() != 0)
{
parentsOfCurrentNode.push(current);
current = current.children.get(0); //getting our initial A
}
}
public Node next()
{
if(current.children.size() == 0)
{
recentChild = current;
current = parentsOfCurrentNode.pop();
return current;
}
else if(recentChild == current.children.get(0))
{//We just came from the left child so now we go to the middle one
Node out = new Node(current.keys.get(0));// will always exist
current = current.children.get(1); //middle path
while(current.children.size() != 0)
{
parentsOfCurrentNode.push(current);
current = current.children.get(0); /*traversing again to the lowest value
in the path with no children,
triggering the first if-case when next is called*/
}
return out;
}
else if(recentChild == current.children.get(1))
{//We just came from the right/middle child so now we go to the parent/right node
if(current.children.size() == 2)
{
recentChild = current;
if(!parentsOfCurrentNode.isEmpty())
{
current = parentsOfCurrentNode.pop();
while(current.children.get(current.children.size()-1) == recentChild)
{//testing for always rigth-most Node
if(parentsOfCurrentNode.isEmpty())
{
return null; //no more elements
}
recentChild = current;
current = parentsOfCurrentNode.pop();
}
//we are now guaranteed to be at a point where the most recent node was not the right most node
if(recentChild == current.children.get(0))
{//We just came from the left child so now we go to the middle one
Node out = new Node(current.keys.get(0));// will always exist
current = current.children.get(1); //middle path
while(current.children.size() != 0)
{
parentsOfCurrentNode.push(current);
current = current.children.get(0); /*traversing again to the lowest value
in the path with no children,
triggering the first if-case when next is called*/
}
return out;
}
else if(recentChild == current.chidren.get(1))
{//Can only happen for size 3 de facto
Node out = new Node(current.keys.get(1)//
current = current.children.get(2); //right path
while(current.children.size() != 0)
{
parentsOfCurrentNode.push(current);
current = current.children.get(0); /*traversing again to the lowest value
in the path with no children,
triggering the first if-case when next is called*/
}
return out;
}
}
}
else
{ //this is size 3 so we continue
Node out = new Node(current.keys.get(1));//
current = current.children.get(2); //right path
while(current.children.size() != 0)
{
parentsOfCurrentNode.push(current);
current = current.children.get(0); /*traversing again to the lowest value
in the path with no children,
triggering the first if-case when next is called*/
}
return out;
}
}
else
{//we are coming from right child and current is of size 3
recentChild = current;
if(!parentsOfCurrentNode.isEmpty())
{
current = parentsOfCurrentNode.pop();
while(current.children.get(current.children.size()-1) == recentChild)
{//testing for always rigth-most Node
if(parentsOfCurrentNode.isEmpty())
{
return null; //no more elements
}
recentChild = current;
current = parentsOfCurrentNode.pop();
}
//we are now guaranteed to be at a point where the most recent node was not the right-most node
if(recentChild == current.children.get(0))
{//We just came from the left child so now we go to the middle one
Node out = new Node(current.keys.get(0));// will always exist
current = current.children.get(1); //middle path
while(current.children.size() != 0)
{
parentsOfCurrentNode.push(current);
current = current.children.get(0); /*traversing again to the lowest value
in the path with no children,
triggering the first if-case when next is called*/
}
return out;
}
else
{//Can only happen for size 3 de facto
Node out = new Node(current.keys.get(1));//
current = current.children.get(2); //right path
while(current.children.size() != 0)
{
parentsOfCurrentNode.push(current);
current = current.children.get(0); /*traversing again to the lowest value
in the path with no children,
triggering the first if-case when next is called*/
}
return out;
}
}
}
return null; //if it ever gets here something is seriously wrong
}
} //end of class
所以这只是Java接口中next()指定的方法Iterator（我猜这就是你正在使用的，因为你使用的语法）。请记住，您还必须实现hasNext()和 optional remove()，在这种情况下，它现在实际上将从您的树中删除。hasNext()可以通过
a) 在构造迭代器时找到最右边的元素，并在调用current时与它进行比较。hasNext()这种方法使其成为静态意味着不会考虑对树的更改。
b) 检查是否current已经是最右边的元素。如果你想这样做，只要我们遍历回根时查看代码并检查我们现在所在的节点是否是最右边的节点（注意你必须克隆，Stack否则你将失去所有父母）。
后一种检查是动态的，但速度很慢。因此，第一次检查对于时间效率来说要好得多。
总的来说，这种方法保存不会导致 astack overflow并且它使用更少的内存，因为我们在其Tree自身中移动。另一方面，它在访问期间较慢，O(d)在运行时d是树的深度，是最大时间复杂度。另一个问题是该hasNext()方法需要链接到最右边的元素才能节省时间（O(1)）。否则，它将始终O(d)找出您的迭代器是否有下一个元素。因此，从不投掷 a 的优势在于StackOverflowError与总体上更高的时间复杂度相竞争。对你来说更重要的是你自己决定。（编辑：您应该记住，最坏情况的复杂性是O(d)而不是O(n)（其中n是树中元素的数量）。）
你问你能做些什么来提高效率：没有。你总会在某处失去一些效率。我喜欢您将所有数据放入 List 并采用它的迭代器的方法，它既漂亮又流畅，而且绝对比我提出的变体更有效。我只是想给你一个不同的角度，因为即使你的问题很广泛，它也是有道理的。简单的答案仍然是你正在做的遍历最有效，你只需要告诉自己没有人会创建一个Tree足够大的来破坏它。
也不要逐字逐句地使用代码，它可能不是 100% 没有错误的。我没有心情Node像你那样建立一个班级，所以它可能无法 100% 与你所拥有的一起工作。如果你真的需要巨大的 2-3 树的东西并选择我的方法，根据你的需要重写它。