Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [c++] двоичное -> многомерное дерево 
:(
    Опции темы
KpoHyc
Дата 21.1.2007, 15:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 1
Всего: 5
Есть класс для бинарного дерева, - нужно передалать его в многомерное дерево и немного исправить вывод.

допустим:
       (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); 
}


Это сообщение отредактировал(а) KpoHyc - 22.1.2007, 11:13
--------------------
AScript + Pascal + C -> C++ ->C#Adobe Photoshop 7.0/CS 2.0 + GIMP+ Visual Studio .NET(sp1)/2005 pro(sp1)
PM MAIL ICQ Skype GTalk Jabber   Вверх
PoloS
Дата 21.1.2007, 16:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 89
Регистрация: 29.12.2006
Где: МО, г. Одинцово

Репутация: 4
Всего: 5
Цитата(KpoHyc @ 21.1.2007,  15:24)

Нужно чтобы вывело:

1
    2
         5
         6
    /2
    3
    4
/1

 какое дерево, когда ты написал класс работы с двусвязным списком  smile 

или я не могу разобратся в твоей реализации...
PM MAIL ICQ   Вверх
KpoHyc
Дата 21.1.2007, 20:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

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


--------------------
AScript + Pascal + C -> C++ ->C#Adobe Photoshop 7.0/CS 2.0 + GIMP+ Visual Studio .NET(sp1)/2005 pro(sp1)
PM MAIL ICQ Skype GTalk Jabber   Вверх
PoloS
Дата 21.1.2007, 20:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 89
Регистрация: 29.12.2006
Где: МО, г. Одинцово

Репутация: 4
Всего: 5
смотрим... 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		Модератор: не забывайте указывать тип подсветки.


Это сообщение отредактировал(а) Alexeis - 24.1.2007, 10:23
PM MAIL ICQ   Вверх
KpoHyc
Дата 21.1.2007, 22:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 1
Всего: 5
PoloS, читай все таки внимательней...я прошу передалать а не объяснить что там...
--------------------
AScript + Pascal + C -> C++ ->C#Adobe Photoshop 7.0/CS 2.0 + GIMP+ Visual Studio .NET(sp1)/2005 pro(sp1)
PM MAIL ICQ Skype GTalk Jabber   Вверх
V.A.KeRneL
  Дата 22.1.2007, 10:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Vadim A. Kazantsev
**


Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: 7
Всего: 14
Цитата(KpoHyc @  21.1.2007, 22:15 Найти цитируемый пост)

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

Оно конечно, но...
Цитата(KpoHyc @  21.1.2007, 15:24 Найти цитируемый пост)

Есть класс для бинарного дерева

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



--------------------
«C'est un pense-creux d'ici. C'est le meilleur et le plus irascible homme du monde...» © Ф.М. Достоевский, «Бесы»
---/)/)---(\.../)---(\(\
--(':'=)---(=';'=)---(=':')
(")(")..)-(").--.(")-(..(")(")
PM MAIL IM ICQ AOL YIM MSN   Вверх
KpoHyc
Дата 22.1.2007, 11:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: 1
Всего: 5
V.A.KeRneL, таГ легче? (испрвил код верхний). Извиняюсь - и в правду накосячил в коде smile но при исправлении какая разница в этом?  smile 
--------------------
AScript + Pascal + C -> C++ ->C#Adobe Photoshop 7.0/CS 2.0 + GIMP+ Visual Studio .NET(sp1)/2005 pro(sp1)
PM MAIL ICQ Skype GTalk Jabber   Вверх
PoloS
Дата 22.1.2007, 21:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 89
Регистрация: 29.12.2006
Где: МО, г. Одинцово

Репутация: 4
Всего: 5
Завтра последний экзамен сдам и обещаю помочь с реализацией.
PM MAIL ICQ   Вверх
Alexeis
Дата 23.1.2007, 01:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Амеба
Group Icon


Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: 23
Всего: 459
PoloS, личные сообщения в ПМ пожалуйста.


--------------------
Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

гениальность идеи состоит в том, что ее невозможно придумать
PM ICQ Skype   Вверх
PoloS
Дата 23.1.2007, 17:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 89
Регистрация: 29.12.2006
Где: МО, г. Одинцово

Репутация: 4
Всего: 5
подобная проблема описана в 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



фуф...



ЗЫ. Класс не отлажен должным образом, так что не пинайте меня.

Присоединённый файл ( Кол-во скачиваний: 16 )
Присоединённый файл  _______.JPG 75,52 Kb
PM MAIL ICQ   Вверх
PoloS
Дата 24.1.2007, 09:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 89
Регистрация: 29.12.2006
Где: МО, г. Одинцово

Репутация: 4
Всего: 5
KpoHyc, тебе уже не нужно это? smile 

нах тогда я стока лопатил...
PM MAIL ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0655 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.