英文:
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 ) < 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 == ( 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 )
{
}
}
答案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 < root.key)
root.left = remove(root.left, key);
else if (key > 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;
}
专注分享java语言的经验与见解,让所有开发者获益!
评论