0

アイテムをバイナリツリーに連続した順序で追加するために使用している（幅優先探索アルゴリズムを使用する）次の方法があります。

たとえば、私が持っていた場合

  A
 / \
 B  C
/  
D

次の追加は次のようになります。

  A
 / \
 B  C
/ \ 
D  E

私の問題は、値を正しく返す方法がわからないという事実にあります。最初のnullノードに遭遇したとき、そこに値を挿入することを知っていますが、それを何に挿入しますか？キューから取得しているバイナリツリーに挿入すると、それはルートのサブツリー（または追加しようとしているツリー）であるため、それを返すと完全なツリーにはなりません。

これが私が持っているコードです：

public static <T> BinaryTree<T> addToTree(BinaryTree<T> t1, BinaryTree<T> t2) {
    Queue<BinaryTree<T>> treeQueue = new LinkedList<BinaryTree<T>>();

    while (t1 != null) {
        if (t1.getLeft() == null) {
            t1.attachLeft(t2);
            break;
        }
        treeQueue.add(t1.getLeft());

        if (t1.getRight() == null) {
            t1.attachRight(t2);
            break;
        }
        treeQueue.add(t1.getRight());

        if (!treeQueue.isEmpty()) t1 = treeQueue.remove();
        else t1 = null;
    }
    return t1;
}
4

2 に答える 2

1

わかりました、私は今あなたが求めているものを手に入れていると思います。

幅優先の実装は正しいです。

二分木は一種の「自己完結型」構造です。Aと呼ばれるルートから始め、他の2つの二分木「左」と「右」への2つの参照を使用します。

あなたはから始めます：

    A
   / \
  B  C
 /  
D

そして、Bの右のサブツリーとして二分木Eを追加します。

  A
 / \
 B  C
/ \ 
D  E

実装は、そのまま、新しいサブツリーが追加された場所であるサブツリー「B」を返します。使用しているBinaryTreeの実装はわかりませんが、次のことを期待しています。

"B".attachRight("E");

元のツリーを変更するため、ノードが追加された「新しい」ツリーは「A」で始まるツリーのままです。つまり、何も返す必要はありません。実装が「親」を追跡しているかどうかはわかりません。追跡している場合は、親がnullであるノード（ルート（再び「a」）が見つかるまで、「B」から始まる親階層をトラバースできます）

addToTree（BinaryTree t1、BinaryTree t2）を呼び出した後の答えは、最初の引数として渡した「A」ルートツリーである「t1」です。

于 2012-11-04T19:47:18.763 に答える
0

あなたの問題はここにあります：

if（！treeQueue.isEmpty（））t1 = treeQueue.remove（）; それ以外の場合、t1 = null;

ノードに子がない場合は、その参照をnullに設定して、whileを中断しますが、これは関数が返す値でもあります。一時変数を使用して、返したいノードへの参照を格納できます。

于 2012-11-04T02:41:03.897 に答える