java - 具有无限循环的二叉树实现

Question

我已经解决了无限循环的问题，但现在当我尝试使用函数 find 时，它总是返回 null 值。对发生的事情有什么想法吗？另外，由于某种原因，我在删除函数中收到 NullPointerException 。请你们帮帮我好吗？

package ui;

import java.time.LocalDate;

import bp.BinaryTree;

public class Main {

    public static void main(String[] args) {
        BinaryTree myTree = new BinaryTree();
        myTree.insert(LocalDate.of(2014,12,01));
        myTree.insert(LocalDate.of(2014,12,02));
        myTree.insert(LocalDate.of(2014,12,03));
        myTree.insert(LocalDate.of(2013,12,04));
        myTree.insert(LocalDate.of(2012,12,04));
        myTree.insert(LocalDate.of(2011,12,04));
        myTree.insert(LocalDate.of(2010,12,04));
        myTree.insert(LocalDate.of(2014,12,04));
        myTree.insert(LocalDate.of(2014,12,05));
        myTree.insert(LocalDate.of(2014,12,06));
        myTree.insert(LocalDate.of(2014,12,07));
        System.out.println(myTree);

        System.out.println(myTree.getSize());
        System.out.println(myTree.showMaximumValue());
        System.out.println(myTree.showMinimumValue());
        System.out.println(myTree.find(LocalDate.of(2014,12,07)));
}


public class BinaryTree implements IBinaryTree {

    public Node root = null;
    private int sizeOfTree = 0;


    @Override
    public LocalDate showMinimumValue() {
        Node current;
        Node last=null;
        current = root;
        while (current != null) {
            last = current;
            current = current.getLeftChild();
        }
        return last.getDate();
    }

    @Override
    public LocalDate showMaximumValue() {
        Node current;
        Node last=null;
        current = root;
        while (current != null) {
            last = current;
            current = current.getRightChild();
        }
        return last.getDate();

    }

    @Override
    public boolean isEmpty() {
        if (root == null) {
            return true;
        } else
            return false;

    }


    public int getDepth(Node n) {
        int currentDepth = 0;
        int depth = 0;
        if (n != null) {
            currentDepth++;

            if (currentDepth > depth) {
                depth = currentDepth;
            }

            getDepth(n.getLeftChild());
            getDepth(n.getRightChild());

            currentDepth--;
        }
        return depth;
    }



    @Override
    public int getSize() {

        return sizeOfTree;
    }

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

    }

    @Override
    public void insert(LocalDate valueToInsert) {
        if (isEmpty()) {
            root = new Node(valueToInsert);
            sizeOfTree++;
        } else {
            Node n = root;
            Node oldParent = null;
            boolean lastDirectWasLeft = false;
            sizeOfTree++;
            while (n != null) {
                oldParent = n;
                if (valueToInsert.isBefore(n.getDate())) {
                    n = n.getLeftChild();
                    lastDirectWasLeft = true;
                } else {
                    n = n.getRightChild();
                    lastDirectWasLeft = false;
                }
            }
            if (lastDirectWasLeft) {
                oldParent.setLeftChild(new Node(valueToInsert));
            } else {
                oldParent.setRightChild(new Node(valueToInsert));
            }
        }

    }


