java - 如何检查 BST 中的节点是否不可访问

Question

class Node {

    int val;
    Node left;
    Node right;

    Node(int val){
        this.val = val;
        left = null;
        right = null;
    }

    Node(int val, Node left, Node right ){
        this.val = val;
        this.left = left;
        this.right = right;
    }

}



class BsTree {

    Node root;

    bstree(){
        root=null;
    }

    bstree(Node n){
        root=n;
    }

    public void insertpath( int val, String path){
        root=insertpath(val, path ,root);
    }

    private Node insertpath(int val, String path, Node n){
        if(n==null)
            n=new Node(val, null, null);
        else     
            if(path.charAt(0)=='X')
                n=new Node(val, null, null);
            else 
            if(path.charAt(0) == 'L'){
                if(path.length()!=0){
                path.substring(1);
                n.left=insertpath(val, path, n.left);
                }
            }
            else
                if(path.charAt(0)== 'R'){
                    if(path.length()!=0){
                        path.substring(1);
                        n.right=insertpath(val, path, n.right);
                    }
                }
        return n;
    }
}

我想编写一个递归函数来告诉我某个节点是否不可访问。输入由用户给出，用户写入要添加到树中的 int 值，并写入应该在二叉搜索树中添加这些节点的路径。例如:

1. X - 第一将是根
2. L - 第二个将添加到左侧节点
3. RR - 数字三将添加到右边，右边

添加 3 的路径 RR 无效，因为在他之前没有任何节点 R。如果发生这种情况，我想打印一条消息，说明这是无效的。我该怎么做？

Answer 1

您可以使用递归方法和Exception 处理机制来检测路径是否不存在。

public void insertpath(int val, String path) throws Exception {
    if(path == null || path.equals("")) {
        throw new Exception("Path is not effective or an empty string.");
    }
    Node node = new Node(val,null,null);
    if(path.equals("X")) {
        if(this.root != null) {
            throw new Exception("BSTree is not correct.");
        } else {
            this.root = n;
        }
    } else {
        root=path(root,path,0,node);
    }
}

private void insertpath (Node current, String path, int index, Node node) throws Exception {
    if(current == null) {
        throw new Exception("Illegal path.");
    }
    char ci = path.charAt(index);
    index++;
    if(index < path.length()) {
        //we're not at the end of the path yet
        switch(ci) {
            case 'L' :
                insertpath(current.left,path,index,node);
                break;
            case 'R' :
                insertpath(current.right,path,index,node);
                break;
            default :
                throw new Exception("Invalid path character '"+ci+"'.");
                break;
        }
    } else {
        switch(ci) {
            case 'L' :
                if(this.left != null) {
                    throw new Exception("BSTree is not correct.");
                } else {
                    current.left = node;
                }
                break;
            case 'R' :
                if(this.right != null) {
                    throw new Exception("BSTree is not correct.");
                } else {
                    current.right = node;
                }
                break;
            default :
                throw new Exception("Invalid path character '"+ci+"'.");
                break;
        }
    }
}

它可以抛出带有多条消息的多个Exception:

• “BSTree is not correct.”如果你想在一个已经使用的路径上插入一个节点；
• “无效的路径字符 'a'。”(或不同于 a 的内容)如果您的路径包含没有语义意义的奇怪字符；
• "Illegal path." 如果路径不能使用，比如你的RR 例子；和
• "Path is not effective or an empty string." 如果路径无效 (null) 或为空 ("") .

显然，您可以发明其他Exception，以便程序可以更轻松地区分不同的问题。