没有子节点的Java Binary Search Tree Delete节点 [英] Java Binary Search Tree Delete node with no children

问题描述

我正在处理要删除的节点是节点的情况.我不确定是否需要跟踪父级，以便在找到要删除的节点时将其父级指针设置为null.但是，我怎么知道要删除的节点是哪个子节点呢?我是否需要更多if语句?

I'm working on the case where the node to be deleted is a node. I'm not sure if I need to keep track of the parent so that when I find the node to delete so I can set its parents pointer to null. But then how would I know which child the node to be deleted is? Do I need more if statements?

感谢任何帮助，我觉得它不太复杂，但是我对如何真正摆脱节点感到困惑.

Any help is appreciated, I feel its not too complicated but I'm just confused on how to actually get rid of the node.

这是我到目前为止所拥有的:

This is what I have so far:

public void insert(E s) 
{
    root = insert(s, root);
} 

private Node<E> insert(E s, Node<E> T)
{
    //easiest case, empty tree, create new tree
    if(T == null)
    {
        T = new Node<E>(s);
    }
    //easiest case, found s
    else if(s.compareTo(T.getData()) == 0)
    {
        System.out.println("Item already present.");
    }
    //s is greater than T, insert on right subtree
    else if(s.compareTo(T.getData()) > 0)
    {
        T.setRight(insert(s, T.getRight()));
    }
    //s is less than T, insert on left subtree
    else
    {
        T.setLeft(insert(s,T.getLeft()));
    }
    return T;
}

public void delete(E d)
{
    delete( d, root);
}

private void delete( E d, Node<E> T)
{

    if(T == null)
    {

    }
    else if(d.equals(T.getData()))
    {
        System.out.println("it found the node at least");
        if(T.getRight() == null && T.getLeft() == null)
        {

        }
        //code other cases for a node with one child and node with two      children
    }
    else if(d.compareTo(T.getData()) > 0)
    {
        System.out.println("going right");
        delete(d, T.getRight());
    }
    //s is less than T, insert on left subtree
    else
    {System.out.println("going left");
        delete(d,T.getLeft());
    }

}

推荐答案

如果不想更改Node结构，则在遍历树时跟踪父节点.

Track the parent node as you traverse the tree like this if you don't want to change the Node structure.

private Node<E> parent;
public void insert(E s) 
{
    root = insert(s, root);
} 

private Node<E> insert(E s, Node<E> T)
{
    //easiest case, empty tree, create new tree
    if(T == null)
    {
        T = new Node<E>(s);
    }
    //easiest case, found s
    else if(s.compareTo(T.getData()) == 0)
    {
        System.out.println("Item already present.");
    }
    //s is greater than T, insert on right subtree
    else if(s.compareTo(T.getData()) > 0)
    {
        T.setRight(insert(s, T.getRight()));
    }
    //s is less than T, insert on left subtree
    else
    {
        T.setLeft(insert(s,T.getLeft()));
    }
    return T;
}

public void delete(E d)
{
    delete( d, root);
}

private void delete( E d, Node<E> T)
{

    if(T == null)
    {

    }
    else if(d.equals(T.getData()))
    {
        System.out.println("it found the node at least");
        if(T.getRight() == null && T.getLeft() == null)
        {
             if (parent != null){//For the first node, parent will be null
                  if (d.equals(parent.getRight().getData())){//Data matches with the right node of parent
                       parent.setRight(null);
                  }else{//Data matches with the left node of parent
                       parent.setLeft(null);
                  }
                  //Reset parent node
                  parent = null;
             }
        }
        //code other cases for a node with one child and node with two      children
    }
    else if(d.compareTo(T.getData()) > 0)
    {
        parent = T;// Make the current node as parent
        System.out.println("going right");
        delete(d, T.getRight());
    }
    //s is less than T, insert on left subtree
    else
    {
        parent = T;// Make the current node as parent
        System.out.println("going left");
        delete(d,T.getLeft());
    }

}

这篇关于没有子节点的Java Binary Search Tree Delete节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！