Вставка бинарного дерева поиска в C - PullRequest
Новая
       14

Вставка бинарного дерева поиска в C

1 голос
/ 26 марта 2019

Я пытался создать двоичное дерево поиска с помощью функции вставки.Результат оказался не таким, как я ожидал, он только дал первыйзначение узла дерева.Может кто-нибудь узнать в чем проблема?Спасибо!

А может кто-нибудь проверить, правильны ли и другие мои функции? 

#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, а не весь массив!

Ответы [ 2 ]

2 голосов
/ 26 марта 2019

Проблема в возвращаемом значении от 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...
}
0 голосов
/ 26 марта 2019

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

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

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); в конце основного и выполняюв 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;
  }
}

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

...