VPF::[Borland C] Бинарное дерево и его операторы

mosk0001

Дата 11.6.2007, 11:16 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 11.6.2007

Репутация: нет
Всего: нет

Добрый день!

Нужно написать программку на borland c. Оплата по вебмани. Стартовая цена 25wmz.

Задание:
Реализуйте АТД TREE (Дерево) для любого типа данных и его операторы PARENT, LEFTMOST_CHILD, RIGHT_SIBLING, LABEL, CREATE, ROOT, MAKENULL. Связное двоичное дерево задано с помощью указателей на левого и правого сыновей.

Описание операторов:
Для формирования АТД на основе математического определения дерева мы должны задать множество операторов, выполняемых над объектами типа TREE (дерево). Рассмотрим следующие операторы:
1. PARENT(n,T) возвращает родителя узла n в дереве Т. Если n является корнем, то возвращается Л. Л – нулевой узел, указывающий на то, что мы выходим за пределы дерева.
2. LEFTMOST_CHILD(n,T) возвращает самого левого сына узла n в дереве Т. Если n является листом, то возвращается Л.
3. RIGHT_SIBLING(n,T) возвращает правого брата узла n в дереве Т и значение Л если такового не существует. Для нахождения правого брата сначала находится родитель р узла n и все сыновья узла р, затем среди этих сыновей находится узел, расположенный непосредственно справа от узла n.
4. LABEL(n,T) возвращает метку узла n дерева Т. Для выполнения этой функции требуется, чтобы на узлах дерева были определены метки.
5. CREATEi(v,T1, T2,…, TI) – это обширное семейство “созидающих” функций, которые для каждого i=0,1,2,… создают новый корень r с меткой v и далее для этого корня создает i сыновей, которые становятся сыновьями поддеревьев T1, T2,…, Ti. Эти функции возвращают дерево с корнем r. Если i=0, то возвращается один узел r, который одновременно является и корнем и листом.
6. ROOT(T) возвращает узел, являющийся корнем дерева Т. Если Т – пустое дерево, то возвращается Л.
7. MAKENULL(T) Этот оператор делает дерево Т пустым деревом.

Надеюсь у кого-нибудь появится желание написать код. Можно сразу написать в личку сколько вмз smile

Это сообщение отредактировал(а) mosk0001 - 11.6.2007, 11:42

Voldemar2004

Дата 11.6.2007, 13:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1650
Регистрация: 25.12.2004

Репутация: 2
Всего: 23

Код

//////////////////////////////////////////////////////////////////////////////
//
//  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 found\n",(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);


}

взято с Vingrad

--------------------

i_i
(';')
(V)

user posted image

mosk0001

Дата 11.6.2007, 13:43 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 11.6.2007

Репутация: нет
Всего: нет

Этот исходник видел. Тогда надо из этой программы убрать search, del, remove. И добавить PARENT, LEFTMOST_CHILD, RIGHT_SIBLING, LABEL, CREATE, ROOT, MAKENULL smile

Кто напишет, тому 25 wmz.
Особенно надо функцию create, потому что понять о чём она, мой моск не в состоянии smile

mosk0001

Дата 11.6.2007, 16:10 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 11.6.2007

Репутация: нет
Всего: нет

Дам 30wmz тому кто предложит рабочий вариант таких функций. Предложение действительно ещё 6 часов. Потом сам буду кнопки нажимать. Сделать надо в течении 20 часов. Если кто надумает, отпишите в личку, чтоб я знал. Неужели никому не надо 30 баксов?
Спасибо всем за внимание!

Это сообщение отредактировал(а) mosk0001 - 11.6.2007, 16:13

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »