3

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

  A
 / \
 B  C
/  
D

次の追加は次のようにしたいと思います。

  A
 / \
 B  C
/ \ 
D  E

しかし、入力するアイテムの次の場所がどこになるかを検出するのに非常に苦労しています. 次のコードがあります。

    public static BinaryTree<String> addToTree(BinaryTree<String> tree, String name) {
        if (tree.getLeft() == null) {
            BinaryTree<String> newTree = new BinaryTree<String>();
            newTree.makeRoot(name);
            tree.attachLeft(newTree);
        }
        else if (tree.getRight() == null) {
            BinaryTree<String> newTree = new BinaryTree<String>();
            newTree.makeRoot(name);
            tree.attachRight(newTree);
        }
        // Both are non-null
        else {
            if (tree.getLeft().getLeft() == null || tree.getLeft().getRight() == null) {
                tree.attachLeft(addToTree(tree.getLeft(), name));
            }
            else if (tree.getRight().getLeft() == null || tree.getRight().getRight() == null) {
                tree.attachRight(addToTree(tree.getRight(), name));
            }
        }

        return tree;
    }

ただし、最大 3 レベルのツリーでしか機能しません。4 番目を追加しようとすると、何も追加されなくなります。

次のアイテムがnullの場所を見つけてそこに追加するように実装するにはどうすればよいですか?

またcheckNullity()、ツリーを取得してその子が null かどうかを確認する方法も考えましたが、子の子を取得する方法もわかりませんでした。null の場所を見つけて、そこに追加したかったのです。

誰かがいくつかの入力を提供できますか?

4

5 に答える 5

2

これを達成するために、幅優先トラバーサルを変更できます。キューからアイテムをポップアップするときは、子のいずれかが空かどうかを確認してください。最初の空の子スロットは、追加したい場所です。

addNode(root, newNode) 
  q = empty queue
  q.enqueue(root)
  while not q.empty do
    node := q.dequeue()
    if node.left == null
      //create new node as nodes left child
      return
    q.enqueue(node.left)
    if node.right == null
      //create new node as nodes right child
      return
    q.enqueue(node.right)
于 2012-11-03T23:06:30.747 に答える
0

なぜなら、要素を左から右の順に、同じレベルから始めて挿入したいからです。幅優先探索を調べることをお勧めします。基本的な実装を提供しました。

public void insert(child, root){

    if (root == null){
        root = child
    }

    Node iter = root
    Myqueue q = new Myqueue(); //Implementation of the Java Queue Interface

    while (iter!=null){

        //Check: If the left node exists, enque in the que
        if(iter.is_left()){
            q.insert(iter.left)
        }
        else{
            iter.left = child
            iter = null
        }

        //Similary for the right
        if(iter.is_right()){
            q.insert(iter.right)
        }
        else{
            iter.right = child
            iter = null
        }
        if (iter != null){
        iter = q.poll() //Retreiving the head of the queue
        }
    }
}
于 2012-11-03T23:30:00.283 に答える
0

これは確かにあなたが求めているツリーを作成しますが、それがあなたが望むものであるかどうかはまだわかりません：

public class BinaryTree<T> {
  T root = null;
  BinaryTree<T> left = null;
  BinaryTree<T> right = null;

  public BinaryTree<T> getLeft() {
    return left;
  }

  public BinaryTree<T> getRight() {
    return right;
  }

  public void makeRoot(T root) {
    this.root = root;
  }

  public void attachLeft(BinaryTree<T> tree) {
    left = tree;
  }

  public void attachRight(BinaryTree<T> tree) {
    right = tree;
  }

  public static BinaryTree<String> addToTree(BinaryTree<String> tree, String name) {
    if (tree.getLeft() == null) {
      BinaryTree<String> newTree = new BinaryTree<String>();
      newTree.makeRoot(name);
      tree.attachLeft(newTree);
    } else if (tree.getRight() == null) {
      BinaryTree<String> newTree = new BinaryTree<String>();
      newTree.makeRoot(name);
      tree.attachRight(newTree);
    } else {
      addToTree(tree.getLeft(), name);
    }
    return tree;
  }

  public static void main(String[] args) {

    try {
      BinaryTree<String> tree = new BinaryTree<String>();
      String add = "ABCDEFG";
      tree.makeRoot(add.substring(0, 1));
      for (int i = 1; i < add.length(); i++) {
        addToTree(tree, add.substring(i, i + 1));
      }
      System.out.println("Done");
    } catch (Throwable e) {
      e.printStackTrace();
    }
  }
}

追加した

私はその質問を明らかに誤解しました。おそらく例が役立つでしょう。

次の文字列から一度に1文字ずつ（文字列として）追加した場合、何を期待しますか？

「ABCDEFG」

  A
 / \
 B   C
/ \  | \
D  E F  G?

または、他の何か。

それならあなたは何を期待しますか

「ADEFGBC」

  A
 / \
 D   E
/ \  | \
F  G B  C

また

  A
 / \
 B   C
/ \  | \
D  E F  G

または、他の何か？

どちらも可能ですが、どちらの場合も値がわかりません。

于 2012-11-03T23:34:05.243 に答える
0

要素をバイナリ ツリーの適切な場所に追加するには、各ノードのルートから次の質問に答える必要があります。左側または右側のサブツリーに降りるべきですか? これが問題の要約です。各ノードでこの決定を行う方法です。

始めればOKです。ノードに左のサブツリーがない場合、新しく追加されたリーフはその左の子になります。また、ノードに左のサブツリーがあり、右のサブツリーがない場合、新しく追加されたリーフはその右の子になります。

しかし、ノードに両方のサブツリーがあるかどうかを判断するにはどうすればよいでしょうか? このためには、決定に使用できるノードに何らかの情報を保持する必要があります。1 つの可能性は、各ノードでそのサブツリーの合計サイズを維持することです。次に、両方のサブツリーが同じサイズの場合、両方が完全にバランスが取れていることを意味するため、左側に追加します。それ以外の場合、左のサブツリーのサイズが2^n-1の場合は、バランスが取れている (右のサブツリーはバランスが取れていない) ことを意味するため、右に追加します。そうでない場合は、左に追加します。

ただし、それよりもはるかに簡単に実行できます。ツリーは常にこの構造を維持するため、ツリーを として表すことができますArrayList。ルート ノードはインデックス0にあり、インデックスnのノードの場合、その子はインデックス _2*n+1_ および _2*n+2_ にあります。これがバイナリ ヒープの実装方法です。このようにして、新しいノードを追加するためのO(1)時間の複雑さを得ることができます - リストの最後に追加するだけです。(ただし、回転などの古典的なツリー操作が必要な場合、この実装は機能しません。)

于 2012-11-04T15:14:44.590 に答える
0

ツリーにノードを追加するときに、すべてのノードを列挙できます。n- 番目のノードをツリーに追加する場合、それはn/2- 番目のノードの子になります: left の場合n%2 == 0と right の場合n%2 == 1。

于 2012-11-03T23:10:08.187 に答える