1

这是我的节点类：

private class Node {
    private int key;         // the key field
    private Object data;     // the rest of the data item
    private Node left;       // reference to the left child/subtree
    private Node right;      // reference to the right child/subtree
    private Node parent;     // reference to the parent

.. 等等。

这是带有 next() 和 hasNext() 方法的中序迭代器：

private class inorderIterator implements LinkedTreeIterator {

    private Node nextNode;

    private inorderIterator() {
        // The traversal starts with the root node.
        nextNode = root;
        if(nextNode == null)
           return;
        while (nextNode.left != null)
           nextNode = nextNode.left;
    }

    public boolean hasNext() {
        return (nextNode != null);
    }

    public int next() {
        if(!hasNext()) 
            throw new NoSuchElementException();             

        Node r = nextNode;

        if (nextNode.right != null) {
            nextNode = nextNode.right;

            while (nextNode.left != null) {
                nextNode = nextNode.left;
            }

            return r.key;
        } else while (true) {
            if (nextNode.parent == null) {
                nextNode = null;
                return r.key;
            }

            if (nextNode.parent.left == nextNode) {          
                nextNode = nextNode.parent;
                return r.key;    
            }

            nextNode = nextNode.parent;                   
        }            
        return r.key; 
    }
}

问题是，它只打印左子树上的左节点。例如，对于具有根节点 17、左节点 15 和右节点 19 的树，它只打印 15。
所以它永远不会进入右子树。

我猜问题出在这else while (true)部分，但我不知道如何解决这个问题。

4

3 回答 3

2

您可以尝试递归方法。

就像是：

public void printTreeInOrder(Node node){
   if(node.left != null){
      printTree(node.left);
   }
   System.out.println(node.key);
   if(node.right != null){
      printTree(node.right);
   } 
}

如果您将此方法传递给根节点，它应该会为您打印出整个树。

我希望这有帮助。

最好的。

于 2015-11-18T20:10:58.130 回答
1

原来我的节点的父字段没有被正确更新。一旦解决了这个问题，迭代器就可以正常工作。

于 2015-11-18T20:05:13.033 回答
0

我会用这个辅助方法使用堆栈：

Node advance_to_min(Node r)
  {
    while (r.left != null)
      {
        s.push(r);
        r = r.left;
      }
    return r;
  }

第一个节点顺序是通过在根上调用此方法给出的。就像是：

curr = advance_to_min(curr);

然后我会这样实现next()：

void next()
  {
    curr = curr.right;
    if (curr != null)
      {
        curr = advance_to_min(curr);
        return;
      }

    if (s.is_empty())
      curr = null;
    else
      curr = s.pop();
  }

curr堆栈s将是迭代器属性。curr将指向中序序列中的当前节点。

O(lg n)每次调用的最坏情况下的成本next()（如果树趋于平衡）并且该方法不需要父指针；因此，它与使用父指针具有相同的空间成本，但仅在最坏的情况下

于 2015-11-18T23:33:55.890 回答