Java BinarySearchTrees：输入密钥返回值（查找）

Question

我想使用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; 
     } 
    } 

第二个问题是我真的不知道如何实现“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)); 
    } 


} 

Answer 1

我不知道你的getNext（）方法应该做什么，但我猜它应该得到下一个最大的元素。如果是这样的话，那么看起来你所做的是正确的。

对于第二个问题，不，递归不起作用。你可能（可能）想要使用一个循环，直到当前节点有你正在寻找的键（并且像你正在做的那样返回值），或者直到没有剩下左或右节点来检查（ curr节点为空）。此外，基于方法头，它看起来像你会想要抛出一个异常，如果没有找到密钥，而不是返回null。看起来你有合适的条件，你只需要在这些条件成立时做一些小的改变。