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 回答