Я пытаюсь реализовать интерфейс базы данных, используя BST.У меня есть внутренний класс BTSEntry, который представляет узел с переменными ключ, значение и левый / правый узлы.Каждый левый узел меньше (в алфавитном порядке), чем его родитель, в то время как каждый правый узел больше, чем его родитель.
Первая проблема заключается в том, что я не знаю, что такое "nextNode ()" вВход во внутренний класс должен быть.Это просто правильный узел?Или это то, что я сделал ниже?
private BinarySearchTreeEntry getLeftMost() {
BinarySearchTreeEntry n = this;
while (n.left != null) {
n = n.left;
}
return n;
}
public BinarySearchTreeEntry getNext() {
if (right != null) {
return right.getLeftMost();
} else {
BinarySearchTreeEntry n = this;
while (n.parent != null && n == n.parent.right) {
n = n.parent;
}
return n.parent;
}
}
Вторая проблема заключается в том, что я действительно не знаю, как реализовать метод Int value get (Str key).РЕДАКТИРОВАТЬ: я пытался сделать метод get (ключ).Это правильно?Будет ли рекурсия работать для этого?
public Integer get(String key) throws NoSuchElementException {
BinarySearchTreeEntry curr = root;
if(curr == null){
return null;
} else if(curr.getKey().equals(key)){
return curr.getValue();
} else if(key.compareTo(curr.getKey()) < 0){
curr = curr.getLeft();
get(key);
} else{
curr = curr.getRight();
get(key);
}
return null;
}
Вот что я сделал до сих пор.Любая помощь будет принята с благодарностью!:)
package database;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;
public class BinarySearchTree<K, V> implements Dictionary<String, Integer> {
private class BinarySearchTreeEntry
implements DictionaryEntry<String, Integer>{
private String key;
private Integer value;
private BinarySearchTreeEntry left;
private BinarySearchTreeEntry right;
private BinarySearchTreeEntry parent;
BinarySearchTreeEntry(String key, Integer value,
BinarySearchTreeEntry left,
BinarySearchTreeEntry right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
if (left != null) left.parent = this;
if (right != null) right.parent = this;
}
private BinarySearchTreeEntry getLeftMost() {
BinarySearchTreeEntry n = this;
while (n.left != null) {
n = n.left;
}
return n;
}
private BinarySearchTreeEntry getRightMost() {
BinarySearchTreeEntry n = this;
while (n.right != null) {
n = n.right;
}
return n;
}
public BinarySearchTreeEntry getNext() {
if (right != null) {
return right.getLeftMost();
} else {
BinarySearchTreeEntry n = this;
while (n.parent != null && n == n.parent.right) {
n = n.parent;
}
return n.parent;
}
}
public String getKey() {
return key;
}
public Integer getValue() {
return value;
}
public BinarySearchTreeEntry getLeft() {
return left;
}
public BinarySearchTreeEntry getRight() {
return right;
}
}
private class ListIterator
implements Iterator<DictionaryEntry<String, Integer>> {
private BinarySearchTreeEntry current;
Stack<BinarySearchTreeEntry> workList;
public ListIterator(BinarySearchTreeEntry entry){
current = entry;
}
public boolean hasNext() {
return current != null;
}
public BinarySearchTreeEntry next() {
BinarySearchTreeEntry result = null;
current = root;
while(current!=null){
workList.push(current);
current = current.getLeft();
}
if(!workList.isEmpty()){
result = (BinarySearchTreeEntry) workList.pop();
current = result.getRight();
}
return result;
}
public void remove() {
}
}
private BinarySearchTreeEntry root;
private int items;
public BinarySearchTree(){
root = null;
items = 0;
}
public int size() {
ListIterator iter = iterator();
while(iter.hasNext()){
items += 1;
}
return items;
}
public boolean isEmpty() {
return size() == 0;
}
public Integer get(String key) throws NoSuchElementException {
BinarySearchTreeEntry curr = root;
if(curr == null){
return null;
} else if(curr.getKey().equals(key)){
return curr.getValue();
} else if(key.compareTo(curr.getKey()) < 0){
//Now what?
}
return null;
}
public void put(String key, Integer value) {
}
public void clear() {
ListIterator iter = iterator();
BinarySearchTreeEntry curr;
curr = root;
while(iter.hasNext()){
remove(curr.getKey());
curr = iter.next();
}
remove(curr.getKey());
}
public void remove(String key) throws NoSuchElementException {
}
public ListIterator iterator() {
return (new ListIterator(root));
}
}