0
我對這個家庭作業的插入方法有點困難。我完成了大部分工作，但由於某種原因，只要我的程序應該在樹的左側插入節點作爲右側子節點，它就會將其作爲左側子節點插入。在BST的左側插入正確的孩子，反之亦然
我有一種奇怪的方式做我的比較（標誌應該顛倒了很多，但因爲某種原因，它的工作原理），所以如果您在閱讀時遇到困難，請耐心等待。
我知道這是一個可怕的方式來實現一個二叉搜索樹，我永遠不會在現實世界中做它，但它是作業，因此 - 我別無選擇。
任何和所有的幫助一如既往的讚賞。謝謝！
編輯：我知道問題現在在哪裏。它位於searchFor（）方法內。而不是節點的合法父節點，它使父節點成爲樹的根節點（在這種情況下節點的父節點總是「杯」）。
現在，這是超出了，任何人都可以提供解決方案？
編輯2：採取了一些額外的東西，我不認爲是相關的問題。我很確定我已經縮小到searchFor（）方法。每當我調用返回當前節點的父節點時，它將返回樹的根（「杯」）。我認爲這就是爲什麼我遇到了問題，因爲它基於此插入。
感謝所有幫助到目前爲止，我真的很感激它。
public class BinarySearchTree //implements Comparator
{
private Comparator<Object> dataComparator;
private LinkedListWithTwoLinks tree;
public static void main (String[] args)
{
BinarySearchTree bst;
Object hold;
String[] words = {"cup", "shaker", "cord", "key", "addressbook", "date", "address", "cupcake",
"card", "tape", "page", "day", "key", "days", "dayt"};
bst = new BinarySearchTree(new AlphabeticComparator());
System.out.println("[1]: original tree");
for(int i=0; i<words.length; i++) if (!bst.insert(words[i])) { System.out.println(">>>>>>>>>>>>> " + words[i] + " is already in tree"); }
bst.inOrder();
}
public static class AlphabeticComparator implements Comparator <Object>
{
public int compare(Object x, Object y)
{
if (x == y) return 0;
if (x == null) return -1;
if (y == null) return 1;
return (x.toString().compareTo(y.toString()));
}
}
public static class LastCharacterComparator implements Comparator <Object>
{
public int compare(Object x, Object y)
{
String xs;
String ys;
if (x == y) return 0;
if (x == null) return -1;
if (y == null) return 1;
xs = x.toString();
ys = y.toString();
if (xs.length() == 0) return -1;
if (ys.length() == 0) return 1;
return (xs.charAt(xs.length()-1) - ys.charAt(ys.length()-1));
}
}
public BinarySearchTree(Comparator<Object> y)
{
dataComparator = y;
this.tree = new LinkedListWithTwoLinks();
}
private int compare(BinarySearchTreeElementInterface s, Object data)
{
return this.dataComparator.compare(s, data);
}
public boolean insert(Object data)
{
boolean success;
BinarySearchTreeElementInterface current;
BinarySearchTreeElementInterface parent;
current = getRoot();
parent = null;
success = false;
if (current == null)
{
getTree().insert(data);
return true;
}
else
{
SearchResult insert;
insert = searchFor(data);
//if (data == "shaker") {System.out.println(insert.resultOfCompare); }
while (current != null)
{
if (insert.insertAsLeftChild())
{
//if (data == "card") {System.out.println("IN RIGHT");}
//System.out.println("IN LEFT");
parent = current;
current = current.getLeftChild();
}
else if (insert.insertAsRightChild())
{
//if (data == "card") {System.out.println("IN RIGHT");}
parent = current;
current = current.getRightChild();
}
}
if (insert.insertAsLeftChild())
{
//parent.setLeftChild(insert.getParentOfLocation()); //insert.getParentOfLocation()
//System.out.println(data);
getTree().insertUsingPrior(parent, data);
//System.out.println(insert.getParentOfLocation()+" bye left");
// System.out.println(insert.getLocation()+" hi");
success = true;
}
else if (insert.insertAsRightChild())
{
//parent.setRightChild(insert.getParentOfLocation());
//System.out.println(data);
getTree().insertUsingNext(parent, data);
//System.out.println(insert.getParentOfLocation()+" bye right");
// System.out.println(insert.getLocation());
success = true;
}
else {success = false;}
/*
figures out if it should be inserted as a left or right child
then call insert using prior/next
}*/
}
return success;
}
private SearchResult searchFor(Object data)
{
/*returns either to node containing the data or the parent of the node of which the data would be a child of*/
if (getTree() == null) {throw new ListEmptyException("Tree is empty!");}
BinarySearchTreeElementInterface currentLocation;
BinarySearchTreeElementInterface parent;
SearchResult destination;
parent = getRoot();
currentLocation = parent;
while (currentLocation != null)
{
if (currentLocation.getData() == data)
{
return new SearchResult(parent, currentLocation, compare(currentLocation, data));
}
if (compare(currentLocation, data) < 0)
{
//System.out.println("IN LEFT");
parent = currentLocation;
currentLocation = currentLocation.getLeftChild();
}
else if (compare(currentLocation, data) > 0)
{
//System.out.println("IN RIGHT");
parent = currentLocation;
currentLocation = currentLocation.getRightChild();
}
}
destination = new SearchResult(parent, currentLocation, compare(parent, data));
//System.out.println(destination.resultOfCompare);
return destination;
/*
* use nothing but BSTEIs
*/
}
public void inOrder()
{
inOrder(getRoot());
}
public void inOrder(BinarySearchTreeElementInterface BSTroot)
{
//System.out.println(BSTroot.getRightChild());
if (BSTroot != null)
{
inOrder(BSTroot.getLeftChild());
System.out.println(BSTroot.getData());
inOrder(BSTroot.getRightChild());
}
/*if (BSTroot.getLeftChild() != null)
{
}
System.out.println(BSTroot.getData());
if (BSTroot.getRightChild() != null)
{
inOrder(BSTroot.getRightChild());
//System.out.println(BSTroot.getData());
}
System.out.println(BSTroot.getData());*/
}
public int size()
{
return tree.size();
}
/*SEARCH RESULT CLASS-----------------------------------------------------------------------------------------*/
public class SearchResult
{
BinarySearchTreeElementInterface location;
BinarySearchTreeElementInterface parentOfLocation;
int resultOfCompare;
public SearchResult(BinarySearchTreeElementInterface parent, BinarySearchTreeElementInterface locate, int comp)
{
this.parentOfLocation = parent;
this.location = locate;
this.resultOfCompare = comp;
}
public BinarySearchTreeElementInterface getLocation()
{
return this.location;
}
public BinarySearchTreeElementInterface getParentOfLocation()
{
return this.parentOfLocation;
}
public boolean insertAsLeftChild()
{
if (resultOfCompare > 0) {return true;}
else {return false;}
}
public boolean insertAsRightChild()
{
if (resultOfCompare < 0) {return true;}
else {return false;}
}
public boolean locationIsLeftOfParent()
{
return this.location == parentOfLocation.getLeftChild();
}
public boolean locationisRightOfParent()
{
return this.location == parentOfLocation.getRightChild();
}
public boolean wasSearchSuccessful()
{
return this.parentOfLocation == this.location;
}
public void setLocation(BinarySearchTreeElementInterface newLocation)
{
this.location = newLocation;
}
public void setLocationOfParent(BinarySearchTreeElementInterface newParentLocation)
{
this.parentOfLocation = newParentLocation;
}
}
}
這是很多代碼 - 你不知道哪裏出了問題？您是否使用調試器來逐步完成？ – mort
很確定我的問題是來自我在二進制搜索樹類中的插入方法，但我想我會提交這一切，以防萬一有人想看看它。 – solllodolllo