BSTree.java

import java.io.IOException;
import java.io.PrintWriter;
import java.util.stream.BaseStream;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;
class Node{
    private String key;
    private String value;
    private Node left;
    private Node right;

    public Node(String key,String value){
        this.key = key;
        this.value = value;
        left = right = null;
    }

    public Node left() {
        return this.left;
    }

    public Node right() {
        return this.right;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public String key() {
        return this.key;
    }

    public void setKey(String key) {
        this.key = key;
    }

    public String value() {
        return this.value;
    }

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

class Result{
    String value = null;
    String originalValue = null;
    public Result(String value){
        this.value = value;
    }
}


public class BSTree implements BST<String,String> {


    private Node root;
    private String key;
    private String value;
    private BSTree left;
    private BSTree right;

    public BSTree(String key, String value) {
        this.key = key;
        this.value = value;
        left = null;
        right = null;
    }

    public BSTree() {
        root = null;
    }

    public BSTree(Node root) {
        this.root = root;
    }


    public BSTree left() {
        return this.left;
    }

    public BSTree right() {
        return this.right;
    }

    private void setLeft(BSTree left) {
        this.left = left;
    }

    private void setRight(BSTree right) {
        this.right = right;
    }

    public String key() {
        return this.key;
    }

    private void setKey(String key) {
        this.key = key;
    }

    public String value() {
        return this.value;
    }

    private void setValue(String value) {
        this.value = value;
    }


    public Node root(){
        return this.root;
    }
    @Override
    public void insert(String key, String value) {
        this.root = insert(root,key,value);  //将结点插入树
    }

    private Node insert(Node node,String key,String value){
        if(key != null && value != null) {
            if (node == null) {    //空树
                node = new Node(key, value);
                return node;
            }

            if(key.compareTo(node.key())<0){
                node.setLeft(insert(node.left(),key,value));
            }
            else if(key.compareTo(node.key())>0){
                node.setRight(insert(node.right(),key,value));  //插入右子树
            }
            else{
                node.setValue(value);
            }
            return node;
        }
        return null;
    }



    @Override
    public String remove(String key) {
        if (key == null) {
            throw new IllegalArgumentException("Key is null");
        }
        Result result = new Result(null);
        root = remove(root, key, result);
        if (result.value == null) {
            return (String) ("remove failure --- " + key);
        } else {
            return (String) ("remove success --- " + key + " " + result.originalValue);
        }
    }

    private Node remove(Node node, String key, Result result){
        if(node == null || key == null){
            return null;
        }

        if(key.compareTo(node.key())<0){
            node.setLeft(remove(node.left(),key,result));
            return node;
        }
        else if(key.compareTo(node.key())>0){
            node.setRight(remove(node.right(),key,result));
            return node;
        }else{        //结点关键码匹配

          if(result.value == null){
              result.value = node.value();
              result.originalValue = node.value();  //存储结点值
          }

          if(node.left() == null){
              return node.right();
          }
          else if(node.right() == null){
              return node.left();
          }
          else{
              Node min = findMin(node.right());
              node.setKey(min.key());
              node.setValue(min.value());
              node.setRight(remove(node.right(),min.key(),result));
          }
        }
        return node;
    }

    private Node findMin(Node node){
        while(node.left() != null){
            node = node.left();
        }
        return node;
    }



    @Override
    public String search(String key) {
        return search(root,key);
    }

    private String search(Node node,String key){
        if(key == null){
            return null;
        }

        if(node == null){
            return (String)("search failure --- "+key);
        }

        if(key.compareTo(node.key())<0){
            return search(node.left(),key);
        }
        else if(key.compareTo(node.key())>0){
            return search(node.right(),key);
        }
        else{
            return (String)("search success --- "+key+" "+node.value());
        }
    }

    public String find(String key){
        return find(key,root);
    }

    private String find(String key,Node node){
        if(key == null){
            return null;
        }
        if(node == null){
            return (String)("FAILURE");
        }

        if(key.compareTo(node.key())<0){
            return find(key,node.left());
        }
        else if(key.compareTo(node.key())>0){
            return find(key,node.right());
        }
        else{
            return node.value();
        }
    }

    @Override
    public boolean update(String key, String value) {
            return update(root,key,value) != null;
    }

    private Node update(Node node,String key,String value){
        if(key == null || value == null || node == null){
            return null;
        }


        if(key.compareTo(node.key())<0){
            return update(node.left(),key,value);
        }
        else if(key.compareTo(node.key())>0){
            return update(node.right(),key,value);
        }
        else{
            node.setValue(value);
            return node;
        }
    }

    @Override
    public void clear() {
        root = null;
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }

    @Override
    public void showStructure(PrintWriter pw) throws IOException {

        pw.println("-----------------------");
            pw.printf("There are %d nodes in this BST.", inorder(this));
            pw.println();
            pw.printf("The height of this BST is %d", height(this));
            pw.println();
        pw.println("-----------------------");
    }

    @Override
    public void printInorder(PrintWriter pw) throws IOException {
        printInorderHelper(root,pw);
    }

    private void printInorderHelper(Node root,PrintWriter pw) throws IOException{
        if(root != null){
            printInorderHelper(root.left(),pw);
            pw.println("["+root.key()+"---<"+root.value()+">]");
            printInorderHelper(root.right(),pw);
        }
    }


    public static int inorder(BSTree root) {
        if (root == null) {
            return 0;
        }

        return inorder(root.left()) + inorder(root.right()) + 1;
    }

    public static int height(BSTree root) {
        if (root == null) {
            return 0;
        }

        return height(root.left()) > height(root.right()) ? height(root.left()) + 1 : height(root.right()) + 1;
    }

    public static void processCommand(BSTree root,String command,PrintWriter pw,int value){
        String newValue =Integer.toString(value);
        String key = null;
        if(command.length()>1){
            String[] parts = command.substring(0,command.length()).split("[ ,?,\\,\",!,--,*,&,(,),:,;]");
            for(int i = 0;i< parts.length;i++){
                if(parts[i].length()>1 && parts[i].charAt(0) == '\'' && parts[i].charAt(parts[i].length()-1)=='\''){
                    parts[i] = parts[i].substring(1,parts[i].length()-1);
                }else if(parts[i].length()>0 && parts[i].charAt(0) == '\''){
                    parts[i] = parts[i].substring(1,parts[i].length());
                }
                else if(parts[i].length()>0 && parts[i].charAt(parts[i].length()-1) == '\''){
                    parts[i] = parts[i].substring(0,parts[i].length()-1);
                }

                if(parts[i].length()>0 && parts[i].charAt(parts[i].length()-1) == '.'){
                    parts[i] = parts[i].substring(0,parts[i].length()-1);
                }
            }
            if(parts.length>0) {
                for(int i = 0;i< parts.length;i++){
                    if(!parts[i].equals("")){
                        key = parts[i];
                        if(root.find(key) == "FAILURE"){
                            root.insert(key,newValue);
                        }
                        else{
                            String original = root.find(key);
                            root.update(key,original+" "+newValue);
                        }
                    }
                }

            }
        }
        if(value == 33404){
            try{
                root.printInorder(pw);
            }catch (IOException e){
                e.printStackTrace();
            }
        }
    }

    public static void processCommand(BSTree root,String command,PrintWriter pw){
        char operation = command.charAt(0);
        String key = null;
        String value = null;
        if(command.length()>1){
            String[] parts = command.substring(2,command.length()-1).split(",");
            key = parts[0].trim();
            if(parts.length>=2){
                value = parts[1].substring(2,parts[1].length()-2);
            }
        }
        switch(operation){
            case '+':
                root.insert(key,value);
                break;

            case '-':
                pw.println(root.remove(key));
                break;

            case'?':
                pw.println(root.search(key));
                break;

            case'=':
                boolean updateResult = root.update(key,value);
                if(updateResult){
                    pw.println("update success ---"+key+" "+value);
                }
                else{
                    pw.println("update failure ---"+key);
                }
                break;
            case '#':
                try{
                    root.showStructure(pw);
                }
                catch(IOException e){
                  throw new RuntimeException(e);
            }
            break;
            default:
                System.out.println("Invalid Command");

        }
    }

    public static void main(String[] args){
        BSTree tree = new BSTree();

     /* try{
           File file = new File("D:/temp/homework3_testcases.txt");
           Scanner scanner = new Scanner(file);
           File outputFile = new File("output.txt");
           PrintWriter printWriter = new PrintWriter(outputFile);
           while (scanner.hasNextLine()){
               String input = scanner.nextLine();
               processCommand(tree,input,printWriter);
           }
           scanner.close();
           printWriter.close();
       }catch (FileNotFoundException e){
           e.printStackTrace();;
       }*/
        try{
            File file = new File("D:/temp/homework3_article.txt");
            Scanner scanner = new Scanner(file);
            File outputFile = new File("index_result.txt");
            PrintWriter printWriter = new PrintWriter(outputFile);
            int Line = 0;
            while (scanner.hasNextLine()){
                Line++;
                String input = scanner.nextLine();
                processCommand(tree,input,printWriter,Line);
            }


            scanner.close();
            printWriter.close();

        }catch (FileNotFoundException e){
            e.printStackTrace();
        }
    }
}