二叉树不插入或搜索节点

Question

我是 Java 和一般编程的新手。该代码主要有效。它可以做所有事情除了当我输入以下内容时：

序列：d, e, f, a, b, c, g, h, i, j.
搜索：b 或 c

我似乎找不到代码的任何问题，但已将其缩小到 insertNode module/class，似乎当用户在 [= 之后键入 a, b, c 16=]只有节点a在左侧注册。

import java.util.Arrays;
import java.util.Scanner;
import java.lang.reflect.Method;

public class BinarySearchTreeTestWhosebug {

    class Node {
        String stringData;
        Node leftChild;
        Node rightChild;
        Node(String stringData) {
            this.stringData = stringData;
            leftChild = rightChild = null;
        }
    }

    //root node for the binary tree
    Node root;

    //Constructor method
    public BinarySearchTreeTestWhosebug() {
        root = null;
    }

    //Insert method for new values in the tree
    public void insert(String key) {
        root = insertNode(root, key);
    }

    //Insert recursive call for inserting from the root, in the right place
    public Node insertNode(Node node, String key) {

        if (node == null) {
            node = new Node(key);

            return node;
        }

        if (key.compareTo(node.stringData) < 0) {
            node.leftChild = insertNode(node.leftChild, key);

        } else if (key.compareTo(root.stringData) > 0) {
            node.rightChild = insertNode(node.rightChild, key);

        }
        return node;
    }



    //Find method asking for the node to find
    public Node find(String key) { //takes user input and turns it into a node
        Node node = findNode(root, key);
        System.out.println("print key to find: " + key);
        return node;
    }

    //Find recursive method using the root node.
    public Node findNode(Node node, String key) {

        if (key.compareTo(node.stringData) == 0) {

            return node;
        }




        //check up on findNodeMethod
        if (key.compareTo(node.stringData) <= 0) {

            if (node.leftChild == null) {
                return null;
            } else {
                return findNode(node.leftChild, key);
            }

        } else if (key.compareTo(node.stringData) > 0) {


            if (node.rightChild == null) {
                return null;
            } else {
                System.out.println("went right"); //toDelete
                return findNode(node.rightChild, key);
            }
        }
        return null;
    }



    public static void main(String[] args) {
        BinarySearchTreeTestWhosebug binaryTree = new BinarySearchTreeTestWhosebug();
        Scanner scanner = new Scanner(System.in);
        for (int i = 1; i <= 10; i++) {

            System.out.print("Enter string " + i + " for the tree: ");
            binaryTree.insert(scanner.nextLine());
        }


        System.out.print("Enter the value to be searched: ");
        String key = scanner.nextLine(); //correct, verified using -  System.out.println("key to be searched: "+ key);

        Node node = binaryTree.find(key);

        if (node == null) {
            System.out.println("The string does not exist");

        } else {
            System.out.println("Node " + node.stringData + " was found");
        }
    }

}

Answer 1

问题出在 insertNode() 里面。而不是与 root 进行比较：

else if (key.compareTo(root.stringData) > 0) {
    node.rightChild = insertNode(node.rightChild, key);
}

你应该与 node 进行比较：

else if (key.compareTo(node.stringData) > 0) {
    node.rightChild = insertNode(node.rightChild, key);
}

二叉树不插入或搜索节点

Binary tree not inserting or searching node

java

sorting

binary-tree

binary-search-tree