0

BST に要素を追加しようとしています。私はそれを行う方法について考えていますが、私の実装は破壊的であり、元のルートは保持されません (したがって、ツリーは基本的に役に立たなくなります)。ツリーはリストに基づいており、このメソッドは再帰に基づいています。私の本当の問題は、元のルートを維持することです。ジェネリックを使用しています。

これまでのところ、私が持っているもの:

public void addElement(E elem, Node<E> root) {

elem の値でノードを作成し、それを newNode と呼びます

ケース 1: ツリーが空です

root = newNode();
return; //End of method.

それ以外の場合は、ツリーの検索を続けます (アウト ノード a の値をツリーのルートと比較します。

if (!root.hasLeft() && !root.hasRight) { //if the root in question has no children
    if (elem < rootValue) {     //Set the element as the left element
      root.setLeft(newNode);
    }
    else {                      //Set the element as the right element.
      root.setRight(newNode);
    }
  } 

  else {

    if (E < root.getElem()) {              
//This is where the value of our node is compared to the value of the root, which we passed in.
//(I know that we can't use the < and > operators with generics, but assume it works).

  root = root.getLeft() //Left node is new root
  addElement(elem, root); //Call the method again
}
else {  
  root = root.getRight(); //Right node is new root
  addElement(elem, root)  //Call method again
}
  }

}

これが重複/漠然とした質問である場合はご容赦ください。これはSOに関する私の最初の投稿であり、私は一種の初心者です。

4

1 に答える 1

0 
if (!root.hasLeft() && !root.hasRight) {

このロジックは間違っています。左の子も右の子もない場合、左の子のみを「設定」することを検討しています。この変更により、次のようになります。

void addElement(elem, root)
{
    if (elem < root.value) {  
      if(!root.hasLeft())
          root.setLeft(newNode);
      else
          addElement(elem, root.getLeft());
    }
    else {    
      if(!root.hasRight())   
          root.setRight(newNode);
      else             
          addElement(elem, root.getRight());
    }
}

次のメソッド呼び出しに渡すだけで、クラスのルートを変更するべきではありません。これにより、ルートが保持されます。

ところで、あなたはrootValue = root.valueどこか似たようなものを持っていると思いますか？

于 2013-11-11T19:01:31.777 に答える