java - 通用二叉搜索树

Question

我有以下类，我想让用户选择是否要创建带有整数的 BST 或带有字符串的 BST。当用户选择 5 时如何从整数创建 BST，或者当用户按 6 时如何从字符串创建 BST？另外，如果有人发现我的泛型有问题，请告诉我!

非常感谢

    public class BSTNode <T extends Comparable<T>>
{ 
       T value; 
        BSTNode<T> left; 
        BSTNode<T> right; 

      public BSTNode(T value, BSTNode<T> l,BSTNode<T> r) 
      { 
            this.value = value; 
            left = l; 
            right = r; 
      } 

      public BSTNode(T value) 
      { 
            this(value,null,null);
      } 

      public T getValue() 
      {
          return value;
      }

      public void setValue(T value) 
      {
          this.value = value;
      }

      public BSTNode<T> getLeftChild() 
      {
          return left;
      }

      public BSTNode<T> getRightChild() 
      {
          return right;
      }

      public void setLeftChild(BSTNode<T> node) 
      {
          left = node;
      }

      public void setRightChild(BSTNode<T> node) 
      {
          right = node;
      }

      public boolean search(T value) 
      { 
            if (value.equals(this.value)) 
                  return true; 
            else if (value.compareTo(this.value) < 0) 
            { 
                  if (left == null) 
                        return false; 
                  else 
                        return left.search(value); 
            } else if (value.compareTo(this.value) > 0) 
            { 
                  if (right == null) 
                        return false; 
                  else 
                        return right.search(value); 
            } 
            return false; 
      }

      public boolean add(T value) 
      { 
            if (value.compareTo(this.value)==0) 
                  return false; 
            else if (value.compareTo(this.value) < 0) 
            { 
                  if (left == null) 
                  { 
                        left = new BSTNode<T>(value); 
                        return true; 
                  } else 
                        return left.add(value); 
            } 
            else if (value.compareTo(this.value) > 0) 
            { 
                  if (right == null) 
                  { 
                        right = new  BSTNode<T>(value); 
                        return true; 
                  } 
                  else 
                        return right.add(value); 
            } 
            return false; 
      } 



     public boolean remove(T value2, BSTNode<T> parent) 
      { 
        if (value2.compareTo(this.value)<0) 
        { 
           if (left != null) 
              return left.remove(value2, this); 
           else 
              return false; 
       }
        else if (value2.compareTo(this.value)>0) 
        { 
           if (right != null) 
              return right.remove(value2, this); 
           else 
              return false; 
        }
       else 
       { 
           if (left != null && right != null) 
           { 
               this.value = right.minValue(); 
               right.remove(this.value, this); 
           } 
           else if (parent.left == this) 
           { 
               parent.left = (left != null) ? left : right; 
           } 
           else if (parent.right == this) 
           { 
               parent.right = (left != null) ? left : right; 
           } 
           return true; 
       }
    } 

    public T minValue() 
    { 
         if (left == null) 
             return value; 
         else 
             return left.minValue(); 
    }

 }

     public class BinarySearchTree <T extends Comparable<T>>
{ 
      private BSTNode<T> root; 

      public BinarySearchTree(T value) 
      { 
          root = new BSTNode<T>(value);
      } 


      public BSTNode getRoot() 
      {
          return root;
      }

      public boolean search(T value) 
      { 
          if (root.equals(null)) 
              return false; 
        else 
              return root.search(value); 
  }

      public boolean add(T value) 
      { 
          if (root == null) { 
              root = new BSTNode(value); 
              return true; 
        } else 
              return root.add(value); 
      } 

      public boolean remove(T value) { 
            if (root == null) 
               return false; 
            else { 
               if (root.getValue() == value) { 
                   BSTNode auxRoot = new BSTNode(null); 
                   auxRoot.setLeftChild(root); 
                   boolean result = root.remove(value, auxRoot); 
                   root = auxRoot.getLeftChild(); 
                   return result; 
               } else { 
                   return root.remove(value, null); 
               } 
             } 
          }

     public static void displayInorder(BSTNode T)
      {
          if (T!=null)
          {
              if (T.getLeftChild()!=null)
              {               
                  displayInorder(T.getLeftChild());               
              }
              System.out.print(T.getValue() + "  ");
              if(T.getRightChild()!=null)
              {
                  displayInorder(T.getRightChild());
              }
          }

      }
  }

import java.util.Scanner;

