0

以下のようなリストがあります。Javaでこのタイプのリストを使用してバイナリツリーを作成する方法を知りたいです。このタイプのリストに対して、Java でバイナリ ツリー挿入コードを提供してくれる人はいますか?

例えば：

List 1:  AND AND AND G M S T

二分木は次のようになります。 

       AND
   AND                AND 
 G     M            S     T

そして、このリストについて：

List 2: AND AND G M S

二分木は次のようになります。

              AND
  AND          S
 G   M

次の挿入方法を試しました：

public void insert(RDFQuery node,  RDF leafValue) { 
    flag++;
    if ((flag%2)!=0) {
        if (node.left  != null) {
            flag--;
            nodeStore=node.left;
            leftFlag=1;
            insert(node.left, leafValue);
        } 
        else { 
              node.left = new RDFQuery(leafValue);
        }

    }       
    if ((flag%2)==0) {
        if (leftFlag==1) {
            node=nodeStore; 
            leftFlag=0;
        }

        if (node.right  != null) {
              flag--;   
              insert(node.right, leafValue);
        } 
        else { 
              node.right = new RDFQuery(leafValue);
              rightFlag=0;
        }
    }
}
4

1 に答える 1

1

私が考えることができる明白なアルゴリズムのいずれかを使用して両方の例を再現できないため、リストをツリーに変換する方法がわかりません。

行ごとに塗りつぶし、幅を優先

通常、次のレベルに進む前に、左から右にレベルを埋めます。入力例の場合、これは次のツリーになります。

List 2: AND AND G M S

        AND
       /   \
    AND     G
  /    \ 
 M      S

これを実装するにはさまざまな方法があります。1 つは、現在挿入している行のインデックス (深さ) とその行内の新しいリーフのインデックスの 2 つの数値を維持することです。行内のそのインデックスのビット パターンは、最上位ビットのルートから始まる左右の子の順序を示します。深さは、考慮する必要があるビット数、つまり、処理する必要があるビットの中で最も重要なビットを示します。

プレフィックス表記

一方、要素の名前は、それらのいくつかが固定アリティを持っていることを示唆しています。私はすべての場合において二項演算子であると想像ANDしていますが、単純な記号はおそらく nullary です。ただし、この解釈では、最初の例は異なるリストになります。

       AND
     /     \
  AND       AND 
 /   \     /   \         
G     M  S      T

AND ( AND ( G, M ), AND ( S, T ) )
List 1: AND AND G M AND S T

これがあなたの解釈である場合、おそらく現在のノードへの参照を維持し、最後に予想される子が追加された後、まだ子を期待しているノードに到達するまで親から親に切り替えるのが最善でしょう。

于 2012-09-28T06:37:17.103 に答える