Создание бинарного дерева поиска

#ifndef CMAP_H
#define CMAP_H
 
/*
   Модуль структуры вида "словарь" на языке Си.
   Для использования данного модуля НЕОБХОДИМО в файле определения(cmap.c)
   ОБЯЗАТЕЛЬНО задать функцию, сравнивающую ключи и значение(инициализировать
   указатели keyCompareFunc и valueComapareFunc).
   При этом пользовательская функция должна возвращать отрицательное значение,
   если первый аргумент меньше второго, положительное значение, если первый аргумент
   больше второго и должна возвращать 0 в случае равенства двух аргументов
 */
 
#include <stdio.h>
 
struct Map; // опережающее объявление
 
typedef int TKey;   // тип ключа
typedef const char * TValue; // тип значения
 
typedef int (*keyCompareFuncPointer)(TKey, TKey); // указатель на функцию сравнения ключей
//typedef int (*valueComapareFuncPointer) (TValue, TValue); // // указатель на функцию сравнения значения
typedef void (*outNodeFuncPointer) (struct Map *);
 
struct Map
{
   TKey key;
   TValue value;
};
 
struct Node
{
   struct Map map;
   struct Node *left;  // левое поддерево (для меньших значений)
   struct Node *right; // правое поддерево (для бОльших значений)
};
 
/* cmap_has_key() проверяет имеется ли в словаре ключ key
   в случае отсутствия такового возвращает NULL,
   иначе структуру Map, содержащий искомый ключ */
struct Map * cmap_has_key(struct Node *rootNode, TKey key);
TValue cmap_get_value(TKey key);                 // возвращает значение по ключу
/* cmap_insert() вставляет в словарь новую запись.
   В случае, если ключ key уже имеется в словаре, то просто обновляется его value */
int cmap_insert(struct Node **rootNode, TKey key, TValue value);
int cmap_clear(struct Node ** const rootNode);            // очищает словарь
int cmap_empty(const struct Node * const rootNode);             // проверяет на пустоту словарь
/* удаляет элемент словаря по ключу. Возвращает 0 в случае успеха, или
   CMAP_KEY_NOT_FOUND в случае неудачи */
int cmap_delete(struct Node ** const rootNode, TKey key);
void cmap_out(struct Node *rootNode, outNodeFuncPointer outFunc);
 
enum CMAP_ERROR{
   CMAP_NULL_POINTER = 1, // если передан неверный указатель
   CMAP_KEY_NOT_FOUND,     // указанный ключ не найден
   CMAP_MEMORY_ALLOCATE_ERROR // ошибка выделения памяти
};
 
#endif // CMAP_H

#include "cmap.h"
 
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
 
int cmpInt(int a, int b)
{
   return a - b;
}
 
static
keyCompareFuncPointer keyCompareFunc = &cmpInt;
 
/*
static
valueComapareFuncPointer valueComapareFunc = &strcmp;
*/
 
// ------------------------------------------------------------
int cmap_insert(struct Node **rootNode, TKey key, TValue value)
{
   /* cmap_insert() вставляет в словарь новую запись.
   В случае, если ключ key уже имеется в словаре, то просто обновляется его value */
   if (!rootNode)
      return CMAP_NULL_POINTER;
 
   if (*rootNode == 0)
   {
      struct Node *newNode = malloc(sizeof (*newNode));
 
      newNode->map.key = key;
      newNode->map.value = value;
      newNode->left = NULL;
      newNode->right = NULL;
      // пустое дерево, новый элемент есть новый корень
      *rootNode = newNode;
   }
   else
   {
      struct Node *curNode = *rootNode; // текущий узел
      int iCmp; // хранит значение функции сравнения ключа текущего узла и ключа вставки
 
      while (1)
      {
         iCmp = keyCompareFunc(curNode->map.key, key);
 
         if (iCmp < 0)
         {
            // ключ вставки меньше ключа текущего узла
            if (curNode->left != NULL)
               curNode = curNode->left;
            else
            {
               struct Node *newNode = malloc(sizeof (*newNode));
 
               if (!newNode)
                  return CMAP_MEMORY_ALLOCATE_ERROR;
 
               newNode->map.key = key;
               newNode->map.value = value;
               newNode->left = NULL;
               newNode->right = NULL;
 
               curNode->left = newNode;
               break;
            }
         }
         else if (iCmp > 0)
         {
            // ключ вставки больше ключа текущего узла
            if (curNode->right != NULL)
               curNode = curNode->right;
            else
            {
               struct Node *newNode = malloc(sizeof (*newNode));
 
               if (!newNode)
                  return CMAP_MEMORY_ALLOCATE_ERROR;
 
               newNode->map.key = key;
               newNode->map.value = value;
               newNode->left = NULL;
               newNode->right = NULL;
 
               curNode->right = newNode;
               break;
            }
         }
         else
         {
            // ключ вставки равен ключу текущего узла. В таком случае просто обновляем значение узла
            curNode->map.value = value;
            break;
         }
      }
   }
 
   return 0;
}
// ------------------------------------------------------------
struct Map * cmap_has_key(struct Node *rootNode, TKey key)
{
   /* cmap_has_key() проверяет имеется ли в словаре ключ key
   в случае отсутствия такового возвращает NULL,
   иначе структуру Map, содержащий искомый ключ */
 
