java - 删除二叉树中的节点

Question

这是一个使用字符串的二叉搜索树，我想删除根。 This is my binary search tree visualization 如果“adam”是我的根并且我想删除它，那么“beta”应该是我的新根。我似乎在我的 deletemethod2 中遇到 NullPointerException 。

if (nodeToDelete.parent.leftChild == nodeToDelete)

此方法是否应该跳过此 if 语句并移至 else if，因为我的树中没有比“adam”更小的东西？它应该集中在树的右侧。

else if (nodeToDelete.parent.rightChild == nodeToDelete)

----------

    public void remove(String word) {
            Node nodeToDelete = find(word);

            if (nodeToDelete!=null) {
                if (nodeToDelete.leftChild==null && nodeToDelete.rightChild== null) {
                    deletemethod1(nodeToDelete); // node had no children
                }
                else if(nodeToDelete.leftChild!=null && nodeToDelete.rightChild!= null){
                    deletemethod3(nodeToDelete); // both node has children
                }
                else if(nodeToDelete.leftChild!=null){
                    deletemethod2(nodeToDelete); // left child should be deleted
                }
                else if(nodeToDelete.rightChild!=null){
                    deletemethod2(nodeToDelete);// right child should be deleted
                }

            }

        }

        private void deletemethod3(Node nodeToDelete) {
            //              example
            //          50
            //              70  <-- delete
            //            59    80
            //                 65 90    
            Node minNode= minlefttraversal(nodeToDelete.rightChild); // temporarily stores the node thats being deleted
             if ((minNode.leftChild != null) || (minNode.rightChild != null)) {
                   deletemethod2(minNode); /// if minNode have right child connected to it
                  }
                  else {
                   deletemethod1(minNode);// if minNode does not have any child connected to it
                  }


            minNode.parent=nodeToDelete.parent; 
            minNode.leftChild=nodeToDelete.leftChild;
            minNode.rightChild=nodeToDelete.rightChild;
            if(nodeToDelete.parent==null){
                root= minNode;
            }
            else{

                if (nodeToDelete.parent.leftChild.equals(nodeToDelete))
                {
                    nodeToDelete.parent.leftChild = minNode;
                } 
                else if (nodeToDelete.parent.rightChild.equals(nodeToDelete))
                {
                    nodeToDelete.parent.rightChild = minNode;
                }

            }
        }   


        /* Finds minimum element in subtree rooted on leftChild */
        private Node minlefttraversal(Node node){
            if(node.leftChild==null){
                return node;
            }
            return minlefttraversal(node.leftChild);
        }

    private void deletemethod2(Node nodeToDelete) {
            //          example
            //              50
            //delete -> 20      70
            //        19       59 80

            if (nodeToDelete.parent.leftChild == nodeToDelete) {

                if (nodeToDelete.leftChild != null) {
                    nodeToDelete.parent.leftChild = nodeToDelete.leftChild;
                } else if (nodeToDelete.rightChild != null) {
                    nodeToDelete.parent.leftChild = nodeToDelete.rightChild;
                }
            } else if (nodeToDelete.parent.rightChild == nodeToDelete)

                if (nodeToDelete.leftChild != null) {
                    nodeToDelete.parent.rightChild = nodeToDelete.leftChild;
                } else if (nodeToDelete.rightChild != null) {
                    nodeToDelete.parent.rightChild = nodeToDelete.rightChild;
                }
        }

        private void deletemethod1(Node nodeToDelete){
            // check if the node that is being deleted is the left or right
            // child of the parent of the node.     

            //              example
            //                  5
            //                   \
            //  delete ->         8
            //
            if (nodeToDelete.parent == null)
            {
                nodeToDelete =null;
            }
                if (nodeToDelete.parent.leftChild==nodeToDelete) {
                    nodeToDelete.parent.leftChild = null;
                } else if (nodeToDelete.parent.rightChild.equals(nodeToDelete)) {
                    nodeToDelete.parent.rightChild = null;
                }

        }

Answer 1

您的问题是您正在尝试删除根，因此在这种情况下

if (nodeToDelete.parent.leftChild == nodeToDelete)

nodeToDelete 是根，因此 nodeToDelete.parent 为 null 并且 nodeToDelete.parent.leftChild 抛出 NullPointerException.

当nodeToDelete.parent == null时，您必须添加特殊处理。