VPF::[C++]Создание бинарного дерева - Форум программистов

xStorm

Дата 22.11.2007, 16:33 (ссылка)

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

Загрузка ...

Новичок

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

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

Помогите дорешать задачу, только начинаю знакомиться с деревьями, поэтому не совсем понимаю как их правильно конструировать.
0 10
00 20
  001 30
01 5
  010 6
  011 7
   0110 100
   0111 0
- Вот допустим мне дан такой файл 0 - корень со значением 10. 00 - левый сын. 01 - правый сын итд. Мне нужно что бы вы помогли мне правильно сконструировать дерево в памяти, сцепить все веточки. Я уже немного продвинулся, моя программа уже считывает индексы и данные. Осталось только дерево сконструировать из данных.

Код


// Lab2C.cpp
#include "stdafx.h"
#include "string.h"
#include "ctype.h"
#define maxline 40

//Структура, опиисывающая элемент дерева.
typedef struct STree{ 
    int data;
    char indicator[maxline];
    struct Tree *Left, *Right;
};

class CTree
{
private:
    STree* Root; //Указатель на корень дерева
    FILE *infile;
    char string[maxline];
    char StringValue[maxline];
    char indicator[maxline];
public:
    int BuildTree ();
    //void CleanTree ();

};

int CTree::BuildTree()
{
    STree *pTree;
    int Value;
    int i, j;

    if((infile=fopen("indata.txt","rt"))!=NULL)
    {
        while(fgets(string, maxline, infile)!=NULL)
        {
            //Узнаем данные и индикатор строки
            i=0; j=0;
            while(string[i]==' ' || string[i]=='\t')
            {
                i++;
            }
            if(string[i]=='0' || string[i]=='1')
            {
                do{
                    indicator[j]=string[i]; //indicator
                    j++;
                    i++;
                }while(string[i]=='0' || string[i]=='1');
            }
            j=0;
            while(string[i]==' ' || string[i]=='\t')
            {
                i++;
            }
            if(string[i]>='0' && string[i]<='9')
            {
                do{
                    StringValue[j]=string[i];
                    i++;
                    j++;
                }while(string[i]>='0' && string[i]<='9');
            }
            i=0; j=0;
          Value=atoi(StringValue);
            //Создаем дерево если оно не создано или добавляем потомков 
            if(Root==NULL)
            {
                Root = new STree;
                Root->indicator[0]='0';
                Root->data=Value;
                Root->Left=NULL;
                Root->Right=NULL;
            }else
            {
                pTree = new STree;

                
                i=0;
                while(indicator[i]=='1' || indicator[i]=='0')
                {
                    pTree->indicator[i]=indicator[i];
                    i++;
                }
                pTree->data=Value;
                pTree->Left=NULL;
                pTree->Right=NULL;
//ПОИСК ПО ДЕРЕВУ СО ВСТАВКОЙ ЭЛЕМЕНТА (ПОМОГИТЕ ОСУЩЕСТВИТЬ)
//Не получается что-то состыковать элементы дерева правильно. Помогите, по идее там
//небольшая функция должна быть.
            }
            puts(string);
        }
        return 0;
    }else
    {
        return -1;
    }
}

void main()
{
    CTree Tree;
    if(Tree.BuildTree()==0)
    {
        puts("File opened successfully");
    }else
    {
        puts("Can't open file: Invalid data, or file is not exist");
        
    }
    getch();
}

Это сообщение отредактировал(а) xStorm - 26.11.2007, 18:36

GIK

Дата 23.11.2007, 10:33 (ссылка)

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

Загрузка ...

Добрый человек

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

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

Цитата

10. 00 - левый сын. 01 - правый сын итд

т.е. ты хочешь сказать что это: 0 10 есть 01 и 10 то есть разделение какое то?

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

Математика=>пиво=> програмирование, три вещи последовательны и совместимы !!!
Программирование - это не деятельнось! Программирование - это состояние души!
Бог - самый крутой программист.

xStorm

Дата 26.11.2007, 15:25 (ссылка)

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

Загрузка ...

Новичок

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

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

Да. Сначала идет код элемента, потом его данные. Вот я постарался нарисовать

                                            О  (0)
                                          /    \
                                (00) О       О (01)
                                      /   \
                          (000) О      О (001)

(просто пример) Если элемент добавляется справа то к строке дописывается 1, если слева то 0.

0 - код конря
0 10 - значит корень со значением 10.
00 20 - значит левый сын корня со значением 20.

(ПОМОЩЬ БОЛЬШЕ НЕ НУЖНА. НАШЕЛ ЧЕЛОВЕКА КОТОРЫЙ СМОГ ПОМОЧЬ)

Это сообщение отредактировал(а) xStorm - 27.11.2007, 01:51

GIK

Дата 27.11.2007, 13:41 (ссылка)

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

Загрузка ...

Добрый человек

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

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

Прикольная логика, мне нравиться smile

Скинь код глянуть, если можно?

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

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