Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [c++] двоичное -> многомерное дерево

Автор: KpoHyc 21.1.2007, 15:24

Есть класс для бинарного дерева, - нужно передалать его в многомерное дерево и немного исправить вывод. допустим:        (1)     /    |   \   (2) (3)(4)   /   \ (5)(6) Нужно чтобы вывело: 1     2          5          6     /2     3     4 /1 Код #include <stdio.h> #include <stdlib.h> #include <string.h> #include <conio.h> typedef struct NODE_         {          void* data;          struct NODE_* left;          struct NODE_* right;         }     NODE; typedef struct        {         NODE* root;          int count;                            }        TREE; //========================================================= TREE* CreateTree(void) {  TREE* r;  if( (r = malloc(sizeof(TREE))) == NULL)                                 return NULL;   r->root = NULL;     r->count = 0;      return r; } //========================================================= void Delete(NODE* p) {  if(p==NULL) return;  Delete(p->left);     Delete(p->right);  free(p);          } //========================================================= void DeleteTree(TREE* p) {  // Уничтожить дерево  Delete(p->root);  free(p); } //========================================================= int InsertNode(    TREE* p,                      void* item,                   int (*fcmp)(void*, void*)                                     ) {  NODE *node, **anode;  node = p->root;       anode = &p->root;    for(;;)   if(node == NULL)   {    if((node = *anode = malloc(sizeof(*node))) != NULL)    {                                  node->data = item;                   node->left = node->right = NULL;      p->count++;                          return 1;    }    else     return 0;   }   else      switch( fcmp(item, node->data) )     {      case  0: return 2;             // ничего делать не надо      case  1: anode = &node->right; // пойти направо               node = node->right;               break;      case -1: anode = &node->left;  // пойти налево               node = node->left;               break;     } } //========================================================= void WalkAndPrintStr( NODE* pnode, FILE* fp) {  if(pnode == NULL)return;  WalkAndPrintStr(pnode->left, fp);    fprintf(fp, "\n%s",  pnode->data);   WalkAndPrintStr(pnode->right, fp); } void WalkAndPrintTreeStr( TREE* ptree, FILE* fp) {  WalkAndPrintStr(ptree->root, fp); } //========================================================= void WalkAndPrintDec( NODE* pnode, FILE* fp) {  if(pnode == NULL)return;  WalkAndPrintDec(pnode->left, fp);  fprintf(fp, "\n%d",  *(int*)(pnode->data) );   WalkAndPrintDec(pnode->right, fp);  } void WalkAndPrintTreeDec( TREE* ptree, FILE* fp) {  WalkAndPrintDec(ptree->root, fp); } //========================================================= int intcmp(void* a, void* b) {  if( *(int*)a > *(int*)b )   return 1;  else   if( *(int*)a < *(int*)b )    return -1;   else    return 0; } //========================================================= int wordcmp(void* a, void* b) {  return strcmp( (char*)a,  (char*)b ); } //========================================================= void WalkAndDeleteData( NODE* pnode) {  if(pnode == NULL)return;  WalkAndDeleteData(pnode->left);    free(pnode->data);                 WalkAndDeleteData(pnode->right);  }

Автор: PoloS 21.1.2007, 16:52

Цитата(KpoHyc @ 21.1.2007,  15:24) Нужно чтобы вывело: 1     2          5          6     /2     3     4 /1  какое дерево, когда ты написал класс работы с двусвязным списком    или я не могу разобратся в твоей реализации...

Автор: KpoHyc 21.1.2007, 20:24

PoloS,  Цитата(KpoHyc @  21.1.2007,  15:24 ) Есть класс для бинарного дерева, - нужно передалать его в многомерное дерево и немного исправить вывод.

Автор: PoloS 21.1.2007, 20:38

