1

削除するノードがノードである場合に取り組んでいます。親を追跡する必要があるかどうかはわかりません。そのため、削除するノードが見つかったときに、その親ポインターを null に設定できます。しかし、削除するノードがどの子であるかをどのように知ることができますか? さらに if ステートメントが必要ですか?

助けていただければ幸いです。それほど複雑ではないと思いますが、実際にノードを削除する方法について混乱しています。

これは私がこれまでに持っているものです:

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());
    }

}
4

2 に答える 2

0 
public Node<E> search(Node<E> node, E d)
{
    while(node!=null && ((node.getLeft()!=null && !node.getLeft().getData().equals(d)) || (node.getRight()!=null && !node.getRight().getData().equals(d)))
    {
        if(d.compareTo(node.getData()) < 0)
        {
            node = node.getLeft();
        }
        else
        {
            node = node.getRight();
        }
    }

    return node;
}

private void delete(E d)
{
    // Search the node
    Node parent = search(root, d);

    // parent is the parent node under which the required node is present
    // Now check which child it is - left or right
    if(parent == null)
    {
         System.out.println("Element not found");
         return;
    }

    if(parent.getLeft().getData().equals(d))
    {
        // Left child
        parent.setLeft(null);
    }
    else
    {
        // Right child
        parent.setRight(null);
    }
}

注:parentにノードがあれば、Node<E>非常に簡単でした。

于 2013-03-02T06:40:29.990 に答える
0

ノード構造を変更したくない場合は、このようにツリーをトラバースしながら親ノードを追跡します。

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());
    }

}
于 2013-03-02T06:44:56.437 に答える