   if (!rootNode) // если словарь пуст, то мы ничего не нашли
      return NULL;
 
   struct Node *curNode = rootNode; // текущий узел
   int iCmp; // хранит результат сравнения ключа текущего узла и искомого
 
 
   while (1)
   {
      iCmp = keyCompareFunc(curNode->map.key, key);
 
      if (iCmp < 0)
      {
         if (curNode->left == NULL)
            return NULL; // ключ не найден
         else
            curNode = curNode->left;
      }
      else if (iCmp > 0)
      {
         if (curNode->right == NULL)
            return NULL; // ключ не найден
         else
            curNode = curNode->right;
      }
      else
      {
         // если мы здесь, то ключ найден
         return &curNode->map;
      }
   }
}
// ------------------------------------------------------------
int cmap_delete(struct Node ** const rootNode, TKey key)
{
   if (!(*rootNode))
      return CMAP_KEY_NOT_FOUND;
 
   struct Node *parentNode = NULL;
   struct Node *curNode = *rootNode;
   int iCmp;
 
   while (1)
   {
      iCmp = keyCompareFunc(curNode->map.key, key);
 
      if (iCmp < 0)
      {
         if (curNode->left == NULL)
            return CMAP_KEY_NOT_FOUND; // ключ не найден
         else
         {
            parentNode = curNode;
            curNode = curNode->left;
         }
      }
      else if (iCmp > 0)
      {
         if (curNode->right == NULL)
            return CMAP_KEY_NOT_FOUND; // ключ не найден
         else
         {
            parentNode = curNode;
            curNode = curNode->right;
         }
      }
      else
      {
         // если мы здесь, то ключ найден. Выходим из цикла
         break;
      }
   } // end while (1)
 
   if (!curNode->left && !curNode->right) // удаляем узел без потомков
   {
      if (!parentNode) // удаляем весь словарь
         *rootNode = NULL;
      else
      {
         if (parentNode->left == curNode)
            parentNode->left = NULL;
         else
            parentNode->right = NULL;
      }
 
      free(curNode);
   }
   else if (curNode->left && curNode->right) // если удаляемый узел содежит два потомка
   {
      struct Node *leaf = curNode->left; // для нахождения листка
      struct Node *leafParent = curNode;
      // цикл поиска листка у дерева удаляемого элемента
      while (leaf->left || leaf->right) // пока у текущего узла есть дети
      {
         leafParent = leaf;
 
         if (leaf->left)
            leaf = leaf->left;
         else
            leaf = leaf->right;
      }
 
      if (leafParent->left == leaf) // удаляем информацию о листочке у его родителя
         leafParent->left = NULL;
      else
         leafParent->right = NULL;
 
      leaf->left = curNode->left;
      leaf->right = curNode->right;
 
      if (parentNode) // если удаляем не самый корень дерева
      {
         // заменяем удаляемый элемент листком из его поддерева
         if (parentNode->left == curNode)
            parentNode->left = leaf;
         else
            parentNode->right = leaf;
      }
      else // усли удаляем самый корень дерева
      {
         *rootNode = leaf;
      }
 
      free(curNode);
   }
   else // если у удаляемого узла только один потомок
   {
      if (parentNode)
      {
         if (parentNode->left == curNode)
            parentNode->left = curNode->left ? curNode->left : curNode->right;
         else
            parentNode->right = curNode->left ? curNode->left : curNode->right;
      }
      else // удаляем самый корень дерева
      {
         *rootNode = parentNode->left = curNode->left ? curNode->left : curNode->right;
      }
 
      free(curNode);
   }
 
   return 0;
}
// ------------------------------------------------------------
int cmap_empty(const struct Node * const rootNode)
{
   return rootNode == NULL;
}
// ------------------------------------------------------------
int cmap_clear(struct Node ** const rootNode)
{
   /* Функция очистки диски. УЖАСНЕЙШАЯ реализация, как будет время надо переделать!!!!!
    */
 
   if (!rootNode)
      return CMAP_NULL_POINTER;
   while (!cmap_empty(*rootNode))
      cmap_delete(rootNode, (**rootNode).map.key);
 
   return 0;
}
// -----------------------------------------------------------
void cmap_out(struct Node *rootNode, outNodeFuncPointer outFunc)
{
   // ужаснейщая реализация. Необходимо задействовать структуру типа стэка
   // вместо рекурсии
   if (!rootNode)
      return;
 
   if (rootNode->left)
      cmap_out(rootNode->left, outFunc);
 
   outFunc(&rootNode->map);
   printf("\n");
 
   if (rootNode->right)
      cmap_out(rootNode->right, outFunc);
}
// -----------------------------------------------------------