смотрим... insert вставляет элемент в "дерево". да? Код void List::insert(int x) {     Node *n = new Node(x);   // заведем новый узел с данными     n->next = head;                // новый узел указывает на root     if (head) head->prev = n;  // а root указывает на новый узел...  } получается список какой - то с вставкой с начала... бинарное дерево, это узел должен иметь указаетель на своего родителся и на левый и правый узел, для которого он является родителем. у тебя получается head prev указывает на n, а n, в качестве следуещего элемента указывает на head....  вывод: Код void List::out() {     if (head == 0) printf("List is empty\n");     else     {         Node *n;         for (n = head; n; n = n->next)             cout << n->data << endl;     } } у бинарного дерева 2 "наследника" а ты идешь по одной ветке next... вот я и говорю что реализация напоминает двусвязный список.. M Alexeis Модератор: не забывайте указывать тип подсветки.

Автор: KpoHyc 21.1.2007, 22:15

PoloS, читай все таки внимательней...я прошу передалать а не объяснить что там...

Автор: V.A.KeRneL 22.1.2007, 10:42

Цитата(KpoHyc @  21.1.2007, 22:15 ) я прошу передалать а не объяснить что там... Оно конечно, но... Цитата(KpoHyc @  21.1.2007, 15:24 ) Есть класс для бинарного дерева Ты говоришь, что «есть класс для бинарного дерева», а приводишь класс для L2List'а (двусвязного списка), который, если рассуждать абстрактно, с точки зрения теории графов, является одинарным деревом (вырожденный случай) [с сслыками на родителей].  Извини, конечно, что объясняем тебе, вмето того, чтобы «помочь» и переписать, но тебе реально трудно помочь в сложившейся ситуации!..  Проще было бы, если бы ты просто попросил написать классы, реализующие двоичное (бинарное) и «многомерное» деревья.

Автор: KpoHyc 22.1.2007, 11:20

V.A.KeRneL, таГ легче? (испрвил код верхний). Извиняюсь - и в правду накосячил в коде  но при исправлении какая разница в этом?

Автор: PoloS 22.1.2007, 21:19

Завтра последний экзамен сдам и обещаю помочь с реализацией.

Автор: Alexeis 23.1.2007, 01:12

PoloS, личные сообщения в ПМ пожалуйста.

Автор: PoloS 23.1.2007, 17:47

подобная проблема описана в 1 томе Кнута "Искусство программирования". Вот вырезки от туда: Основные отличия деревьев от бинарных: 1) Дерево всегда имеет корень. 2) Каждый узел может иметь 0, 1, 2, 3, ... детей. Вот алгоритм "перевода" дерева в бинарное дерево (представление многомерных деревьев в виде бинарных деревьев) Пусть F = (T1, T2, ..., Tn) - некоторый лес деревьев. Тогда бинарное дерево B(F), соответствующее F, можно строго определить следующим образом: a) Если n = 0, то B(F) пусто. b) Если n > 0, то корень B(F) является корнем (T1); B(T11, T12, ..., T1m) является левым поддеревом дерева B(F), где T11, T12, ..., T1m - поддеревья корня (T1); B(T2, ..., Tn) является правым поддеревом дерева B(F). на прикрепленной картинке наглядно показано правило. я не стал переделывать твой "класс" (там структуры и функции), а написал свой параметризированный (чтобы работал с разными типами данных). Вот некоторые его ограничения: 1) дерево не может быть пустым (в узле root всегда есть данные) 2) Если удаляется узел, то автоматически удаляются все его поддеревья. 3) Значения в data не должны повторятся (иначе я не знаю что произойдет, но последствия будут это точно =) (хотя бы потому что функция удаления узла (и вставки) будет удалять первый попавшийся узел с совпавшим значением)) Код #include <iostream> #pragma once template <typename ObjType> class NTree {     typedef unsigned char BYTE;     struct Node     {             ObjType data;         Node *parent;    // предок узла         Node *left;        // левое дите  // является поддеревом узла         Node *right;    // правое дите // следующий узел на этом уровне         Node()          {             left = right = parent = NULL;         }         Node (ObjType _data, Node *_left, Node *_right, Node *_parent)         {             data =_data; left = _left; right = _right; parent = _parent;         }     }; public:     NTree(ObjType data) {root = new Node(data, 0, 0, 0);} // необходимое условие: дерево никогда не пусто          Node *root;    // корень дерева     //вставка элемента после элемента = after     bool AddAfterN (const ObjType data, const ObjType after) // no throw     {         Node *find = LookUpNode (root, after);         Node *p;         if (!find) return false;         else         {             p = find->left;             if (!p) find->left = new Node(data, 0, 0, find);             else             {                 while (p->right) p = p->right;                 p->right = new Node(data, 0, 0, p);             }         }     }     // поиск элемента прямым порядком обхода     Node* LookUpNode (Node *node, ObjType data)     {         // прямой порядок обхода         Node *p;         if (node == NULL) return NULL;         else if (node->data == data) return node;         else         {             if (p = LookUpNode(node->left, data)) return p;             else return LookUpNode(node->right, data);         }     }     bool DeleteNode (const ObjType data)     {         Node *find = LookUpNode(root, data); // ищем узел         if (!find) return false;    // если не найден, то возвращаем false         else         {             if (find == find->parent->right) find->parent->right = find->right, find->right = NULL; // если правая ветка, то нужно исключить элемент из правых, не разрывая связи с последующими             else find->parent->left = NULL;             DeleteBTree(find); // удаляем поддерево         }     }     // удалить бинарное дерево     void DeleteBTree (Node *root)     {         if (!root) return;         DeleteBTree (root->left);         DeleteBTree (root->right);         delete root;     }          void PrintBTree (Node *root)     {         // прямой порядок обхода бинарного дерева         if (!root) return;         std::cout << " " << root->data;         PrintBTree(root->left);         PrintBTree(root->right);     }     public:     ~NTree(void) {DeleteBTree(root);} }; вот небольшой тест для класса: Код #include "NTree.h" NTree<int> tree(1); void main () {     tree.AddAfterN(2,1);     tree.AddAfterN(3,1);     tree.AddAfterN(4,1);     tree.AddAfterN(5,1);     tree.AddAfterN(6,4);     tree.AddAfterN(7,4);     tree.AddAfterN(8,4);     tree.AddAfterN(9,4);     int i;     tree.PrintBTree(tree.root);     std::cout << std::endl;     tree.DeleteNode(4);     tree.PrintBTree(tree.root);     std::cin >> i; } сперва образуется дерево такое                           1                        / /   \ \                       2  3   4  5                              /| |\                            6 7 8 9 в памяти хранится как такое                                                           1                             /                            2                             \                              3                               \                                4                               / \                              6   5                               \                                7                                 \                                  8                                   \                                    9 после удаления узла 4 в памяти так                           1                          /                         2                          \                           3                            \                             5 фуф... ЗЫ. Класс не отлажен должным образом, так что не пинайте меня.

Автор: PoloS 24.1.2007, 09:19

KpoHyc, тебе уже не нужно это?   нах тогда я стока лопатил...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)