随机二叉树中的插入函数 [英] Insertion function in a random binary tree
问题描述
我在C ++中的此二叉树中的插入函数遇到问题.节点已正确插入,直到需要再次在右侧或左侧添加一个节点为止.该功能认为在我已经在那些位置插入节点的情况下,我的左侧或右侧没有任何节点.
I'm having a problem with my insertion function in this binary tree in C++. The nodes are correctly inserted until I need to add again a node to the right or to the left. The function thinks I don't have any nodes to either the left or the right in the case being that I already inserted nodes in those places.
这是我的代码:
void insert(string data)
{
srand(time(NULL));
int r;
node *aux=head;
node *n=new node(data);
if (head==NULL)
{
head =n;
return;
}
while (aux!=NULL)
{
r=rand()%100;
if (r>50)
{
cout<<"\nRandom is "<<r<<", Therefore we have to go to the right."<<endl;
aux=aux->right;
}
else
{
cout<<"\nRandom is "<<r<<", Therefore we have to go to the left."<<endl;
aux=aux->left;
if (aux!=NULL)
{
cout<<aux->getdata()<<endl;
}
}
}
aux=n;
cout<<"\nWe insert "<<aux->getdata()<<endl;
}
推荐答案
以下是您的代码的略微修改:
Here's a slight modification of your code:
void insert(string data)
{ srand(time(NULL));
int r;
node *aux=head;
node *n=new node(data);
if(head==NULL){
head =n;
return;
}
while(aux!=NULL) // We could put while(true) here.
{
r=rand(); // Modulo is a somehow slow operation
if((r & 1 )== 0) // This is much faster. It checks if r is even
{ cout<<"\nRandom is "<<r<<", which is even therefore we have to go to the right."<<endl;
if ( aux->right == NULL) // We found an empty spot, use it and break
{
aux->right = n; break;
}
else // else move to the right child and continue
{
aux=aux->right;
cout<<aux->getdata()<<endl;
}
}
else
{
cout<<"\nRandom is "<<r<<", which is odd Therefore we have to go to the left."<<endl;
if ( aux->left == NULL) // We found an empty spot, use it and break
{
aux->left = n; break;
}
else // else move to the left child and continue
{
aux=aux->left;
cout<<aux->getdata()<<endl;
}
}
}
cout<<"\nWe insert "<<n->getdata()<<endl;
}
主要原因是您滥用辅助功能.这是一个示例,希望对您有所帮助:
THe main reason is that you are misusing aux. Here's an example which I hope will help you identify your mistake:
node * aux = head; // suppose head doesn't have any child node
node * n = new node(data);
aux = aux->left; // Set aux to point on the left child of head
aux = n; // Set aux to point on n
cout << aux == NULL?"Aux is null":"Aux is not null" << endl;
cout << head->left == NULL?"Left is null":"Left is not null" << endl;
此代码应返回:
Aux is not null
Left is null
原因是,当我们将 n 分配给 aux 时,我们只是告诉 aux 指向 n 而不是指向左侧节点.我们没有将 n 分配为head的左侧孩子.
The reason is that when we assigned n to aux, we simply told aux to point on n instead of pointing on the left node. We didn't assign n to be the left child of head.
您也可以通过将aux声明为node的指针来解决此问题.
You could also solve this issue by declaring aux to be a pointer of a pointer of node.
node * * aux = &head;
这篇关于随机二叉树中的插入函数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!