BST&递归 [英] BST & recursion

问题描述

先生们，


我有一个二进制搜索树ADT应该使用递归进行所有操作

除了isEmpty（）和isFull（）;


我已完成插入功能，插入数字10后，

20,30,15,5,9,3,17,4,7 ，6,8,1和调用showStructure（）我得到

以下（完美地工作）：


30

20< ;

17

15<

11

10<

9 \

8

7<

6

5<

4
3 /


删除10并调用showStructure（）后，我得到以下内容（丢失了

我的树右半部分）：

30 \

9 \

8

7<

6

5<

4

3 /


我做错了什么？

提前致谢，

Andrew

========================= ========================= ==

这是我的remove（）函数的代码：


template< class DT，class KF>

bool BSTree< DT，KF> :: remove（KF deleteKey）

{

return removeSub（root ，deleteKey）;

}


模板< class DT，class KF>

bool BSTree< DT，KF> :: removeSub（BSTreeNode< DT，KF> *& p，KF deleteKey）

{

if（deleteKey< p-> dataItem.key（））

{

removeSub（p-> left，deleteKey）;

}

else if（deleteKey> p-> dataItem.key（））

{

removeSub（p-> right，deleteKey）;

}

else

{

DT temp_data;

BSTreeNode< DT，KF> * temp_node = p;

if（p-> left == NULL）

{

p = p-> right;

删除temp_node;

cout<< \ nNode删除了;

返回true;

}

else if（p-> right == NULL）

{

p = p-> left;

删除temp_node;

返回true;

}

else

{int count = 0;

while（p-> right！= NULL）

{

p-> right-> left = p-> left;

// p-> right-> right = p- >权; //导致无限循环。

p = p->右;

}

删除temp_node;

}

}

返回false;

}

解决方案

" David White" < [e-mail]>写道......

不是女士们吗？


对不起，如果这冒犯了任何人。

我已经完成了插入功能，在插入数字
10,20,30,15,5,9,3,17,4,7,6,8,11并调用showStructure（）后，我发现
得到以下内容（完美无缺） ：

30
20<
17
15<
11
10<
9 \
8
7<
6
5<
4

删除10并调用showStructure（）后我得到以下内容（丢失

我树的右半边）：

3 0 \
9 \
8
7<
6
5<
4
3 /

我现在没有时间分析您的代码。但我发现你已经声明''p''作为指针的引用，就像你在链接的
列表中所做的那样。我只是想我会检查这次是你的意图。


是的，这是故意的（实际上，选择不是我的）。它也是我之所以有这么多问题的原因之一：我真的错过了什么呢

来引用指针和递归。

编程的一个重要部分是调试。你有什么办法尝试
看看它出了什么问题？一个明显的出发点是在每个地方显示一条消息，您可以更改附加到另一个树的树的一部分，每次删除一个节点。您也可以尝试调用
函数在某些点显示整个树，这样您就可以看到到目前为止发生的总变化。如果您有可用的工具，单步执行代码也可以帮助您找到问题。

DW

我这样做了：提供的树的打印输出是在删除包含10的节点之前和之后在

removeSub（）函数内完成的。


我做了不包括那个调试信息，因为我被告知在早期帖子中将这些代码包含在类中是不好的做法。

从调试中我看到树的右边部分每次都掉下来

我试图移除一个有两个孩子的节点。尝试纠正这个

问题让我得到了：1）与前一个例子相反（缺少

左半部分树）。 2）无限循环，3）最少的时间来找到解决方案，以及4）偏头痛。


去除有一个或没有孩子的叶子很好，我真正的问题是

有两个孩子的节点。


谢谢，

Andrew

[snip]

我没有包含调试信息，因为我被告知
它不好练习在早期帖子中的类中包含这样的代码。
从调试中我看到，当我尝试删除有两个孩子的节点时，树的右边部分每隔
就会掉落一次。尝试纠正这个问题让我有了：1）与前一个例子相反（缺少
左半边的树）。 2）无限循环，3）寻找解决方案的时间极短，以及4）偏头痛。

有一个或没有孩子的叶子去除很好，我真正的问题是
，节点有两个孩子。

谢谢，
Andrew

这就是我被教导如何删除内部来自二叉树的节点。


