java - 我将如何搜索二叉树以找到目标？

Question

我已经研究这段代码有一段时间了，但没有运气。我知道我需要通过此方法传递我的树，但我不确定如何做到这一点。

我认为我的算法是正确的，但无论我输入什么，它总是告诉我“null”。任何反馈都可以提供帮助，我认为它一直返回 null，因为我不知道如何通过该方法传递树.

下面，我的 find2 方法应该使用我的 add2 方法创建的树来查找所选节点。这也包括我的主要方法。

代码如下:

public boolean add2(E item) {
    root = add2(root, item);
    return addReturn;
}

private Node<E> add2(Node<E> localRoot, E item){
    if(localRoot == null) {
        //Adding item if tree is empty...
        addReturn = true;
        return new Node<>(item);
    } else if (item.compareTo(localRoot.data) == 0) {
        //Returning item if equal to root...
        addReturn = false;
        return localRoot;
    } else if (item.compareTo(localRoot.data) < 0) {
        //Adding item to right side of tree if less than the root...
        localRoot.right = add(localRoot.right, item);
        return localRoot;
    } else {
        //Adding item to left side of tree if grater than the root...
        localRoot.left = add(localRoot.left, item);
        return localRoot;
    }
}

//wrapper method
public E find2(E target) {
    return find2(root, target);
}

//recursive method
private E find2(Node<E> localRoot, E target) {
    if(localRoot == null) {
        return null;
    }
    int compResult2 = target.compareTo(localRoot.data);

    if(compResult2 == 0) {
        return localRoot.data;
    } else if (compResult2 < 0) {
        return find2(localRoot.right, target);
    } else {
        return find2(localRoot.left, target);
    }
}

public class BinarySearchTreeTest {

public static void main(String[] args) {

    //Object creation
    BinarySearchTree<Integer> tree = new BinarySearchTree<>();

    //Tree building...
    tree.add2(50);
    tree.add2(70);
    tree.add2(80);
    tree.add2(60);
    tree.add2(30);
    tree.add2(40);
    tree.add2(20);

    //Output tree
    System.out.println("\nThe built binary search tree:");
    System.out.println("\n" + tree.toString());

    System.out.println("\nSearch the node with data 60: " + tree.find2(60));
    System.out.println("Search the node with data 65: " + tree.find2(65));
    System.out.println("Search the node with data 20: " + tree.find2(20));
    System.out.println("Search the node with data 25: " + tree.find2(25));

}

}

Answer 1

我尝试将本地的 add2 方法调用更改为 add2 而不是 add

        static class BinarySearchTree<Item extends Comparable> {

        Node root;
        boolean addReturn;

        class Node {
            Item data;
            Node left;
            Node right;

            public Node(Item e) {
                data = e;
            }
        }

        public boolean add2(Item item) {
            root = add2(root, item);
            return addReturn;
        }

        private Node add2(Node localRoot, Item item) {
            if (localRoot == null) {
                // Adding item if tree is empty...
                addReturn = true;
                return new Node(item);
            } else if (item.compareTo(localRoot.data) == 0) {
                // Returning item if equal to root...
                addReturn = false;
                return localRoot;
            } else if (item.compareTo(localRoot.data) < 0) {
                // Adding item to right side of tree if less than the root...
                localRoot.right = add2(localRoot.right, item);
                return localRoot;
            } else {
                // Adding item to left side of tree if grater than the root...
                localRoot.left = add2(localRoot.left, item);
                return localRoot;
            }
        }

        // wrapper method
        public Item find2(Item target) {
            return find2(root, target);
        }

        // recursive method
        private Item find2(Node localRoot, Item target) {
            if (localRoot == null) {
                return null;
            }
            int compResult2 = target.compareTo(localRoot.data);
            if (compResult2 == 0) {
                return localRoot.data;
            } else if (compResult2 < 0) {
                return find2(localRoot.right, target);
            } else {
                return find2(localRoot.left, target);
            }
        }
    }

    public static void main(String[] args) {

        // Object creation
        BinarySearchTree<Integer> tree = new BinarySearchTree<>();

        // Tree building...
        tree.add2(50);
        tree.add2(70);
        tree.add2(80);
        tree.add2(60);
        tree.add2(30);
        tree.add2(40);
        tree.add2(20);

        // Output tree
        System.out.println("\nThe built binary search tree:");
        System.out.println("\n" + tree.toString());

        System.out.println("\nSearch the node with data 60: " + tree.find2(60));
        System.out.println("Search the node with data 65: " + tree.find2(65));
        System.out.println("Search the node with data 20: " + tree.find2(20));
        System.out.println("Search the node with data 25: " + tree.find2(25));

    }

，并给出输出:

Search the node with data 60: 60
Search the node with data 65: null
Search the node with data 20: 20
Search the node with data 25: null