我正在写二叉树的删除函数。我把我的案子分为三个。一个同时具有两个子项null。一个有一个子项为null,另一个有两个子项都不为null。我在案例3之后递归调用delete操作。对于ex,如您所见,我在节点50上调用了删除操作。这将用75替换父节点50。现在我必须从右子树中删除节点75。所以我递归地运行了delete过程。但我没有得到所需的输出,因为75是50的右子树中的根节点。如何修复它以便能够删除根目录
class BST {
public static void main(String args[]) {
Tree tr;
tr = new Tree(100);
tr.insert(50);
tr.insert(125);
tr.insert(150);
tr.insert(25);
tr.insert(75);
tr.insert(20);
tr.insert(90);
tr.delete(50);
}
}
class Tree {
public Tree(int n) {
value = n;
left = null;
right = null;
}
public void insert(int n) {
if (value == n)
return;
if (value < n)
if (right == null)
right = new Tree(n);
else
right.insert(n);
else if (left == null)
left = new Tree(n);
else
left.insert(n);
}
public Tree min() {
if(left == null)
return this;
else
return left.min();
}
public Tree max(){
if(right == null)
return this;
else
return right.max();
}
public Tree find(int n)
{
if(n == value)
return this;
else if(n > value)
return right.find(n);
else if(n < value)
return left.find(n);
else
return null;
}
public Tree findParent(int n, Tree parent)
{
if(n == value)
return parent;
else if(n > value)
return right.findParent(n, this);
else if(n < value)
return left.findParent(n, this);
else
return null;
}
public void case1(int n, Tree tr, Tree parent)
{
if(parent.left.value == n)
parent.left = null;
else
parent.right = null;
}
public void case2(int n, Tree tr, Tree parent)
{
if(parent.left!=null && parent.left.value == n)
parent.left = parent.left.left;
else
parent.right = parent.right.right;
}
public void case3(int n, Tree tr, Tree parent)
{
int min = tr.right.min().value;
tr.value = min;
tr.right.delete(min);
}
public void delete(int n) {
// fill in the code for delete
Tree tr = find(n);
Tree parent = findParent(n, this);
if(tr == null)
{
System.out.println("The tree is not present in Binary Tree");
return;
}
if(tr.left == null && tr.right == null)
{
case1(n, tr, parent);
}
else if((tr.left == null) || (tr.right == null))
{
System.out.print(tr.right.value);
System.out.print(parent.right.value);
case2(n, tr, parent);
}
else
{
case3(n, tr, parent);
}
}
protected int value;
protected Tree left;
protected Tree right;
}
你有两个选择:
第一种方式:您可以将树结构包装在一个隐藏此数据结构实现细节的对象中。将所有相关的修改调用转发给根节点,并实现删除操作来处理根节点应该删除的情况:在这种情况下,您可以替换包装器对象中的引用。
第二种方法:重用现有资源。不要删除根节点,而是用所需的新内容覆盖它。这样,您就不必查找和更改节点的父节点,问题就解决了。但这似乎容易得多。
我读了一个算法来寻找二叉树中两个节点之间的距离。 这段代码在二叉树中找到(从根到给定节点的1个距离)。 我不明白的是,“x”有两个值,一个来自左子树,另一个来自右子树,它如何知道返回哪个值 例如,如果树类似于: 然后调用, 那么,在语句“”中,它如何返回正确的x值?
首先,这是家庭作业,所以把它放在外面。 我应该用特定的方法实现二叉查找树: void insert(字符串)、boolean remove(字符串)和boolean find(字符串)。 我已经能够成功地编程和测试插入,并找到方法,但我有困难与删除。 我的程序中发生的事情是,删除实际上并没有从树中删除任何东西,我相信这是因为它只引用当前节点的本地创建,但我可能错了。我认为我可以实现我需要测试的不同
开始为不平衡的BST结构编写删除函数。为第一种情况手动运行一些测试(节点没有子节点)。决定在大小为1的树上运行它(仅在根上),出于某种原因,它似乎没有按照我在本语句第3行期望的方式将根重新分配到: 然后,当我在单节点树上运行时,它应该只是
问题内容: 我想在非二叉树中搜索一个项目(任何节点都可以有n个孩子)并立即退出递归。所讨论的节点可以是任何节点,而不仅仅是叶子。 这是我的代码,但我没有完整的搜索。 nNode包含: (是孩子) 和数据对象。 问题答案: 探索第一个孩子后,您不应该退出。您不需要循环前面的语句。
我现在正在读一本关于从二叉搜索树中删除节点的书,书中描述的过程对我来说似乎不必要地复杂。 在1号情况下,如果我们删除40,它将替换为30;在 2 号情况下,如果我们删除 40,它将被替换 35。 但在书中,它说应该从要删除的节点的右子树中找到替换,这可能涉及一些复杂的操作。 我在这里遗漏了什么吗?请指出。
我正在阅读一本书,该书解释了如何从二元搜索树中删除节点,基本上如果我们有这棵树: 我们想删除节点4,书上说我应该: 在其右子树(即6)中找到4的继任者 交换4和6 从右子树中删除6 将4的左侧子树(在本例中仅为1)附加到新节点6 因此我们得到 然而,我想到了另一种方法来做到这一点: 找到4个右子树的最小元素(即6) 将4的左子树附加到6(它不会有左子树) 将父元素(10)附加到4的右侧元素(8)。