Поиск двоичного дерева

Question

Я работаю над своим двоичным деревом, написанным на c, но когда я начал искать внутри него, у меня начались проблемы, я не смог ничего найти в нем, сначала я думал, что я просто поиск по-другому, но когда я печатал обе стороны корня, я узнал, что оба они были NULL, даже когда память была выделена для этого узла.

Я хотел бы знать, где память, которую я выделил, если она не находится на дереве и почему она выделяется в другой части памяти, прямо сейчас меня интересует только то, что дерево работает, но если у вас есть полезный совет, это тоже будет здорово.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include "tree.h" 

int main() 
{ 
    Tree* root = initTree(); 
    insert(root, "John", 10); 
    insert(root, "Tom", 11); 
    printf("%d\n", root->value); 
    printf("%p %p\n", root->left, root->right); 
    if(root->left != NULL) 
     printf("Left : %d\n", root->left->value); 
    else if(root->right != NULL) 
     printf("Right : %d\n", root->right->value); 
    else 
     printf("Both sides are NULL\n"); 
    destroyTree(root); 
    return 0; 
} 

Tree* initTree() 
{ 
    Tree* root; 
    root = malloc(sizeof(Tree)); 
    strcpy(root->key, ""); 
    root->left = NULL; 
    root->right = NULL; 
    return root; 
} 

void insert(Tree* root, char* key, int value) 
{ 
    if(root == NULL){ 
     root = malloc(sizeof(Tree)); 
     root->left = NULL; 
     root->right = NULL; 
     strcpy(root->key, key); 
     root->value = value; 
     printf("Node added, (%s), %p\n",root->key, root); 
     return; 
    } 

    if(!strcmp(root->key, "")){ 
     strcpy(root->key, key); 
     root->value = value; 
     printf("Added key %s\n", root->key); 
     return; 
    } 
    if(strcmp(root->key, key) > 0){ 
     insert(root->left, key, value); 
     return; 
    } 
    else if(strcmp(root->key, key) < 0){ 
     insert(root->right, key, value); 
     return; 
    } 
    printf("I dont know where to put this\n"); 
} 

int find(Tree* root, char* key) 
{ 
    if(root == NULL) return -1; 
    if(!strcmp(root->key, key)){ 
     return root->value; 
    } 
    if(strcmp(root->key, key) > 0){ 
     return find(root->left, key); 
    } 
    else if(strcmp(root->key, key) < 0){ 
     return find(root->right, key); 
    } 
    if(root->left == NULL && root->right == NULL) 
     return 0; 
    return 0; 
} 

void destroyTree(Tree* root) 
{ 
    /*If we dont have a valid pointer to destroy then we return*/ 
    if(root == NULL) return; 
    /*If any of the sides from the Tree have data storaged in 
    *we proceed to destoy it*/ 
    if(root->left != NULL || root->right != NULL){ 
     /*We give priority to the right site always in order 
    *to destroy everithing organized*/ 
     if(root->right != NULL) 
      destroyTree(root->right); 
     if(root->left != NULL) 
      destroyTree(root->left); 
    } 
    /*If we reach the end of the tree, we free the block of memory 
    *stored there*/ 
    else if(root->left == NULL && root->right == NULL){ 
     free(root); 
     return; 
    } 
} 

Это tree.h

#ifndef TREE_H 
#define TREE_H 

typedef struct Tree Tree; 
struct Tree 
{ 
    char key[16]; 
    int value; 
    Tree* left; 
    Tree* right; 
}; 

Tree* initTree(); 
void insert(Tree* root , char* key, int value); 
int find(Tree* root, char* key); 
void destroyTree(Tree* root); 

#endif 

Answer 1

Могу я рекомендую вам избегать использования STRCPY, чтобы скопировать данные из ключа к ключу, но вместо того, чтобы использовать тетср и/или MemSet (так как это всегда 16 символов) , Я также рекомендую вам обнулить все, что вы malloc, чтобы вы знали состояние полученной вами памяти.

Ключ всегда 16 байт, ergo, при инициализации дерева memset (key, 0, 16) будет обнулять ключ (и будет выглядеть как пустая строка, если вы попытаетесь ее распечатать).

Затем вместо strcpy (root-> key, key) попробуйте memset (root-> key, key, 16). Это гарантирует, что вы не перезапишете свой 16-значный предел и будете идеально соответствовать исходному значению ключа.

При вставке нового ключа я рекомендую вам проверить размер нового ключа, чтобы убедиться, что он находится в пределах 16 символов (помните, что для завершения строки вам понадобится один символ как нуль, так что у вас действительно будет только 15 символов для вашего ключа). Если вы хотите усечь его, просто скопируйте 15 символов и аннулируйте последний.

