C-программа: двоичное дерево

Question

Мне нужна помощь в создании двоичной программы. В принципе, у меня есть разные методы для создания и использования таблицы двоичных деревьев (insert, find и т. Д.). Методы вызываются из других классов. Прямо сейчас я не думаю, что моя функция вставки работает правильно, поскольку, когда я печатаю таблицу, она показывает только последний узел дерева.

#include <stdio.h> 
#include <stdlib.h> 
#include <ctype.h> 
#define __USE_BSD 
#include <string.h> 

#include "speller.h" 
#include "dict.h" 

typedef struct node *tree_ptr; 
struct node { 
    Key_Type element; // only data is the key itself 
    tree_ptr left, right; 
    // add anything else that you need 
}; 

struct table { 
    tree_ptr head; // points to the head of the tree 
    // add anything else that you need 
}; 

Table initialize_table(/*ignore parameter*/) { 
    Table newTable = malloc(sizeof(Table)); 
    newTable->head = NULL; 
    return newTable; 
} 

void insert_again(Key_Type key, tree_ptr node) { 
    Key_Type currentKey = node->element; 
    //printf("%s\n%s", currentKey, key); 
    int keyCompare = strcmp(key, currentKey); 
    // Move to the left node. 
    if (keyCompare < 0) { 
     //printf("%s\n%s", currentKey, key); 
     // If left node is empty, create a new node. 
     if (node->left == NULL) { 
      tree_ptr newPtr = malloc(sizeof(tree_ptr)); 
      newPtr->element = key; 
      newPtr->left = NULL; 
      newPtr->right = NULL; 
      node->left = newPtr; 
     } else { 
      insert_again(key, node->left); 
     } 
    } 
    // Move to the right node. 
    else if (keyCompare > 0) { 
     //printf("%s\n%s", currentKey, key); 
     // If right node is empty, create a new node. 
     if (node->right == NULL) { 
      tree_ptr newPtr = malloc(sizeof(tree_ptr)); 
      newPtr->element = key; 
      newPtr->left = NULL; 
      newPtr->right = NULL; 
      node->right = newPtr; 
     } else { 
      insert_again(key, node->right); 
     } 
    } 
} 

Table insert(Key_Type key, Table table) { 
    // if it's a new tree. 
    if (table->head == NULL) { 
     tree_ptr headPtr = malloc(sizeof(tree_ptr)); 
     headPtr->element = key; 
     headPtr->left = NULL; 
     headPtr->right = NULL; 
     table->head = headPtr; 
     //printf("%s", table->head->element); 
    } 
    // if the tree already exists 
    else { 
     //printf("%s", table->head->element); 
     insert_again(key, table->head); 
    } 
    //printf("%s", table->head->element); 
    return table; 
} 

Boolean find_key(Key_Type key, tree_ptr node) { 
    Key_Type currentKey = node->element; 
    int keyCompare = strcmp(key, currentKey); 
    if (node != NULL) { 
     if (keyCompare == 0) { 
      return TRUE; 
     } else 
     if (keyCompare == -1) { 
      return find_key(key, node->left); 
     } else { 
      return find_key(key, node->right); 
     } 
    } else { 
     return FALSE; 
    } 
} 

Boolean find(Key_Type key, Table table) { 
    return find_key(key, table->head); 
} 

void print_tree(tree_ptr node) { 
    if (node == NULL) { 
     return; 
    } 
    print_tree(node->left); 
    printf("%s\n", node->element); 
    print_tree(node->right); 
} 

void print_table(Table table) { 
    print_tree(table->head); 
} 

void print_stats(Table table) { 
} 

Answer 1

Вы должны найти пустой дочерний узел, чтобы вставить новый узел в дерево. Используйте указатель на указатель, чтобы заметить пустой дочерний узел. Кроме того, вы должны выделить память для sizeof(struct node), а не для sizof(struct node*), как и вы. Что касается кода, который я вижу, этот тип Key_Type равен char*. Поэтому для сравнения ключей вам необходимо использовать strcmp, и вам нужно выделить память и скопировать ключ в узел.

Boolean insert(Key_Type key, Table table) 
{ 
    tree_ptr *ppNode = &(table->head); // pointer to pointer to node (struct node **) 
    while (ppNode != NULL) 
    { 
     int keyCompare = strcmp(key, (*ppNode)->element); 
     if (keyCompare == 0) 
      return FALSE; // element with key is already member of tree 

     if (keyCompare < 0) 
      ppNode = &((*ppNode)->left); // go to left child 
     else 
      ppNode = &((*ppNode)->right); // go to right child 
    } 

    // now ppNode is either a pointer to an empty child pointer, 
    // or to table->head if the tree is empty 

    *ppNode = malloc(sizeof(struct node)); // allocate new node right to target 
    (*ppNode)->left = NULL; 
    (*ppNode)->right = NULL; 
    (*ppNode)->element = malloc(strlen(key) + 1); 
    strcpy((*ppNode)->element, key); 

    return TRUE; // new node added successfully 
} 

найти узел с key похож найти пустой указатель cjhild:

Boolean find_key(Key_Type key, Table table) 
{ 
    tree_ptr pNode = table->head; 
    while (ppNode != NULL) 
    { 
     int keyCompare = strcmp(key, pNode->element); 
     if (keyCompare == 0) 
      return TRUE; // element with key was found 

     if (keyCompare < 0) 
      pNode = pNode->left; // go to left child 
     else 
      pNode = pNode->right; // go to right child 
    } 
    return FALSE; // key is not member of tree 
}