У меня небольшие трудности с методом вставки для этого домашнего задания. Я сделал большую часть этого, но по какой-то причине, когда моя программа должна вставить узел как правый дочерний элемент в левой части дерева, она просто вставляет его как левый дочерний элемент.
Я делаю свое сравнение странным образом (для многих из них знаки должны быть обратными, но по некоторым причинам это работает), поэтому, пожалуйста, потерпите меня, если у вас возникнут трудности при чтении.
Я знаю, что это ужасный способ реализовать бинарное дерево поиска, и я никогда бы не сделал это в реальном мире, но это домашняя работа, и поэтому - у меня нет выбора.
Любая помощь приветствуется, как всегда. Спасибо!
Редактировать: я знаю, где проблема сейчас. Это внутри метода searchFor (). Вместо законного родителя узла он делает родителя корнем дерева (в этом случае родителем узла всегда является "чашка".)
Теперь, когда это не так, кто-нибудь может предложить решение?
Edit2: вытащил некоторые дополнительные вещи, которые, я не думаю, имеют отношение к проблеме. Я почти уверен, что сузил его до метода 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;
}
}
}