c++ 中的 AVL 树
我对这个非常简单的代码块有疑问。请给我你的建议。 (我的这个问题解决了,在解决这个问题的过程中,id为stakx的人确实帮助了我,唯一的问题是我使用的是stack
在代码之前你需要假设以下树
替代文本 http://img44.imageshack.us/img44/7016/avlimage06.jpg< /a>
如图所示,根为 8,堆栈有两个节点,即 6 和 4。我将此堆栈和根节点传递给以下代码
void Avltree::attachwithtree(treeNode* tree, Stack<treeNode>&s)
{
if(!s.isempty())
{
treeNode *stacknode;
stacknode=s.pop();
cout<<"\ninside the attachwithtree function, stack node is "<<stacknode->data;
stacknode->right=tree;//attaching the passed node to the right of popped node
root=stacknode;//setting the root to stack node which is the private data member of class
updatebalance(root);//this function is ok, it does not create problem
while(!s.isempty())
{
cout<<"\nstack is still not empty";
stacknode=s.pop();
cout<<"\nright side of "<<root->data<<" is "<<(root->right)->data;
//the below three lines causing the problem i don't know why,
root=stacknode;
treeNode* temp;
temp=root->right;
cout<<"\n\n\nthe right side of "<<temp->data<<" is now "<<(temp->right)->data;
updatebalance(root);
}
这是我正在使用的堆栈的pop方法的代码
template <class t>
t * Stack<t>::pop()
{
if(topelement!=NULL)
{
t* num;
current=topelement;
num=&(current->object);
topelement=topelement->preptr;
current=topelement;
return(num);
}
else
{
head=NULL;
}
}
这里是堆栈的push方法的代码
template <class t>
void Stack<t>::push(t &number)
{
Node<t>* newNode=new Node<t>;
if(head==NULL)
{
head=newNode;
topelement=newNode;
current=newNode;
head->object=number;
head->preptr=NULL;
}
else
{
topelement=newNode;
newNode->preptr=current;
current=topelement;
newNode->object=number;
}
}
I have a problem with this very simple block of code. please give me your advice .
(My this problem is solved, and in solving this problem the person having id stakx really helped me, the only problem was that i was using stack< treeNode >, when i saw the push method of the stack carefully, there is a copying process when i write head->object=number, so finally i made the stack of pointers, like this stack< treeNode* > and it really solved the problem , i have no problem now , i am very very thankful to the person stakx.)
before the code you need to suppse the following tree
alt text http://img44.imageshack.us/img44/7016/avlimage06.jpg
as you can see in the picture that root is 8 and stack have two nodes i.e 6 and 4. i pass this stack and root node to the following code
void Avltree::attachwithtree(treeNode* tree, Stack<treeNode>&s)
{
if(!s.isempty())
{
treeNode *stacknode;
stacknode=s.pop();
cout<<"\ninside the attachwithtree function, stack node is "<<stacknode->data;
stacknode->right=tree;//attaching the passed node to the right of popped node
root=stacknode;//setting the root to stack node which is the private data member of class
updatebalance(root);//this function is ok, it does not create problem
while(!s.isempty())
{
cout<<"\nstack is still not empty";
stacknode=s.pop();
cout<<"\nright side of "<<root->data<<" is "<<(root->right)->data;
//the below three lines causing the problem i don't know why,
root=stacknode;
treeNode* temp;
temp=root->right;
cout<<"\n\n\nthe right side of "<<temp->data<<" is now "<<(temp->right)->data;
updatebalance(root);
}
the ouptput of this function is given by
here is the code of the pop method of the stack that i am using
template <class t>
t * Stack<t>::pop()
{
if(topelement!=NULL)
{
t* num;
current=topelement;
num=&(current->object);
topelement=topelement->preptr;
current=topelement;
return(num);
}
else
{
head=NULL;
}
}
here is the code of push method of the stack
template <class t>
void Stack<t>::push(t &number)
{
Node<t>* newNode=new Node<t>;
if(head==NULL)
{
head=newNode;
topelement=newNode;
current=newNode;
head->object=number;
head->preptr=NULL;
}
else
{
topelement=newNode;
newNode->preptr=current;
current=topelement;
newNode->object=number;
}
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
原始答案:
是否堆栈上的节点
4
的右侧有一个不同的节点6
(其右侧有节点7
的节点)右)而不是您正在处理的节点6
(节点8
在其右侧)?您可以比较它们的地址,以确保您没有获得节点6
的两个不同副本。对上述参数的详细说明:
让我们看看您的方法的签名:
s
被定义为对Stack
的引用。它是否应该是一个
Stack
?根据您的
treeNode
类,当您推送X
在此堆栈上,您实际上最终得到的是X
的副本,而不是X
本身。同样,当您从堆栈中弹出时,您可能实际上并没有获得您推送的项目,而是获得了它的外观相同的副本!?这意味着,当您将节点
6
压入堆栈时,其右子节点是节点7
。但是您已将一个新的、相同的节点推送到堆栈上。即使您从堆栈中弹出该元素并更改它,您也只更改了一个副本并保留原始树节点与之前一样。因此,您将在节点
6
的不同副本上进行操作。首先,从堆栈中弹出它的副本,并附加一棵树作为其右子节点。检查这一点将给出正确的结果。然后,从堆栈中弹出节点
4
的副本。正如预期的那样,它的右子节点是节点6
,但是不是您刚刚修改的节点,而是原始节点!因此,您会在节点6
的右侧得到7
。演示按值传递和按引用传递之间的区别:
好的,这是使用指针或引用时需要了解的内容。它基本上显示了按值传递参数(将创建副本)或按引用传递参数(不会创建副本)之间的区别。
仔细研究它,然后看看它如何应用于您的问题。
提示:是的,在您的
pop
方法中,您使用指针,但最有可能使用指向最初压入堆栈的对象副本的指针。Original answer:
Could it be that the node
4
on the stack has a different node6
to its right (the one with node7
to its right) than the node6
(with the node8
on its right) you're working on? You could compare their addresses to make sure you haven't got two different copies of node6
around.Elaboration on the above argument:
Let's look at your method's signature:
s
is defined as a reference to aStack<treeNode>
.Could it be that it should be a
Stack<treeNode*>
?Depending on your
treeNode
class, it's possible that when you pushX
on this stack, you actually end up with a copy ofX
and notX
itself. Similarly, when you pop from the stack, you might not actually get the item you pushed, but an identical-looking copy of it!?This would mean that, at the time when you push node
6
on the stack, its right child is node7
. But you have pushed a new, identical node on the stack. Even if you pop this element from the stack and change it, you only change a copy and leave the original tree node as it was before.Therefore, you'd operate on different copies of node
6
. First, you pop a copy of it from the stack, and append a tree as its right child. Checking this will give the right result.Then, you pop a copy of node
4
from the stack. It's right child is node6
, as expected, BUT not the one you just modified but the original! Therefore you get7
on the right side of node6
.Demonstrating the difference between pass-by-value and pass-by-reference:
OK, here's something you need to understand when working with pointers or references. It basically shows the difference between passing a parameter by value (a copy will be created) or passing it by reference (no copy will be created).
Study it carefully and then see how it applies to your problem.
Hint: Yes, in your
pop
method, you work with pointers, but most likely with a pointer to a copy of the object originally pushed on the stack.那是你自己的 Stack 类吗?快速浏览一下 STL,我发现 pop() 的返回类型为 void。
stakx 可能在这里有所发现。如果您的 pop() 函数返回顶部元素的副本而不是对其的引用,则您所做的更改将仅应用于该副本。修改后是否将副本显式添加回树中的任何位置?
Is that your own Stack class? A quick look at the STL tells me that pop() has return type void.
It could be that stakx is onto something here. If your pop() function returns a copy of the top element rather than a reference to it, the changes you make will only apply to the copy. Do you explicitly add the copy back into the tree anywhere after modifying it?