gpt4 book ai didi

java - 删除二叉搜索树中的节点

转载 作者:行者123 更新时间:2023-12-02 05:26:13 25 4
gpt4 key购买 nike

这不是作业。我对此完全受阻。我知道该怎么做,但我在操纵树时遇到困难。

下面的代码似乎适用于叶节点,但不适用于其他情况。以下代码可编译。请帮忙。

package com.binarytree;

import com.binarytree.Node;

public class BinaryTree1 {
private Node root;
private Node parent;

public BinaryTree1(){
root = null;
}

public Node getRoot() {
return root;
}

public void setRoot(Node root) {
this.root = root;
}

public Node insert(int data){
return insert(root, data);
}

private 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;
}

public void printTree(Node node){
if( node == null) return;

//System.out.println( "left: " + (node.left != null ? node.left.data : null) );
printTree(node.left);
System.out.print(node.data + " ");
//System.out.println( "right: " + (node.right != null ? node.right.data : null) );
printTree(node.right);
}

/**
* case 0: no children - leaf node - delete the parent link
* case 1: 1 child - make the parent to point to the node child and delete
* case 2: find min from right sub tree, copy value in targetted node and delete duplicate node
* (OR)
* find max from left sub tree, copy value in targetted node and delete duplicate node
* @param root
* @param data
*/
public Node deleteNode(Node myroot, int data){
if( myroot == null) return null;
else if( data < myroot.data ){ //left sub tree
myroot.left = deleteNode(myroot.left, data);
}
else if (data > myroot.data){
myroot.right = deleteNode(myroot.right, data);
}

else{ //found the node
//no child
if( myroot.left == null && myroot.right == null ){
myroot = null;
parent = myroot;
}
else if( myroot.left == null && myroot.right != null){
parent.right = myroot.right;
myroot = null;
}
else if (myroot.left != null && myroot.right == null){
parent.left = myroot.right;
myroot = null;
} //2 children
else{
Node temp = myroot.right;
myroot.data = temp.data;
myroot.right = myroot.right.right;
}
}

parent = myroot;

return parent;
}

}


package com.binarytree;

public class RunBinaryTree1 {
public static void main(String[] args){
BinaryTree1 bt = new BinaryTree1();
bt.setRoot(bt.insert(5));
bt.setRoot(bt.insert(3));
bt.setRoot(bt.insert(4));
bt.setRoot(bt.insert(1));
bt.setRoot(bt.insert(6));
bt.setRoot(bt.insert(9));
// bt.setRoot(bt.insert(2));

System.out.print("Nodes in the BST (In order) are: "); bt.printTree(bt.getRoot());
System.out.println("");

System.out.print("Nodes in the BST (In order) are: "); bt.printTree(bt.deleteNode(bt.getRoot(), 1));
bt.setRoot(bt.insert(1));

//DOES NOT WORK
System.out.print("Nodes in the BST (In order) are: "); bt.printTree(bt.deleteNode(bt.getRoot(), 6));
}
}


package com.binarytree;

public class Node {
Node left;
Node right;
int data;

public Node(int data){
this.data = data;
this.left = null;
this.right = null;
}
}

最佳答案

从平衡树中删除节点时需要注意三种可能性,搜索树通常就是这种情况。如果你的树不应该是自平衡的,请忽略讨论它的部分。即使它们 self 平衡的,这个特定方面也是复杂的,可能值得提出一个不同的问题。

另请记住,下面的示例树实际上并不是平衡的,它们只是用于显示操作。

<小时/>

首先,如果您的节点是叶子。在这种情况下,这很容易。您只需删除该节点即可。然后转换变成,删除 D:

  B             B
/ \ / \
A C ==> A C
\
D

如果您在本例中使用平衡树,请从您删除的节点 (C) 的父节点开始平衡,并从那里沿着树向上移动。

<小时/>

第二种情况,它有一个 child 。在这种情况下,你只需“抚养”那个 child ,包括指示等等。例如,删除下面的C:

  B             B
/ \ / \
A C ==> A D
\ \
D E
\
E

如果树是自平衡的,您将从上移到的节点开始,在本例中为 D。

<小时/>

第三种情况有点棘手,因为您要删除的节点有两个子节点,因此您既不能删除它也不能启动子节点。

在这种情况下,您要做的就是将该节点中的数据与其直接前任的数据交换,该前任保证是叶节点或仅具有左子节点的节点。

然后,您只需恢复到上面的情况 1 或 2 并删除前驱节点(现在包含您要删除的数据)并根据需要使用适当的规则重新平衡。

假设您要从以下节点中删除 F,首先将 F 与其前任 E 交换,然后删除 F(在本例中是从叶节点,因此使用上面的情况 1):

  B             B               B
/ \ / \ / \
A F ==> A E ==> A E
/ \ / \ / \
D G D G D G
/ \ \ / \ \ / \
C E H C F H C H
(swap EF) (del F)

其工作原理与列表中的工作原理相同:

Index: 12345678
ABCDEFGH

如果您想从该列表中删除 F,但第六个位置受到某种保护,您可以交换索引 5 和 6 处的数据:

Index: 12345678
ABCDFEGH

然后删除索引5处的数据:

Index: 1234567
ABCDEGH

查找节点(有两个子节点)的直接前驱节点的方法(有两个子节点)是先找到它的左子节点,然后继续向右移动,直到右子节点为 NULL,伪代码如:

def predecessor(n):
pre = n.left
while pre.right != null:
pre = pre.right
return pre

关于java - 删除二叉搜索树中的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25987343/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com