Симметричных итератор для бинарного дерева - ява

Question

Вот мой Узел класс:

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 

.. и так далее.

Это Симметричное итератор со следующими() и 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), но я не могу понять, как это исправить.

Answer 1

Оказывается, что родительское поле моих узлов не обновлялось должным образом. Как только это было исправлено, итератор работал правильно.

Answer 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); 
    } 
} 

Если вы прошли этот метод корневого узла он должен распечатать все дерево для вас.

Надеюсь, это поможет.

Лучший.

Answer 3

Я хотел бы использовать стек с этим вспомогательным методом:

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() (если дерево имеет тенденцию быть сбалансированным), и подход не требует указателей родителей; поэтому он будет иметь одинаковую стоимость пространства, чем использование указателей родителя, но только в худшем случае.