BST を使用してデータベース インターフェイスを実装しようとしています。変数キー、値、および左右のノードを持つノードを表す内部クラス BTSEntry があります。左の各ノードは親より (アルファベット順で) 小さく、右の各ノードは親より大きくなっています。
最初の問題は、Entry 内部クラスの "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;
}
}
2 つ目の問題は、"Int value get(Str key)" メソッドの実装方法がよくわからないことです。編集: get(key) メソッドを実行しようとしました。それが正しいか？これで再帰は機能しますか？
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));
}
}