有没有一种方法在不涉及父节点的情况下从二叉搜索树中移除一个节点?

huangapple 未分类评论44阅读模式
英文:

Is there a way to remove a node from a BST without incorporating the parent node into the program?

问题

这是我为你翻译的内容:

public class BinarySearchTree
{

    private Node root;

    public BinarySearchTree() { this.root = null; }

    public BinarySearchTree ( Node root ) { this.root = root; }

    public void add ( Integer key, String value )
    {
        if (root == null)
            root = new Node( key, value);
        else
            root.add( key, value);
    }

    public boolean contains ( Integer key )
    {
        return root == null ? null : ( boolean ) root.contains( key );
    }

    public void remove ( Integer key )
    {

    }
}

public class Node
{
    public Node left;
    public Node right;
    public Integer key;
    public String value;

    public Node (String value, Node left, Node right)
    {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Node (String value)
    {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public Node (Integer key, String value)
    {
        this.key = key;
        this.value = value;
    }

    public void add ( Integer key, String value )
    {
        if ( key.compareTo ( this.key ) < 0)
        {
            if ( left != null )
                left.add ( key, value );
            else
                left = new Node ( key, value );
        }
        else if ( key.compareTo ( this.key ) > 0 )
        {
            if ( right != null )
                right.add ( key, value );
            else
                right = new Node ( key, value);
        }
        else
            this.value = value;
    }

    public Serializable contains ( Integer key )
    {
        if ( this.key.equals(key) )
            return value;
        if ( key.compareTo ( this.key ) < 0 )
            return left == null ? null : left.contains ( key );
        else
            return right == null ? null : right.contains ( key );
    }

    public void remove ( Integer key )
    {

    }
}
英文:

This is for an assignment in my Data Structures class, and my professor wants me to create a remove method that removes a node from the tree based on an integer key. If the key is not found, then the function should do nothing. All the examples I've found base their tree on having a parent, left, right node. This program only has a left and right node. I tried to include as much of the classes as I thought would be relevant. Pretty much only the methods to print the trees were ommitted.

public class BinarySearchTree
{

    private Node root;

    public BinarySearchTree() { this.root = null; }

    public BinarySearchTree ( Node root ) { this.root = root; }

    public void add ( Integer key, String value )
    {
        if (root == null)
            root = new Node( key, value);
        else
            root.add( key, value);
    }

    public boolean contains ( Integer key )
    {
        return root == null ? null : ( boolean ) root.contains( key );
    }

    public void remove ( Integer key )
    {

    }
}

public class Node
{
    public Node left;
    public Node right;
    public Integer key;
    public String value;

    public Node (String value, Node left, Node right)
    {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Node (String value)
    {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public Node (Integer key, String value)
    {
        this.key = key;
        this.value = value;
    }

    public void add ( Integer key, String value )
    {
        if ( key.compareTo ( this.key ) &lt; 0)
        {
            if ( left != null )
                left.add ( key, value );
            else
                left = new Node ( key, value );
        }
        else if ( key.compareTo ( this.key ) &gt; 0 )
        {
            if ( right != null )
                right.add ( key, value );
            else
                right = new Node ( key, value);
        }
        else
            this.value = value;
    }

    public Serializable contains ( Integer key )
    {
        if ( this.key == ( key ) )
            return value;
        if ( key.compareTo ( this.key ) &lt; 0 )
            return left == null ? null : left.contains ( key );
        else
            return right == null ? null : right.contains ( key );
    }

    public void remove ( Integer key )
    {

    }
}

答案1

得分: 0

这里,remove() 没有 Node 类具有 parent 的情况。

Node remove(Node root, int key) {

    if (root == null)  return root;

    if (key < root.key)
        root.left = remove(root.left, key);
    else if (key > root.key)
        root.right = remove(root.right, key);
    else {
        // 只有一个子节点或没有子节点的节点
        if (root.left == null)
            return root.right;
        else if (root.right == null)
            return root.left;

        // 有两个子节点:获取中序后继(右子树中最小的)
        root.key = minValue(root.right);

        // 删除中序后继
        root.right = remove(root.right, root.key);
    }
    return root;
}
英文:

Here, remove() without Node class having a parent.

Node remove(Node root, int key) { 

    if (root == null)  return root; 
  
    if (key &lt; root.key) 
        root.left = remove(root.left, key); 
    else if (key &gt; root.key) 
        root.right = remove(root.right, key); 
    else { 
        // node with only one child or no child 
        if (root.left == null) 
            return root.right; 
        else if (root.right == null) 
            return root.left; 
  
        // node with two children: Get the inorder successor (smallest 
        // in the right subtree) 
        root.key = minValue(root.right); 
  
        // Delete the inorder successor 
        root.right = remove(root.right, root.key); 
    } 
    return root; 
} 

huangapple
  • 本文由 发表于 2020年4月6日 06:12:58
  • 转载请务必保留本文链接:https://java.coder-hub.com/61050228.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定