Между тем, ваша функция initTree вызывает «malloc (sizeof (Tree)», предоставляя вам память, которая может быть установлена ​​на что угодно ... что означает, что ваше «значение» - это некоторое неопределенное число (поскольку вы явно устанавливаете все остальное) Вы должны иметь возможность безопасно называть memset (root, 0, sizeof (Tree)), чтобы свести на нет все (ключ, значение, левый и правый).

В ответ на ваш вопрос мне кажется, что вы . распределение памяти и положить его в дереве, но, как кто-то указал, что вам нужно каким-то образом, чтобы иметь дело с условием корня == 0

Один из комментаторов предложили:

void insert(Tree** root, char* key, int value) 

По какой-то причине, однако, это не кажется мне правильным. Я бы рекомендовал вам вернуть bool и вернуть false, если root == 0 вместо создания узла, true, когда вы фактически добавляете узел в дерево.

bool insert(Tree* root, char* key, int value) 

Затем документ, в котором вы должны иметь дерево, чтобы вставить что-либо в него.

Answer 2

Вы представили много кода. Я укажу только на первую серьезную ошибку, которая заключается в том, что C проходит по значению.

Когда указатель передается функции insert, делается копия этого указателя. Эта копия является аргументом Tree* root той же функции. Если он изменен, это не повлияет на исходный указатель вне функции.

Поэтому этот код ничего не делает, насколько указатель root обеспокоен:

insert(root, "John", 10); 

Если вы хотите изменить его либо Назначьте значения для него или передать адрес указателя:

root = insert(root, "John" , 10); 

или

insert(&root , "John" ,10); 

в любом случае, функция должна быть мо dified.

Answer 3

есть некоторые перерабатывает свои функции,

#include <stdio.h> 
#include <stdlib.h> 
// TREE_H 
typedef struct Tree Tree; 
struct Tree{ 
    char key[16]; 
    int  value; 
    Tree* left; 
    Tree* right; 
}; 

void insert(Tree** proot , char* key, int value); 
int  find(Tree* root, char* key,int *result); 
void destroyTree(Tree** proot); 
// TREE_H 

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
//#include "tree.h" 

int main() 
{ 
    Tree* root = NULL; 
    insert(&root, "John", 10); 
    insert(&root, "Tom", 11); 
    printf("%d\n",  root->value); 
    printf("%p %p\n", root->left, root->right); 

    if(root->left) 
     printf("Left : %d\n", root->left->value); 
    if(root->right) 
     printf("Right : %d\n", root->right->value); 

    if(!(root->left || root->right)) 
     printf("Both sides are NULL\n"); 

    if(1){ 

     int  val; 
     char *name = "John"; 

     printf("\n"); 
     if(find(root, name, &val)) 
      printf("%s's value = %d \n", name, val); 
     else 
      printf("%s do not exists\n", name); 
    } 

    destroyTree(&root); 
    return 0; 
} 



Tree * new_node(char *key, int value){ 
    Tree *node = calloc(1 , sizeof(Tree)); //calloc zero init buffer 

    if(node){ 
     strcpy(node->key, key); 
     node->value = value; 
    } 
    else { 
     perror("new_node"); 
     exit(-1); 
    } 

    return node; 
} 


// root is passed by reference (pointer to pointer) 
// so that it can be updated 
void insert(Tree** proot, char* key, int value) 
{ 
    Tree* root = *proot; 



    if(!root){ 
     root = new_node(key, value); 
     *proot = root; 
     printf("Node added, (%s), %p\n", root->key, root); 
     return; 
    } 

    if(strcmp(root->key, key) > 0){ 
     insert(&root->left, key, value); 
     return; 
    } 
    else if(strcmp(root->key, key) < 0){ 
     insert(&root->right, key, value); 
     return; 
    } 
    else if(strcmp(root->key, key) == 0){ 
     root->value=value; 
     printf("key %s updated to %d\n",key,value); 
     return; 
    } 
    printf("you should never see this\n"); 
} 


// value can be 0, so it is better to modify 
// this to return either success or failure, 
// and store result in an external variable (3rd parameter) 
int find(Tree* root, char* key,int *result) 
{ 
    if(!root) 
     return 0; 

    if(!strcmp(root->key, key)){ 
     *result= root->value; 
     return 1; 
    } 

    return 
     find(root->left, key, result) 
     || 
     find(root->right, key, result); // if the first call succeed we never get here 
} 

// same as inser (pointer to pointer to Tree) 
void destroyTree(Tree** proot) 
{ 
    Tree* root = *proot; 

    if(!root) // right && left will be checked here 
     return; 

    destroyTree(&root->right); 
    destroyTree(&root->left); 

    free(root); 
    *proot = NULL; 
    return; 

}