在二叉树中插入字符串

Question

我正在尝试创建一个采用字符串的二叉树，但它使用“-”和“+”向左或向右移动，如果符号是 + 向左插入，如果是 - 则向右插入。这是我正在尝试做的事情的直观表示。

insert 方法现在应该接受单词和一个符号，并基于向右或向左插入

这是我的代码，但出现空指针错误。显然，我没有插入正确的顺序


public class BinaryTree {
    
    private static Node root = null;
    private static Node sign = null;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        BinaryTree bt = new BinaryTree();
        bt.insert("to", "-");
        bt.insert("the", "+");
        bt.preorder();

    }
    
    private class Node {
        String data;
        String sign;
        Node left;
        Node right;
        
    
    public Node(String w) {
        data = w;
        left = right = null;
        
    }
    
//  public Node(String w, String s) {
//      data = w;
//      sign = s;
//      left = right = null;
//      
//  }
    
    
    } // -----------------end of Node
    
    private void insert(String val, String sign) {
        root = insert(root, val, sign);
        
    }
    
    Node insert(Node r, String data, String passSign) {
        if (r == null) {
            return new Node(data);
        }
        
        if(r.sign.equals(passSign)) {
            r.right = insert(r.right, data, passSign);
        } 
        else if (r.sign.equals(passSign)){
            r.left = insert(r.left, data, passSign);
        }
        return r;
    }
    
    public void preorder() {
        preorder(root);
    }
    
    public void preorder(Node p) {
        if (p != null) {
            System.out.println(p.data);
            preorder(p.left);
            preorder(p.right);
        }
    }

}

Answer 1

主要问题是：

BinaryTree 或 Node 实例应该有一个 sign 成员。符号只在插入过程中起作用，插入节点后就没有意义了
r.sign.equals(passSign) 因此也不是要检查的正确条件。根据您的描述，您应该只检查标志是否为“-”然后向右走，否则向左走（“+”）。没有state节点影响这个决定。所以 passSign.charAt(0) == '-' 相反。
进行递归调用时，您不应再次传递相同的符号：它已被处理。相反，在消费后传递任何 follow 的标志。您可以为此目的使用 substring。
图像显示了一个没有值的根节点。然而，您创建一个根本没有节点的树实例是正确的。因此，您的 insert 方法应该处理 root 为空但符号参数不是空字符串的情况。在那种情况下，应该创建一个 root 节点，但它不应该包含目标数据，至于我们仍然应该在树中更深入。这个原则可以适用于任何节点，而不仅仅是根。所以预见到创建这样的“占位符”节点并给它们一些默认值（如“（null）”）。

没问题，但我发现按 inorder 顺序打印并缩进更深的节点更有用。这样您就可以了解树的结构。

这是更正后的代码：

public class BinaryTree {
    
    private static Node root = null;
    // No sign member needed;

    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.insert("to", "-");
        bt.insert("the", "+");
        bt.insert("buy", "-+");
        bt.insert("imperial", "+-");
        bt.insert("afflication", "++");
        bt.inorder();
    }
    
    private class Node {
        String data;
        // No sign member needed;
        Node left;
        Node right;
            
        public Node(String w) {
            data = w;
            left = right = null;    
        }
    }
    
    private void insert(String val, String sign) {
        root = insert(root, val, sign);
    }
    
    Node insert(Node r, String data, String passSign) {
        // Check whether there is a sign
        if (passSign.length() == 0) {
            return new Node(data);
        }
        // If needed, create a placeholder node so to be able to descend further
        if (r == null) {
            r = new Node("(null)");
        }
        
        if (passSign.charAt(0) == '-') {
            // Extract the rest of the signs
            r.right = insert(r.right, data, passSign.substring(1, passSign.length()));
        } 
        else {
            r.left = insert(r.left, data, passSign.substring(1, passSign.length()));
        }
        return r;
    }
    
    public void inorder() {
        inorder(root, "");
    }
    
    // This method gives a bit more visual output
    public void inorder(Node p, String indent) {
        if (p != null) {
            inorder(p.left, indent + "  ");
            System.out.println(indent + p.data);
            inorder(p.right, indent + "  ");
        }
    }
}

在二叉树中插入字符串

Insert string in a Binary tree

java

binary-tree

insert