public class main {
    public  static void main(String[] args) {
        BinarySearchTree b = new BinarySearchTree(null);
        boolean flag = true;
        while (flag) {
        Scanner scan = new Scanner(System.in);
          System.out.println("Select 1 to add values in to BST\n"
                + "Select 2 to delete values from the BST \n"
                + "Select 3 to search for a value\n"
                + "Select 4 to display te values held in the BST\n"
                + "Select 5 to create a BST of strings\n"
                + "Select 6 to create a BST of integers\n"
                + "Select 7 to exit" );
          int opt = scan.nextInt();

    switch (opt) {
    case 1: System.out.println("Insert the value of your choice: ");
            String str = scan.next();
            b.add(str);
            break;
    case 2: System.out.println("Insert the value of your choice: ");
              str = scan.next();
              b.remove( str);
            break;
    case 3:
        System.out.println("Insert the value of your choice: ");
          str = scan.next();
          b.search(str);
        break;
    case 4:
        BinarySearchTree.displayInorder(b.getRoot());
        break;
    case 5:

    case 7:
        flag=false;
        break;
    }
  }
 }
}

Answer 1

为了在代码中充分利用泛型，这是我的建议:

我将添加一个方法来将字符串(用户输入)处理为树类中的适当类型:

...
import java.util.function.Function;
...

public class BinarySearchTree <T extends Comparable<T>>
{ 
      private BSTNode<T> root; 
      private Function<String,T> valueDecoder

      public BinarySearchTree(final Function<String,T> valueDecoder) 
      { 
          this.valueDecoder = valueDecoder; 
          root = new BSTNode<T>(null);
      } 

      ... 
      public boolean decodeAndAdd(final String encodedValue) {
          return add(valueDecoder.apply(encodedValue));
      }

      public boolean decodeAndRemove(final String encodedValue) {
          return remove(valueDecoder.apply(encodedValue));
      }
}

```

然后您将离开 b变量未定义/空，直到您实际上知道用户提供的选择的树类型。因为它可能包含 String或Integer这里你只能使用?作为类型参数，也许 ? extends Comparable<?>因为这是约束的一部分... ?在这种情况下没问题:

BinarySearchTree<?> b = null ;

现在，当用户请求String时或Integer树，您需要提供适当的 lambda 将扫描的字符串传输到实际的元素值:

case 5:
   b = new BinarySearchTree<>(scanStr -> scanStr);
   break;
case 6:
   b = new BinarySearchTree<>(scanStr -> Integer.parseInt(scanStr));
   break;

现在添加和删除都很简单:

case 1:
     b.decodeAndAdd(scan.next());
     break;

case 2:
     b.decodeAndRemove(scan.next());
     break;

如果用户在树是 Integer 时提供无效的整数字符串值树它会导致 NumberFormatException然后程序就会停止。也许您宁愿显示错误消息并允许用户执行其他操作。为此:

case 6:
    b = new BinarySearchTree<>(scanStr -> {
       try {
          return Integer.parseInt(scanStr);
       } catch (NumberFormatException ex) {
          throw new IllegalArgumentException("you must provide a valid integer value: '" + scanStr + "'");
       }
    });
    break;
...

case 1:
     try {
       b.decodeAndAdd(scan.next());
     } catch (final IllegalArgumentException ex) {
       System.err.println("ERROR: " + ex.getMessage());
     }
     break;

case 2:
     try {
       b.decodeAndRemove(scan.next());
     } catch (final IllegalArgumentException ex) {
       System.err.println("ERROR: " + ex.getMessage());
     }
     break;

如果您想让事情变得更加模块化，那么将decodeAndAdd和decodeAndRemove添加到BinarySearchTree类中可能并不理想，因为BST可能会在问题中描述的用户命令行上下文之外使用。

在这种情况下，您可以定义一个类似于类的通用“结构”，其中包含一个引用，该引用包含对 BST 的引用和解码 lambda，并且使用类型参数将它们的元素类型绑定(bind)为相同。您还可以在另一个用户界面专用 BST 中扩展 BST 类，以添加此功能:

class CommandLineBST<T> {

  public final BST<T> tree;
  public final Function<String, T> valueDecoder;

  public CommandLineBST(final BST<T> tree, final Function<String, T> decoder) {
      this.tree = tree;
      this.valueDecoder = decoder;
  }

  public boolean add(final String scanStr) { 
     return tree.add(valueDecoder.apply(scanStr)); 
  }

  public boolean remove(final String scanStr) {
     return tree.remove(valueDecoder.apply(scanStr));
  }

}

或

class CommandLineBST<T> extends BST<T> {
    private Function<String, T> valueDecoder;

    public CommandLineBST(final Function<String, T> valueDecoder) {
       super(null);
       this.valueDecoder = valueDecoder;
    }

    public boolean decodeAndAdd(final String scanStr) { ... }
    public boolean decodeAndRemove(final String scanStr) { ... }
}