如果节点有两个子节点，请按顺序查找下一个节点（即向右移动

一次，然后向左移动尽你所能）。此节点最多只能有一个
子节点，因此您可以使用已经为您工作的技术将其删除

。但在删除它之前，请将其值复制到您正在尝试的节点上。

要删除。


HTH


john

Andrew Edwards< ed ******* @ spamfreeusa.com>在消息中写道

新闻：TG ********************** @ twister.southeast.rr .com ...

David White < [e-mail]>写了...

编程的一个重要部分是调试。你怎么做才能尝试

看看它出了什么问题？一个明显的出发点是在每个地方显示一条消息，你将
附加到另一个树上的树的一部分更改，并且每次删除一个节点。您也可以尝试调用
函数在某些点显示整个树，这样您就可以看到
到目前为止发生的总变化。如果您有可用的工具
，单步执行代码也可以帮助您找到问题。

我这样做了：提供的树的打印输出已完成在删除包含10的节点之前和之后的
removeSub（）函数内部。

我没有包含调试信息，因为我被告知

在较早的帖子中将这些代码包含在类中是不好的做法。


是的，对于那些试图查看错误的人来说，没有调试

代码会更好。

来自调试我看到，当我尝试删除有两个孩子的节点时，树的右边部分每隔
就会掉落一次。尝试纠正这个问题让我有了：1）与前一个例子相反（缺少
左半边的树）。 2）无限循环，3）寻找解决方案的时间极短，以及4）偏头痛。

有一个或没有孩子的叶子去除很好，我真正的问题是
，节点有两个孩子。

如果你没有得到解决问题的答案，我建议你

发布整个类，包含类定义，以及插入值的测试代码

。虽然通常最好发布显示问题的最小代码

，但这种递归树代码并不是一件容易的事情。

得到一个'没有花一些时间在上面，所以有一个完整的，可编辑的测试程序可能会让人更容易找到

出了什么问题。


此外，一眼就看出你的最终''其他''中的循环是什么？b $ b b b目标不是很明显。要删除一个值，我看不出在任何

情况下改变它下面的所有节点的必要性，除非它是某种优化的b / b
优化树更平衡。如果是重新平衡，请尝试使用两个

分支中相应的一个来替换要删除的节点，只是为了看看你是否还有同样的问题。至少

你可能会缩小它。


DW

Gentlemen,

I have a Binary Search Tree ADT that should use recursion for all operation
except for isEmpty() and isFull();

I have completed the insert function, and after inserting the numbers 10,
20, 30, 15, 5, 9, 3, 17, 4, 7, 6, 8, 11 and calling showStructure() I get
the following (works perfectly):

30
20<
17
15<
11
10<
9\
8
7<
6
5<
4
3/

After deleting 10 and calling showStructure() I get the following (lost the
right half of my tree):
30\
9\
8
7<
6
5<
4
3/

What am I doing wrong?
Thanks in advance,
Andrew
================================================== ==
Here is the code for my remove() function:

template < class DT, class KF >
bool BSTree<DT,KF>:: remove ( KF deleteKey )
{
return removeSub( root, deleteKey );
}

template < class DT, class KF >
bool BSTree<DT,KF>:: removeSub ( BSTreeNode<DT,KF>*& p, KF deleteKey )
{
if ( deleteKey < p->dataItem.key() )
{
removeSub ( p->left, deleteKey );
}
else if ( deleteKey > p->dataItem.key() )
{
removeSub ( p->right, deleteKey );
}
else
{
DT temp_data;
BSTreeNode<DT,KF>* temp_node = p;
if ( p->left == NULL )
{
p = p->right;
delete temp_node;
cout << "\nNode deleted";
return true;
}
else if ( p->right == NULL )
{
p = p->left;
delete temp_node;
return true;
}
else
{ int count=0;
while (p->right != NULL)
{
p->right->left = p->left;
// p->right->right = p->right; // causes infinite loop.
p = p->right;
}
delete temp_node;
}
}
return false;
}

解决方案

"David White" <[e-mail]> wrote...

Not ladies as well?
Sorry if this offends anyone.

I have completed the insert function, and after inserting the numbers 10, 20, 30, 15, 5, 9, 3, 17, 4, 7, 6, 8, 11 and calling showStructure() I get the following (works perfectly):

