在BST中删除节点 [英] Deleting an node in BST
本文介绍了在BST中删除节点的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
这不是家庭作业.我对此完全被封锁.我知道该怎么办,但我在操纵树上遇到困难.请帮忙.
This is not an homework. I am just totally blocked on this. I know what to do but I am having difficulty manipulating the tree. please help.
我正在尝试从BST删除节点.我可以查找并找到父级并将其存储在树中.
I am trying to delete and node from an BST. I am able to lookup and find the parent and store it an tree.
package com.test.binarytree;
public class BinaryTreeDelete {
private Node root;
//create null binary tree
public BinaryTreeDelete(){
root = null;
}
//delete
public void delete(int target){
root = delete(root, target);
}
public Node delete(Node node, int target){
NodeWithParent temp = lookupFindParent(root, null, target);
if( node == null){
return null;
}
else{
if( node.left == null || node.right == null) //leaf node
{
//WHAT DO I DO HERE
//temp.parent.left = null;
//temp.parent.right = null;
//return null;
}
if( node.left != null && node.right == null ) //one child only on left
{
//WHAT DO I DO HERE
}
if( node.right != null && node.left == null ) //one child only on right
{
//WHAT DO I DO HERE
}
if( node.left != null && node.right != null ) //two children
{
//WHAT DO I DO HERE
}
}
return null;
}
private NodeWithParent lookupFindParent(Node node, Node parentNode, int target){
if( node == null ){
return null;
}
if( node.data == target){
return new NodeWithParent(node, parentNode);
}
else if( node.data > target ){
parentNode = node;
return lookupFindParent(node.left, parentNode, target);
}
else{
parentNode = node;
return lookupFindParent(node.right, parentNode, target);
}
}
//insert
public void insert(int data){
root = insert(root, data);
}
public Node insert (Node node, int data){
if(node == null){
node = new Node(data);
}
else{
if( data <= node.data ){
node.left = insert(node.left, data);
}
else{
node.right = insert(node.right, data);
}
}
return node;
}
//print tree
public void printTree(){
printTree(root);
System.out.println();
}
//print tree
private void printTree(Node node) {
if (node == null) return;
// left, node itself, right
printTree(node.left);
System.out.print(node.data + " ");
printTree(node.right);
}
//node class
public static class Node{
Node left;
Node right;
int data;
Node(int newNode){
data = newNode;
left = null;
right = null;
}
}
//node class
public static class NodeWithParent{
Node current;
Node parent;
NodeWithParent(Node current, Node parent){
this.current = current;
this.parent = parent;
}
}
public static void main(String[] args) {
BinaryTreeDelete bt = new BinaryTreeDelete();
//insert with inserts - tree increases on right if inserted in order
bt = new BinaryTreeDelete();
bt.insert(5);
bt.insert(3);
bt.insert(7);
bt.insert(1);
bt.insert(4);
bt.insert(6);
bt.insert(9);
bt.printTree();
//bt.delete(3);
//bt.delete(4);
//bt.delete(6);
bt.delete(9);
//bt.delete(5);
bt.printTree();
}
}
推荐答案
我将向您提供有关如何删除BST中的节点的逻辑(这意味着您必须自己编写代码).
I'm going to provide you the logic (that means you have to write the code yourself) of how to delete a node in a BST.
有三种情况.
- 要删除的节点的左子节点和右子节点均为null:删除该节点并将父节点指向null.
- 要删除的节点的左或右子节点(但不是两个)均为null:删除节点,但要确保其父节点指向要删除的节点的有效子节点.
- 要删除的节点的左子节点或右子节点都为null:在这种情况下,您必须找到要删除的节点的下一个较大元素.下一个更大的元素是要删除的节点的右子树中的最小元素.由于这是最小的元素,因此它的至少一个子元素为null.因此,将要删除的节点的值与下一个更大的节点交换.交换后,使用点1和2(以适合情况的任意一个)删除下一个更大的节点.现在,为什么下一个更大的节点而不是任何节点.因为如果用下一个更大的节点替换一个节点,则BST仍为BST.在一个示例中尝试一下,这将很明显.
这篇关于在BST中删除节点的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文