    @Override
    public void delete(LocalDate valueToDelete) {
        Node current = root;
        Node parent = root;
        boolean isLeftChild = true;

        while (current.getDate() != valueToDelete) {
            parent = current;
            if (valueToDelete.isBefore(current.getDate())) {
                isLeftChild = true;
                current = current.getLeftChild();
            } else {
                isLeftChild= false;
                current = current.getRightChild();
            }
            if (current == null) {
                break;
            }
        }

        //When there is no children, cut the string
        if(current.getLeftChild().equals(null)
                && current.getRightChild().equals(null)) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.setLeftChild(null);
            } else {
                parent.setRightChild(null);
            }
        }

        //When there is no right child, replace with left child
        else if (current.getRightChild().equals(null)) {
            if (current == root) {
                root = current.getLeftChild();
            } else if (isLeftChild) {
                parent.setLeftChild(current.getLeftChild());
            } else
                parent.setRightChild(current.getLeftChild());
        }

        //When there is no left child, replace with right child
        else if (current.getLeftChild() == null) {
            if (current == root) {
                root = current.getRightChild();
            } else if (isLeftChild) {
                parent.setLeftChild(current.getRightChild());
            } else
                parent.setRightChild(current.getRightChild());
        }

        //has grandchildren, pass them to the grandpas
        else {
            //find the grandchildren
            Node successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.setLeftChild(successor);
            } else {
                parent.setRightChild(successor);
            }
            //bring grandkids and granppas together
            successor.setLeftChild(current.getLeftChild());
        }

    }



    private Node getSuccessor (Node otroNode) {
        Node successorParent = otroNode;
        Node successor = otroNode;
        Node current = otroNode.getRightChild();
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.getLeftChild();
        }

        if (successor != otroNode.getRightChild()) {
            successorParent.setLeftChild(successor.getRightChild());
            successor.setRightChild(otroNode.getRightChild());
        }

        return successor;

    }   

        @Override
    public Node find(LocalDate valueToFind) {
        Node current = root;
        while (current.getDate() != valueToFind) {
            if (valueToFind.isBefore(current.getDate())) {
                current = current.getLeftChild();
            } else {
                current = current.getRightChild();
            }
            if (current == null) {
                return null;
            }
        }
        return current;

    }

        if (isEmpty()) {
            return null;
        }
        if (root.getDate().isAfter(valueToFind)) {
            find(root.getLeftChild().getDate());

        } else if (root.getDate().isBefore(valueToFind)) {
            find(root.getRightChild().getDate());

        } else if (root.getDate().equals(valueToFind)   ) {
            return root;
        }
        return null;
        **/


    private String toString(Node todoElArbol) {
        if (todoElArbol == null){
            return "";
        } else {
            return (toString(todoElArbol.getLeftChild()) + ","
            + todoElArbol.getDate() + ","
            + toString(todoElArbol.getRightChild()))
            .replaceAll(",+", ",").replaceAll("^,", "").replaceAll(",$", "");

        }
    }


    @Override
    public String toString() {
        return toString(root);
    }
}

节点类:

import java.time.LocalDate;


public class Node implements IBinaryTreeNode {

    private LocalDate date;

    private Node leftChild;

    private Node rightChild;

    public Node (LocalDate valueToInsert) {
        date = valueToInsert;

    }
    @Override
    public LocalDate getDate() {

        return date;
    }

    @Override
    public void setDate(LocalDate pDate) {

        date = pDate;
    }

    @Override
    public Node getLeftChild() {

        return leftChild;
    }

    @Override
    public void setLeftChild(Node pLeftChild) {

        leftChild = pLeftChild;
    }

    @Override
    public Node getRightChild() {

        return rightChild;
    }

    @Override
    public void setRightChild(Node pRightChild) {

        rightChild = pRightChild;
    }

}

Answer 1

你的二分查找已经坏了。

@Override
public Node find(LocalDate valueToFind) {
    if (isEmpty()) {
        return null;
    }
    if (root.getDate().isAfter(valueToFind)) {
        find(root.getLeftChild().getDate());

    } else if (root.getDate().isBefore(valueToFind)) {
        find(root.getRightChild().getDate());

    } else if (root.getDate() == valueToFind) {
        return root;
    }
    return null;
}

该方法应该递归地在树中查找值(深度优先搜索)。

类似的方法通常分两部分实现，公共(public)部分和递归的实现:

@Override
public Node find(LocalDate valueToFind) {
    if (isEmpty()) {
        return null;
    }
    return findRecursive(root, valueToFind);
}

然后是私有(private)/递归方法:

private Node findRecursive(Node node, LocalDate valueToFind) {
    if (node == null) {
        return null;
    }
    if (node.getDate().isAfter(valueToFind)) {
        return findRecursive(node.getLeftChild(), valueToFind);
    }
    if (node.getDate().isBefore(valueToFind)) {
        return findRecursive(root.getRightChild(), valueToFind);
    }
    if (node.getDate().equals(valueToFind)) {
        return node;
    }
    return null;
}

请注意，递归调用中没有引用 root，并且还将 == 比较更改为 .equals(...) .