Работа с двоичными деревьями: построение, поиск, удаление, включение и обход

int bin_insert(struct bin_tree *tree, int item)

{

  struct bin_node *node, **new; 

  assert(tree != NULL);

  new = &tree->root;

  node = tree->root;

  for (;;) {

    if (node == NULL) {

      node = *new = malloc(sizeof *node);

      if (node != NULL) {

      node->data = item;

      node->left = node->right = NULL;

      tree->count++;

      return 1;

      }

      else

      return 0;

    }

    else if (item == node->data)

      return 2;

    else if (item > node->data) {

      new = &node->right;

      node = node->right;

    }

    else {

      new = &node->left;

      node = node->left;

    }

  }

} 

/* Deletes any item matching ITEM from TREE.  Returns 1 if such an

   item was deleted, 0 if none was found. */

int bin_delete(struct bin_tree *tree, int item)

{

  struct bin_node **q, *z; 

  assert(tree != NULL);

  q = &tree->root;

  z = tree->root;

  for (;;) {

    if (z == NULL)

     return 0;

    else if (item == z->data)

      break;

    else if (item > z->data) {

      q = &z->right;

      z = z->right;

    }

    else {

      q = &z->left;

      z = z->left;

    }

  } 

  if (z->right == NULL)

    *q = z->left;

  else {

    struct bin_node *y = z->right;

    if (y->left == NULL) {

      y->left = z->left;

      *q = y;

    }

    else { 

      struct bin_node *x = y->left;

      while (x->left != NULL) {

      y = x;

      x = y->left;

      }

      y->left = x->right;

      x->left = z->left;

      x->right = z->right;

      *q = x;

    }

  } 

  tree->count--;

  free(z);

  return 1; 

} 

/* Helper function for bin_walk().  Recursively prints data from each

   node in tree rooted at NODE in sorted-order. */

static void walk(const struct bin_node *node,int x,int y,int offset)

{

  int x1;

  char text[4];

  if (node == NULL) return;

  if(node->data==fp) {setcolor(18);setfillstyle(11,29);}

  else

  {

    setcolor(17);

    setfillstyle(11,20);

  }

  fillellipse(x,y,13,13);

  setcolor(18);

  ltoa(node->data, text, 10);

  if(node->data>9) outtextxy(x-7,y-3,text);

  else if(node->data<0) outtextxy(x-8,y-3,text);

  else outtextxy(x-3,y-3,text);

  setcolor(19);

  if(node->left!=NULL)

  {

    x1=x-(int)offset/2;

    line(x,y+13,x-(int)offset/2,y+27);

    walk(node->left,x1,y+40,(int)offset/2);

  }

  if(node->right!=NULL) 

  {

    x1=x+(int)offset/2;

    line(x,y+13,x+(int)offset/2,y+27);

    walk(node->right,x1,y+40,(int)offset/2);

  }

} 

/* Prints all the data items in TREE. */

void bin_walk(const struct bin_tree *tree)

{

  assert(tree != NULL);

  walk(tree->root,400,74,300);

} 

/* Destroys tree rooted at NODE. */

static void destroy(struct bin_node *node)

{

  if (node == NULL)

    return;

  destroy(node->left);

  destroy(node->right);

  free(node);

} 

/* Destroys TREE. */

void bin_destroy(struct bin_tree *tree)

{

  assert(tree != NULL);

  destroy(tree->root);

  free(tree);

} 

/* Returns the number of data items in TREE. */

int bin_count(const struct bin_tree *tree)

{

  assert(tree != NULL);

  return tree->count;

} 

void Back()

{

  setrgbpalette(17,0,63,5);  //LIGHTGREEN

  setrgbpalette(18,63,0,0);  //LIGHTRED

  setrgbpalette(19,52,52,52);//WHITE

  setrgbpalette(20,0,40,5);  //GREEN 

  setrgbpalette(21,0,33,55); //BLUE1

  setrgbpalette(22,0,23,48); //BLUE2

  setrgbpalette(23,0,13,46); //BLUE3

  setrgbpalette(24,0,3,44);  //BLUE4

  setrgbpalette(25,0,3,24);  //BLUE5 

  setrgbpalette(26,63,63,0); //YELLOW

  setrgbpalette(27,20,20,20);//LIGHTGREY1

  setrgbpalette(30,27,27,27);//LIGHTGREY2

  setrgbpalette(31,17,17,17);//LIGHTGREY3

  setrgbpalette(28,0,0,0);   //BLACK

  setrgbpalette(29,43,13,0); //RED 

  setcolor(21);

   line(0,0,800,0);line(0,0,0,600);line(799,0,799,600);

   line(5,110,210,110);line(585,110,795,110);

   line(210,54,210,113);line(585,54,585,113);

   line(210,54,585,54);

  setcolor(22);

   line(1,1,799,1);line(1,1,1,599);line(798,1,798,599);

   line(5,111,210,111);line(585,111,795,111);

   line(211,55,211,113);line(584,55,584,113);

   line(211,55,584,55);

  setcolor(23);

   line(2,2,798,2);line(2,2,2,598);line(797,2,797,598);

   line(5,112,210,112);line(585,112,795,112);

   line(212,56,212,113);line(583,56,583,113);

   line(212,56,583,56);

  setcolor(24);

   line(3,3,797,3);line(3,3,3,597);line(796,3,796,697);

   line(5,113,210,113);line(585,113,795,113);

   line(213,57,213,113);line(582,57,582,113);

   line(213,57,582,57);

  setcolor(25);

   line(4,4,796,4);line(4,4,4,596);line(795,4,795,696);

   line(5,114,210,114);line(585,114,795,114);

   line(214,58,214,113);line(581,58,581,113);

   line(214,58,581,58); 

  setcolor(26);

  showbmp16x(5,5,"c:\\nbutton_.bmp",0,1,0);

   outtextxy(54,27,"F1 - Справка");

  showbmp16x(5,53,"c:\\ybutton_.bmp",0,1,0);

   outtextxy(54,75,"F2 - О программе");

  showbmp16x(748,5,"c:\\nbutton_.bmp",0,1,0);

   outtextxy(660,27,"F7 - Поиск");

  showbmp16x(748,53,"c:\\ybutton_.bmp",0,1,0);

   outtextxy(660,75,"F10 - Выход");

  showbmp16x(326,5,"c:\\nbutton_.bmp",0,1,0);

   outtextxy(207,27,"Ins - Добавить");

  showbmp16x(424,5,"c:\\ybutton_.bmp",0,1,0);

   outtextxy(476,27,"Del - Удалить");

} 

