挿入メソッドと検索メソッドを取得しました。二分探索ツリーをループしてノードを取得するような方法を使用し、他の二分探索ツリーでそれを検索し、それが真であれば挿入する方法を考えていました。その要素ですが、問題は、たとえばlinkedListとは異なり、最初にノードを取得する方法が考えられないため、インデックスに基づいてノードを取得する方法を思いつかないことです。要約すると、私は実際にその質問を解決するための適切な方法を知りません。
public class BinarySearchTree extends BinaryTree {
//default constructor
//Postcondition: root = null;
public BinarySearchTree() {
super();
}
//copy constructor
public BinarySearchTree(BinarySearchTree otherTree) {
super(otherTree);
}
public class BinaryTree {
//Definition of the node
protected class BinaryTreeNode {
DataElement info;
BinaryTreeNode llink;
public DataElement getInfo() {
return info;
}
public BinaryTreeNode getLlink() {
return llink;
}
public BinaryTreeNode getRlink() {
return rlink;
}
BinaryTreeNode rlink;
}
protected BinaryTreeNode root;
//default constructor
//Postcondition: root = null;
public BinaryTree() {
root = null;
}
//copy constructor
public BinaryTree(BinaryTree otherTree) {
if (otherTree.root == null) //otherTree is empty
{
root = null;
} else {
root = copy(otherTree.root);
}
}
public BinaryTreeNode getRoot() {
return root;
}
public boolean search(DataElement searchItem) {
BinaryTreeNode current;
boolean found = false;
current = root;
while (current != null && !found) {
if (current.info.equals(searchItem)) {
found = true;
} else if (current.info.compareTo(searchItem) > 0) {
current = current.llink;
} else {
current = current.rlink;
}
}
return found;
}
public int countEven() {
return countEven(root);
}
public void insert(DataElement insertItem) {
BinaryTreeNode current;
BinaryTreeNode trailCurrent = null;
BinaryTreeNode newNode;
newNode = new BinaryTreeNode();
newNode.info = insertItem.getCopy();
newNode.llink = null;
newNode.rlink = null;
if (root == null) {
root = newNode;
} else {
current = root;
while (current != null) {
trailCurrent = current;
if (current.info.equals(insertItem)) {
System.out.println("The insert item is already in" + "the list -- duplicates are" + "not allowed.");
return;
} else if (current.info.compareTo(insertItem) > 0) {
current = current.llink;
} else {
current = current.rlink;
}
}
if (trailCurrent.info.compareTo(insertItem) > 0) {
trailCurrent.llink = newNode;
} else {
trailCurrent.rlink = newNode;
}
}
}