Блог

Я попытался создать двоичное дерево поиска с помощью функции 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,amp;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("%dn",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(amp;T,a[i]);
    }
    preOrder(T);
    return 0;
}
  

Результат равен 62, а не всему массиву!

Проблема заключается в возвращаемом значении из searchTree . Когда вы выполняете рекурсивные вызовы, вам нужно получить возвращаемое значение из этих рекурсивных вызовов. Нравится:

 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)
    {
        return searchTree(T->right,key,T,p);  //notice the return
    }
    else
    {
        return searchTree(T->left,key,T,p);  // notice the return
    }
    return 1;  // Not really needed...
}
  

Ваша функция поиска работает не так, как вы ожидаете

Вы можете просто удалить его и сделать :

 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(amp;(*t)->right, key);
   else
     insert(amp;(*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(amp;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(amp;(*t)->left);
    delete(amp;(*t)->right);
    free(*t);
    *t = NULL;
  }
}
  

После этого изменения утечек памяти не происходит