Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


Бинарное дерево

Поиск:
Код

//////////////////////////////////////////////////////////////////////////////
//
//  Dynamic structures (binary tree)
//  (c) Johna Smith, 1996
//
//  Method description:
//               *
//            /     
//           *       *
//         /      /   
//        *     * *     *
//
//   From current element X left element is less than X and right element
// is greater than X. All elements in the must be different.
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <alloc.h>
#include <conio.h>
#include <math.h>

struct item
{
  int element;
  item *left;
  item *right;
};

item *tree; // base element of the list

// this function searches element in the tree and returns 0 if element wasn't
// found and 1 - if element was found, result is address of element
char Search(int element, item** result)
{
  item *p,*q;
  char found=0;

  p=tree;
  if (tree!=NULL)
  do
  {
    q=p;
    if (p->element==element) found=1;
    else
    {
      q=p;
      if (element<p->element) p=p->left;
      else p=p->right;
    }
  }
  while (!found && p!=NULL);
  *result=q;

  return found;
}

// this function adds an element to the tree
void Add(int element)
{
  item *r,*s;

  if (Search(element,&r)==0)
  {
    s=(item*)malloc(sizeof(item));
    s->element=element;
    s->left=NULL;
    s->right=NULL;
    if (tree==NULL) tree=s; // if tree is empty make s=top of the tree
    else
    {
      if (element<r->element) r->left=s;
      else r->right=s;
    }
  }
}

// this is auxulary function for Remove procedure
void Del(item **r, item **q)
{
  item *tmp;

  if ((*r)->right==NULL)
  {
    (*q)->element=(*r)->element;
    *q=*r;
    *r=(*r)->left;
  }
  else Del(&((*r)->right),q);
}

// this function removes element with value 'element' from the tree
void Remove(int element, item **d)
{
  item *q;

  if (*d==NULL)
  printf("There is not element %d in the tree.n",element);
  else
  if (element<(*d)->element) Remove(element, &((*d)->left)); else
  if (element>(*d)->element) Remove(element, &((*d)->right)); else
  {
    // element found
    q=*d;
    if (q->right==NULL) *d=q->left; else
    if (q->left==NULL) *d=q->right; else
    Del(&(q->left),&q);
    free(q);
  }
}

// this function prints the tree
void printtree(item *t, int offset=40, int depth=2)
{
  gotoxy(offset,depth);
  cprintf("%d",t->element);
  if (t->left!=NULL) printtree(t->left,offset-pow(2,6-depth),depth+1);
  if (t->right!=NULL) printtree(t->right,offset+pow(2,6-depth),depth+1);
}

void main(void)
{
  item *tmp;

  // creating tree
  Add(100);
  Add(20);
  Add(120);
  Add(15);
  Add(50);
  Add(130);
  Add(30);
  Add(55);
  Add(28);
  Add(35);
  Add(60);
  Add(33);

  // printing tree
  clrscr();
  printf("Press a key to delete element 50...n");
  printtree(tree);
  getch();
  clrscr();
  Remove(50,&tree);
  printtree(tree);
  gotoxy(1,20);
  // searching
  cprintf("Element 20 is%s found",(Search(20,&tmp)?"":"n't"));
  printf("nElement 25 is%s foundn",(Search(25,&tmp)?"":"n't"));
  // removing all elements
  Remove(100,&tree);
  Remove(20,&tree);
  Remove(120,&tree);
  Remove(15,&tree);
  Remove(35,&tree);
  Remove(130,&tree);
  Remove(30,&tree);
  Remove(55,&tree);
  Remove(28,&tree);
  Remove(33,&tree);
  Remove(60,&tree);
}
Сайт: forum.vingrad.ru






Просмотров: 2413

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную