バイナリ検索ツリーのサイズを再帰なしにどのように見つけることができますか？

Question

私は再帰を伴うツリーのサイズを見つける方法を知っていますが、再帰なしでそれを見つける方法は不明です。 これまで私が持っていたことがあります。私はそれが私が木を横切るのを妨げている私のif文であると思う。あなたは、反復1に再帰的なソリューションを変換したいときはいつでも

public int size() { 
    size = 0; 
    NodeWord current = root; 
    while(current != null) { 
     if(current.left != null) { 
      size++; 
     } 
     else { 
      current = current.right; 
     } 
    } 
    return size; 
} 

Answer 1

は、あなたがStackを使用することができます。

• この場合、あなたはNodeは、二分探索木のNodeあるStack<Node>を、使用することができます。

• まず、ルートNodeをスタックにプッシュします。

• 次に、スタックが空になるまで続けるwhileループを作成します。あなたがStackのトップNodeでのぞくとStackにそのNodeの子供たちをプッシュすることができますwhileループの各反復で

• 。子どもがいない場合は、のうちNodeをポップして、それに必要な計算を行います（例ではカウンタを増やすだけです）。

• 現在のNodeとその2つの子を、ツリーの走査順序に応じてプッシュ/ポップする順序を変更できます。