バイナリ検索ツリーでの検索で再帰の代わりに繰り返しを使用

Question

バイナリ検索ツリーでアイテムを検索していました。私はそれが 再帰の代わりに反復を使用するように検索（）メソッドを書き換えたい

public class Node { 
     public int key; 
     public Object data; 
     public Node left; 
     public Node right; 
     } 

public static Object search(Node root, int key) { 
    if (root == null) 
    return null; 
    else if (key == root.key) 
    return root.data; 
    else if (key < root.key) 
    return searchTree(root.left, key); 
    else 
    return searchTree(root.right, key); 
    } 

：私はこのコードを発見しました。私はこのようにしました：

public static Object search(Node root, int key) { 
     if (root == null) 
     return null; 
     else if (key == root.key) 
     return root.data; 
     else if (key < root.key) { 
      Iterator iter = root.left.iterator(); 
     while (iter.hasNext()) { 
      object item = iter.next(); 
      if(iter.key.equals(key)) { 
       return item.data; 
      } 
     } 
     } else { 
      Iterator iter = root.right.iterator(); 
      while (iter.hasNext()) { 
       object item = iter.next(); 
       if(iter.key.equals(key)) { 
        return item.data; 
       } 
      } 
     } 
    } 

私は正しくやっていますか？

おかげ

Answer 1

は正直言って - 私はかなりあなたのイテレータのアプローチで失われた、非再帰的なアプローチとして、あなたがスタックを使用することができます。

1. ルートにスタックをプッシュします。
2. スタックの要素をポップし、ノードの条件を検索します（スタックブレークの要素なし、検索に失敗しました）。
3. 条件が一致して、破損しています。
4. 基準が左と右の子をスタックに押し込むのに一致しません。
5. 手順2に戻ります。