二叉搜索树实现 - 搜索函数找不到节点 (Java)

Question

我正在Java中实现一个二叉搜索树。但是，我的search函数似乎在删除函数中无法正常工作。它总是找不到树内的Nodes，无论它们是否真的在树中。我认为我的逻辑是正确的，根据要搜索的Node是更大还是更小，比较节点左右移动，但我在return值时可能会遇到一些问题。如果添加 Node 类或程序测试会有所帮助，我可以这样做。有什么建议吗？

public class BinarySearchTree {
    private boolean empty = true;
    private int size = 0;
    private Node root;
    public BinarySearchTree(Node root)
    {
        this.root = root;
    }
    public Node[] search(int value)
    {
        Node parent = null;
        Node currentNode = root;
        Node[] returnList = new Node[2];
        while ( currentNode != null )
        {
            if (currentNode.getValue() == value)
            {
                returnList[0] = parent;
                returnList[1] = currentNode;
                return returnList;
            }
            else if (value < currentNode.getValue())
            {
                parent = currentNode;
                currentNode = currentNode.getLeft();
            }
            else if (value > currentNode.getValue())
            {
                parent = currentNode;
                currentNode = currentNode.getRight();
            }
        }
        return returnList;
    }
    public void add(int value)
    {
        Node comparingNode = root;
        while (true)
        {
            if (comparingNode.getValue() == value)
            {
                System.out.println("Tried to add duplicate value of " + value);
                break;
            }
            if (comparingNode.getLeft() == null && comparingNode.getRight() == null)
            {
                if (value > comparingNode.getValue())
                {
                    comparingNode.setRight(new Node(value));
                }
                if (value < comparingNode.getValue())
                {
                    comparingNode.setLeft(new Node(value));
                }
                break;
            }
            else
            {
                if (value < comparingNode.getValue())
                {
                    if (comparingNode.getLeft() == null)
                    {
                        comparingNode.setLeft(new Node(value));
                        break;
                    }
                    else
                    {
                        comparingNode = comparingNode.getLeft();
                    }
                }
                if (value > comparingNode.getValue())
                {
                    if (comparingNode.getRight() == null)
                    {
                        comparingNode.setRight(new Node(value));
                        break;
                    }
                    else
                    {
                        comparingNode = comparingNode.getRight();
                    }
                }
            }
        }
    }
    public void remove(int value)
    {
        Node[] nodesFound = search( value );
        Node parent = nodesFound[0];
        Node child = nodesFound[1];
        boolean fLeft = ( parent.getLeft() == child );
        // child node has no children.
        if (fLeft)
        {
            parent.setLeft(null);
        }
        else
        {
            parent.setRight(null);          
        }
        if( child.getLeft() != null && child.getRight() == null )
        {
            // child node has only left child.
            if( fLeft )
            {
                parent.setLeft(child.getLeft());
            }
            else
            {
                parent.setRight(child.getLeft());
            }
        }
        else if ( child.getRight() != null && child.getLeft() == null )
        {
            // child node has only right child.
            if( fLeft )
            {
                parent.setLeft(child.getRight());
            }
            else
            {
                parent.setRight(child.getRight());
            }
        }
        else
        {
            // child node has both children.
            if( child.getRight().getLeft() == null )
            {
                child.getRight().setLeft( child.getLeft() );
                parent.setRight( child.getRight() );
            }
            else
            {
                Node[] returnList = findLeftMost2Children(child.getRight());
                Node leftMostParent = returnList[0];
                Node leftMostChild = returnList[1];
                leftMostParent.setLeft(null);
                leftMostChild.setLeft(child.getLeft());
                leftMostChild.setRight(child.getRight());
                parent.setRight(leftMostChild);
            }
        }
    }
    public Node getRoot()
    {
        return root;
    }
    public void outputTreeInOrder( Node root )
    {
        if( root == null )
            return;
        // Output the left tree.
        if( root.getLeft() != null )
            outputTreeInOrder( root.getLeft() );
        // Output the current node.
        System.out.print( root.getValue() + " " );
        // Output the right tree.
        if( root.getRight() != null )
            outputTreeInOrder( root.getRight() );       
    }
    private Node[] findLeftMost2Children( Node root )
    {
        Node parent = null;
        Node current = root;
        while (current.getLeft() != null)
        {
            parent = current;
            current = current.getLeft();
        }
        Node[] returnList = new Node[2];
        returnList[0] = parent;
        returnList[1] = current;
        return returnList;
    }
}

Answer 1

我用问题中的代码更正了。我意识到在删除时必须为移动节点设置适当的指针，而不仅仅是更改值。您必须实际移动node，并为它及其parent提供新的pointers。