30
20<
17
15<
11
10<
9\
8
7<
6
5<
4
3/

After deleting 10 and calling showStructure() I get the following (lost

the

right half of my tree):
30\
9\
8
7<
6
5<
4
3/

I don''t have time to analyse your code right now. But I see that you have
declared ''p'' as a reference to a pointer, just as you did in your linked
list. I just thought I''d check that this is what you intended this time.
Yes this is intentional(actually, the choice is not mine). It is also one of
the reason why I have so much problem: I truly am missing something when it
comes to reference pointers and recursion.
An essential part of programming is debugging. What have you done to try to see where it''s going wrong? An obvious starting point is to display a
message at each place you change the part of the tree that is attached to
another, and each time you delete a node. You call also try calling a
function to display the entire tree at certain points, so you can see the
total changes that have occurred so far. If you have the tools available,
single-stepping through the code would also help you find the problem.

DW

I have done this: the printout of the trees provided were done inside the
removeSub() function before and after removing the node containing 10.

I did not include that debugging information because I was advised that it''s
not good practice to include such code within classes in an earlier post.
From debugging I see that the right portion of the tree falls off every time
I try to remove a node that has two children. Attempts to correct this
problem have left me with: 1) the reverse of the previous example (missing
left half of the tree). 2) infinite loops, 3) minimal amount of time to
find a solution, and 4) migraines.

Removal of leaves with one or no children woks fine, my real problem is with
nodes that have two children.

Thanks,
Andrew

[snip]

I did not include that debugging information because I was advised that it''s not good practice to include such code within classes in an earlier post.
From debugging I see that the right portion of the tree falls off every time I try to remove a node that has two children. Attempts to correct this
problem have left me with: 1) the reverse of the previous example (missing
left half of the tree). 2) infinite loops, 3) minimal amount of time to
find a solution, and 4) migraines.

Removal of leaves with one or no children woks fine, my real problem is with nodes that have two children.

Thanks,
Andrew

This is how I was taught to remove an internal node from a binary tree.

If the node has two children, find the next node in sequence (i.e. go right
once, and then left as far as you can). This node must have at most one
child, so you can delete it using the techniques that have already worked
for you. But before you delete it, copy its value to the node you are trying
to delete.

HTH

john

Andrew Edwards <ed*******@spamfreeusa.com> wrote in message
news:TG**********************@twister.southeast.rr .com...

"David White" <[e-mail]> wrote...

An essential part of programming is debugging. What have you done to try to

see where it''s going wrong? An obvious starting point is to display a
message at each place you change the part of the tree that is attached to another, and each time you delete a node. You call also try calling a
function to display the entire tree at certain points, so you can see the total changes that have occurred so far. If you have the tools available, single-stepping through the code would also help you find the problem.

I have done this: the printout of the trees provided were done inside the
removeSub() function before and after removing the node containing 10.

I did not include that debugging information because I was advised that

it''s not good practice to include such code within classes in an earlier post.
Yes, for those trying to see what''s wrong it''s better without debugging
code.
From debugging I see that the right portion of the tree falls off every time I try to remove a node that has two children. Attempts to correct this
problem have left me with: 1) the reverse of the previous example (missing
left half of the tree). 2) infinite loops, 3) minimal amount of time to
find a solution, and 4) migraines.

Removal of leaves with one or no children woks fine, my real problem is with nodes that have two children.

In case you don''t get an answer that solves the problem, I suggest that you
post the entire class, incuding the class definition, and your test code
that inserts the values. Though it''s usually best to post the minimum code
that exhibits the problem, this kind of recursive tree code isn''t trivial to
get one''s head around without spending some time on it, so having a
complete, compilable test program might make it easier for someone to find
what''s wrong.

Also, it isn''t obvious at a glance what the loop in your final ''else'' is
aiming to do. To delete one value, I can''t see the necessity in any
circumstance to alter all the nodes below it, unless it is some sort of
optimization to make the tree more balanced. If it is re-balancing, try
replacing the node to be deleted with the appropriate one of its two
branches instead, just to see if you still have the same problem. At least
you might narrow it down.

DW

这篇关于BST&amp;递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！