バイナリツリートラバーサル：再帰、反復、および親へのポインター

ここを含む、二分木の基本について説明します 。 「5コペック」を追加します。この投稿では、バイナリツリーの走査に関連するマテリアルを体系化します。つまり、再帰機能と反復機能を比較し、親ノードへのポインターを使用する可能性について説明します。



したがって、... Java言語では、ノードクラスの形式は次のとおりです。

public class Node { Node left; Node right; Node parent; String value; public Node(Node p, String v){ parent=p; value=v; } … }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

注 ：親親へのポインター-原則として、あまり意味がありませんが、見出しが示すように、多くの場合に役立ちます。



ツリーのバイパス -ツリーのすべてのノードの順次処理（表示、変更など）。各ノードは厳密に1回処理されます。 これにより、ツリーノードが直線的に配置されます。



軌跡に応じて、2種類のバイパスが区別されます。

-水平（ワイド）; そして

-垂直（深さ）。



水平走査には、レベル（レベル順）でツリーを走査することが含まれます-最初に、現在のレベルのすべてのノードが処理され、その後、下位レベルへの遷移が実行されます。





垂直トラバーサルでは、現在のノードとその右および左のサブツリーのノードの処理順序が異なり、この基準に従って、垂直トラバーサルには3つのオプションがあります。

-直接（プレフィックス、事前順序付け）：頂点-左サブツリー-右サブツリー。

-逆（挿入、順序付け）：左サブツリー-頂点-右サブツリー。 そして

-終了（後置、後順）：左サブツリー-右サブツリー-頂点。



バイパス自体はすべての場合で基本的に同じであり、処理順序は異なります。 ツリーノードの処理が行われる順序を表すには、「トラバースパス」に従うのが便利です。 ダイレクトバイパスでは、ノードはノードの左のポイントで処理され、ノードの下部とノードの右の端で処理されます。

言い換えると、特定のノードに「存在する」場合、そのノードを処理する必要があるかどうか、どこに移動するかを知る必要があります。

再帰

