1

これが私のNodeクラスです：

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 に答える