void clear()

{

  setfillstyle(1,28);

  bar(216,59,579,120);

  bar(6,115,794,600);

} 

void help()

{

  setcolor(17);

  outtextxy(380,210,"Помощь");

  setcolor(21);

  writexy(120,245,"Данная  программа работает с клавиатурой  и не требует манипулятора 'мышь'. Вашему вниманию предо-");

  writexy(105,260,"ставляется  возможность работы с двоичными деревьямия.");

  setcolor(17);

  writexy(105,275,"Добавление  элемента:");setcolor(21);

  writexy(230,275,"Для  того, чтобы добавить элемент  просто нажмите клавишу Ins и  введите значение.");

  writexy(105,290,"Внимание!! Не добавляйте в дерево уже существующий элемент, т.к. программа не позволит сделать");

  writexy(105,305,"это  и работа будет завершена. ");

  setcolor(17);

  writexy(105,320,"Удаление  элемента:");setcolor(21);

  writexy(225,320,"Для  удаления элемента нажмите клавишу Del. Как и с добавлением не стоит пытаться");

  writexy(105,335,"удалить  не существующий элемент - все  равно ничего не получиться.");

  setcolor(17);

  writexy(105,350,"Поиск:");setcolor(21);

  writexy(150,350,"Для  поиска элемента нажмите клавишу  F7 и введите искомое. Найденный элемент будет выделен");

  writexy(105,365,"другим  цветом.");

  writexy(120,380,"Текущее  двоичное дерево выводиться автоматически  после любых операций, изменяющих  его структуру");

  writexy(105,395,"или  маркеровку.");

  writexy(120,420,"Для выхода нажмите любую клавишу.");

} 
 

void about()

{

  setcolor(17);

  outtextxy(360,310,"О программе");

  setcolor(21);

  writexy(340,360,"(C) Andrew Ru SW-01b");

  writexy(320,385,"Курсовой проект по дисциплине");

  writexy(290,410,"'Структуры  и организация данных в ЭВМ'");

  writexy(300,460,"Для  выхода нажмите любую клавишу.");

} 

void bar_(int x1,int y1,int x2,int y2)

{

   setfillstyle(1,27);

   bar(x1+2,y1+2,x2-2,y2-2);

   setcolor(30);

   line(x1,y1,x2,y1);line(x1,y1,x1,y2);

   line(x1+1,y1+1,x2-1,y1+1);line(x1+1,y1+1,x1+1,y2-1);

   setcolor(31);

   line(x2,y2,x1,y2);line(x2,y2,x2,y1);

   line(x2-1,y2-1,x1+1,y2-1);line(x2-1,y2-1,x2-1,y1+1);

}

//READ STRING FROM CONSOLE

int re(int cx, int cy, char * s, int n, int xs )

  {

  int p=0, x=cx+4,y=cy+4;

  long z;

  const long mz=10000;

  char ch;

  char c[2]; 

  s[0]=0; 

  setfillstyle(1,27);

  do

    {

        if (kbhit())

          {

          setcolor(27);line(x,y-1,x,y+11);

          goto HIT;

          }

    // ------------------------

    if (0)

      {

      HIT:;

      ch=getch();

      if (!ch)

        {

        getch();

        // ---

        } // end_special

        else

        {

        if (

           (((ch>='a')&&(ch<='z'))||

            ((ch>='A')&&(ch<='Z'))||

            ((ch>='а')&&(ch<='п'))||

            ((ch>='р')&&(ch<='я'))||

            ((ch>='А')&&(ch<='Я'))||

            ((ch>=91)&&(ch<=96))||

            ((ch>=123)&&(ch<=127))||

            ((ch>=32) &&(ch<=64)))&&    // все символы + цифры

           (p<n)&&

           (slen(s)+clen(ch)<xs)