我试图通过使用insert函数创建一个二进制搜索树。
结果不是我所期望的，它仅
生成树节点的第一个值。谁能找出问题所在？
谢谢！
有人可以检查我的其他功能是否也正确吗？
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
struct node* left;
struct node* right;
int val;
}treeNode;
int searchTree(treeNode *T, int key, treeNode *T1, treeNode** p)
{
if(!T)
{
*p=T1;
return 0;
}
else if(T->val==key)
{
*p=T;
return 1;
}
else if(T->val<key)
{
searchTree(T->right,key,T,p);
}
else
{
searchTree(T->left,key,T,p);
}
return 1;
}
int insert(treeNode **T, int key)
{
treeNode *p;
treeNode *s;
if(!searchTree(*T,key,NULL,&p))
{
s= malloc(sizeof(treeNode));
s->val=key;
s->left=s->right=NULL;
if(!p)
{
*T=s;
}
else if(p->val<key)
{
p->right=s;
}
else
{
p->left=s;
}
}
else
{
return -1;
}
return 1;
}
int delete(treeNode **T)
{
treeNode *q;
if(!(*T)->left)
{
q=*T;
*T=(*T)->right;
free(q);
}
else if(!(*T)->right)
{
q=*T;
*T=(*T)->left;
free(q);
}
else
{
treeNode *s;
q=*T;
s=(*T)->right;
while(s->left)
{
q=s;
s=s->left;
}
(*T)->val=s->val;
if(q!=*T) q->left=s->right;
else q->right=s->right;
free(s);
}
return 1;
}
void preOrder(treeNode *T)
{
if(!T) return;
preOrder(T->left);
printf("%d\n",T->val);
preOrder(T->right);
}
int main() {
int a[10]={62,88,58,47,35,73,51,99,37,93};
treeNode *T=NULL;
for(int i=0;i<10;i++)
{
insert(&T,a[i]);
}
preOrder(T);
return 0;
}
结果是62，而不是整个数组！
您的搜索功能无法按预期工作
您可以删除它并执行以下操作：
int insert(treeNode ** t, int key)
{
if (*t == NULL)
{
treeNode * s = malloc(sizeof(treeNode));
s->val=key;
s->left=s->right=NULL;
*t = s;
}
else if ((*t)->val == key) /* I am not sure but it seems you do not want to insert several times the same key, else that case */
return -1;
else if((*t)->val < key)
insert(&(*t)->right, key);
else
insert(&(*t)->left, key);
return 1;
}
如您所见，代码要简单得多...而且可以正常工作
编译与执行
pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra -Wall t.c
pi@raspberrypi:/tmp $ ./a.out
35
37
47
51
58
62
73
88
93
99
您的删除功能不起作用，如果我delete(&t);在main的末尾添加并在valgrind下执行，则会发生内存泄漏：
==14950== definitely lost: 12 bytes in 1 blocks
==14950== indirectly lost: 96 bytes in 8 blocks
一个简单的方法是：
void delete(treeNode **t)
{
if (*t != NULL) {
delete(&(*t)->left);
delete(&(*t)->right);
free(*t);
*t = NULL;
}
}
更改之后，没有内存泄漏
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句