垂直トラバーサルの3つのバリアントはすべて、再帰関数によって基本的に実装されます。

  void recPreOrder(){ treatment(); if (left!=null) left.recPreOrder(); if (right!=null) right.recPreOrder(); } void recInOrder(){ if (left!=null) left.recInOrder(); treatment(); if (right!=null) right.recInOrder(); } void recPostOrder(){ if (left!=null) left.recPostOrder(); if (right!=null) right.recPostOrder(); treatment(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

再帰は、クロールするときだけでなく、ツリーを構築するとき、ツリー内を検索するとき、およびバランスを取るときにも非常に便利です。 ただし、再帰では、水平方向のツリートラバーサルは許可されません。 この場合、およびソフトウェアスタックのオーバーロードに関する懸念がある場合は、反復アプローチを使用する必要があります。

コンテナ

反復を使用する場合、訪問されたが処理されていないノードに関する情報を保存する必要があります。 スタックコンテナ（垂直トラバーサル用）とキュー（水平トラバーサル用）が使用されます。

水平バイパス：

キューの最初のノードを処理します。子ノードがある場合は、それらをキューの最後に配置します。 次の反復に進みます。

  static void contLevelOrder(Node top){ Queue<Node> queue=new LinkedList<> (); do{ top.treatment(); if (top.left!=null) queue.add(top.left); if (top.right!=null) queue.add(top.right); if (!queue.isEmpty()) top=queue.poll(); }while (!queue.isEmpty()); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

垂直ダイレクトバイパス：

現在のノードを処理します。正しいサブツリーがある場合は、さらに処理するためにスタックに追加します。 左のサブツリーのノードに渡します。 左側のノードがない場合は、スタックから最上位ノードに移動します。

  static void contPreOrder(Node top){ Stack<Node> stack = new Stack<> (); while (top!=null || !stack.empty()){ if (!stack.empty()){ top=stack.pop(); } while (top!=null){ top.treatment(); if (top.right!=null) stack.push(top.right); top=top.left; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

垂直バックトレース：

現在のノードから左下のノードに「下って」、訪問したすべてのノードをスタックに追加します。 スタックの最上位ノードを処理します。 現在のノードに正しいサブツリーがある場合、正しいノードから次の反復を開始します。 正しいノードがない場合、降下ステップをスキップして、スタックから次のノードの処理に進みます。

  static void contInOrder(Node top){ Stack<Node> stack = new Stack<> (); while (top!=null || !stack.empty()){ if (!stack.empty()){ top=stack.pop(); top.treatment(); if (top.right!=null) top=top.right; else top=null; } while (top!=null){ stack.push(top); top=top.left; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

垂直端バイパス：

ここでは状況は複雑です-往復とは対照的に、降下順序に加えて、正しいサブツリーがすでに処理されているかどうかを知る必要があります。 1つの解決策は、関連情報を保存するノードの各インスタンスにフラグを含めることです（考慮されません）。 別のアプローチは、スタック順序で直接「コーディング」することです。降下中に、次のノードが後で適切なサブツリーを処理する必要がある場合、シーケンス「親、右ノード、親」がスタックにプッシュされます。 したがって、スタックからノードを処理するときに、適切なサブツリーを処理する必要があるかどうかを判断できます。

  static void contPostOrder(Node top){ Stack<Node> stack = new Stack<> (); while (top!=null || !stack.empty()){ if (!stack.empty()){ top=stack.pop(); if (!stack.empty() && top.right==stack.lastElement()){ top=stack.pop(); }else{ top.treatment(); top=null; } } while (top!=null){ stack.push(top); if (top.right!=null){ stack.push(top.right); stack.push(top); } top=top.left; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

親ポインターについて

クラスインスタンスに親へのポインタが存在すると、ツリーの構築とバランス調整に問題が生じます。 ただし、ツリーノードのいずれかからそのノードのいずれかに「到達」する機能は便利です。 それは、右の子孫から来たのか左から来たのかにかかわらず、上位レベルへの「上昇」中に監視する必要があるすべてのものです。

そのため、親ポインターを使用すると、垂直方向のエンドトラバーサルのコードが見えます。

  static void parentPostOrder(Node top){ boolean fromright=false; Node shuttle=top, holder; while(true){ while (fromright){ shuttle.treatment(); if (shuttle==top) return; holder=shuttle; shuttle=shuttle.parent; fromright=shuttle.right==holder; if (!fromright && shuttle.right!=null) shuttle=shuttle.right; else fromright=true; } while (shuttle.left!=null) shuttle=shuttle.left; if (shuttle.right!=null) shuttle=shuttle.right; else fromright=true; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

既に述べたように、親ポインターが解決できるタスクの別のクラスは、ツリー内を移動します。

したがって、「ツリー内の向き」なしで現在のノードからn番目のノードに移動するには、最初から既知のノードに移動し、さらに別のnノードに移動する必要があります。 ツリーをトラバースするときに、親ポインターを使用して、現在のノード（開始）からノードのステップを移動すると、次の形式になります。

  public static Node walkTheTree(Node start, int steps){ boolean fromright=true; Node shuttle=start, holder; if (shuttle.right!=null){ shuttle=shuttle.right; while (shuttle.left!=null) shuttle=shuttle.left; fromright=false; } int counter=0; do{ while (true){ if (!fromright && ++counter==steps) return shuttle; if (!fromright && shuttle.right!=null){ shuttle=shuttle.right; break; } holder=shuttle; shuttle=shuttle.parent; fromright=(holder==shuttle.right); } while (shuttle.left!=null) shuttle=shuttle.left; }while (true); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

注 ：一般的なケースでは、ツリーを超えて（ルートノードより上に）移動しようとする可能性を防ぐことも必要です。