14.4 Основные операции

Основные операции для двоичного дерева следующие:

1. найти элемент с заданным ключом в дереве;
2. записать в дерево новый элемент;
3. удалить из дерева заданный элемент;
4. операции навигации в дереве;
5. операции инициализации.

Рассмотрим программную реализацию функций для работы с двоичным деревом.

1. Функция инициализации
   void InitBinaryTree(BinaryTree *tree)
   {
         tree->root=NULL; //корень дерева отсутствует
         tree->size=0; //количество узлов равно нулю
   }
2. Функция создания узла дерева, используется функция malloc из alloc.h. На входе функции указатель на блок памяти, хранящий данные.
   Node* CreateNode(void *data)
   {
         Node *node=(Node*)malloc(sizeof(Node));
         if(node==NULL) return NULL;
         node->data=data;
         node->left= NULL;
         node->right=NULL;
         return node;
   }
3. Функция поиска заданного элемента данных в двоичном дереве. Входные параметры: адрес корня дерева или поддерева addr, указатель на функцию сравнения Compare, адрес элемента данных data, которые надо найти в дереве. Функция сравнения Compare на входе принимает два адреса для сравнения и на выходе возвращает 0, если совпали данные и не ноль, если не совпали. Если данные были найдены, то функция поиска возвращает адрес найденных данных, в противном случае NULL.
   void* FindBinaryTree(Node *addr, int (*Compare)(void *d,void *t), void *data)
   {
         if(addr==NULL) return NULL;
         int result=Compare(addr->data,data);
         if(result==0) return data; //нашли
         if(result<0) return FindBinaryTree(addr->left,Compare,data);
         return FindBinaryTree(addr->right,Compare,data);
   }
4. Функция удаления узла в двоичном дереве (не доделана) Это упражнение!!!
   void* DeleteBinaryTreeNode(Node *addr, int (*Compare)(void *d,void *t), void *data)
   {
         void* tdata;
         if(addr==NULL) return NULL;
         int result=Compare(addr->data,data);
         if(result==0) //нашли, удаляем узел
         {    
               tdata=addr->data;
               if(addr->left==addr->right){ } // это лист
               return tdata;
         }
         if(result<0) return DeleteBinaryTreeNode(addr->left,Compa
         return DeleteBinaryTreeNode(addr->right,Compare,data);
         return NULL;
   }
5. Функция добавления нового элемента в двоичное дерево. На входе функции подается корень дерева или поддерева, указатель на функцию сравнения Compare (аналогична функции поиска), адрес блока данных, указатель на счетчик элементов.
   void* AddBinaryNode(Node *addr, int (*Compare)(void *d,void *t), void *data, int *size)
   {
         int result=Compare(addr->data,data);
         if(result==0) return addr->data;
         if(result<0)
         if(addr->left!=NULL) return AddBinaryNode(addr->left,Compare
         else
         {
               addr->left=CreateNode(data);
               *size++;
               return data;
         }
         if(result>0)
               if(addr->right!=NULL) return AddBinaryNode(addr->right,Compa
               else
               {
                     addr->right=CreateNode(data);
                     *size++;
                     return data;
               }
   }
6. Функция добавления нового элемента в двоичное дерево по заданному блоку BinatyTree
   void* AddBinaryTree(BinaryTree *tree, int (*Compare)(void *d,void *t), void *data)
   {
         if(tree->root==NULL) //дерево пусто
         {
               tree->root=CreateNode(data); //создать корень
               tree->size=1;
               return data;
         }
         else //добавить в дерево
               return AddBinaryNode(tree->root,Compare,data,&tree->size);
   }
7. Левосторонний обход двоичного дерева. Функция ForEachNode на входе получает адрес текущего узла, указатель на функцию Func(void*). Рекурсивно производит обход двоичного дерева и для каждого узла вызывает функцию Func(node->data).
   void ForEachNode(Node *node,void (*Func)(void*))
   {
         if(node==NULL) return;
         ForEachNode(node->left,Func);
         Func(node->data);
         ForEachNode(node->right,Func);
   }
   Функция ForEachBinaryTree производит обход двоичного дерева для блока BinaryTree
   void ForEachBinaryTree(BinaryTree *tree, void (*Func)(void*))
   {
         ForEachNode(tree->root,Func);
   }
8. Левосторонний обход двоичного дерева. Функция ForEachNodeParam на входе получает адрес текущего узла, указатель на функцию FuncParam(void*,void*), указатель на поле параметров param. Рекурсивно производит обход двоичного дерева и для каждого узла вызывает функцию Func(node->data,param)
   void ForEachNodeParam(Node *node,void (*Func)(void*,void*),void *param)
   {
         if(node==NULL) return;
         Func(node->data,param);
         ForEachNodeParam(node->left, Func,param);
         ForEachNodeParam(node->right,Func,param);
   }
   void ForEachBinaryTreeParam(BinaryTree *tree,void (*Func)(void* param)
   {
         ForEachNodeParam(tree->root,Func,param);
   }
   
   void ForEachNodeTest(Node *node,void (*Func)(void*,int,int,int),int x0,int nx,int y)
   {
         if(node==NULL) return; 
         Func(node->data,x0,nx,y);
         ForEachNodeTest(node->left, Func,x0,nx/2,y+2);
         ForEachNodeTest(node->right,Func,x0+nx/2,nx/2,y+2);
   }
   //////////////////
   void ForEachBinaryTreeTest(BinaryTree *tree,void (*Func)(void*,int,int,int),int x0,int nx,int y)
   {
         ForEachNodeTest(tree->root,Func,x0,nx,y);
   }
   void DeleteBinaryTree(Node *addr,void (*DelObject)(void*))
   {
         if(addr==NULL) return;
         DeleteBinaryTree(addr->left,DelObject); //удалить левое поддерево
         DeleteBinaryTree(addr->right,DelObject); //удалить правое поддерево
         DelObject(addr->data); //удалить объект;
         free(addr); //удалить сам узел
   }
9. Пример организации множества строк в виде двоичного дерева. Функция создания строки символов.
   char* CreateString(char *str)
   {
         char *ptr=(char*)malloc(strlen(str)+1);
         strcpy(ptr,str);
         return ptr;
   }
   Функция сравнения строк символов
   int CompareString(void *s,void *t)
   {
         return strcmp((char*)t,(char*)s);
   }
   Функция вывода строки символов.
   void OutString(void *d)
   {
         printf("::%s\n",(char*)d);
   }
   Функция удаления строки символов.
   void DelString(void*) {; //заглушка
   /////////////////////////////////////////////////
   #define SIZEENIMAL 10
   char *Enimal[SIZEENIMAL]= { "Elehpant", "Cat", "Dog", "Bull", "Fox", "Leon", "Donkey", "Monkey", "Volf", "Mouse" };
   ///////////////
   void KruTestBinaryTree()
   {
         BinaryTree tree;
         tree.root=NULL;
         randomize();
         for(int i=0; i<10; i++)
         {
               AddBinaryTree(&tree,CompareString,Enimal[i]);
         }
         ForEachBinaryTree(&tree,OutString);
         char *ptr=(char*)FindBinaryTree(tree.root,
         CompareString,Enimal[5]);
         if(ptr!=NULL) printf("Find::%s\n",ptr);
         DeleteBinaryTree(tree.root,DelString);
         //ForEachBinaryTreeTest(&tree,OutStringTest,1,80,2);
         while(!kbhit());
   }