VPF::Деревья - Форум программистов

Romfkn

Дата 10.5.2008, 14:18 (ссылка)

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

Загрузка ...

Новичок

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

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

Помогите пожалуйста доделать задачку.
Мне нужно вывести массив всех листов дерева.Опрос я написал, а дальше что-то туплю.
Вот код

Код



#include <stdio.h>
#include <conio.h>
#include<windows.h>
char* rus(const char* text);

struct PNode{ //описание структуры
       int metka; //метка целое число
       PNode *leftmchild; //указатель на левого сына
       PNode *rightsibling; //указатель на правого брата
};

PNode *Tree; //указатель на дерево
int count;


//рекурсивная процедура создания дерева
void createTree(PNode *T, int t, int p, int kolvo)
//передаем поддерево,текущего сына, родителя, кол-во сыновей
{
     int name,kol;
     //Ввод данных
     printf(rus("Введите метку для %d сына %d узла: "),t,p);
     scanf("%d",&name);
     printf(rus("Введите колличество сыновей для %d : "),name);
     scanf("%d",&kol);
     T->metka=name;//запись метки
     if (kol==0) T->leftmchild=NULL; else//если нет сыновей
     {
     T->leftmchild=new PNode();//выделение памяти
     createTree(T->leftmchild,1,name,kol);//вызов создания поддерева
     }
     if (t+1>kolvo) T->rightsibling=NULL; else//создание братьев
     {
     T->rightsibling=new PNode();//выделение памяти
     createTree(T->rightsibling,t+1,p,kolvo);//создание узлов
     }
}

//поиск родителя по номеру в обходе,  p-текущий родитель
int Parent(int n,PNode *T,int p)
{
 if (T==NULL) return 0; else//если пустое дерево-выход
 if (count==n) return p;//если совпадет-возврат текущего родителя
 count++;

 int t=Parent(n,T->leftmchild,T->metka);//поиск в поддереве
 if (t>0) return t;//если успешно-выход

 int q=Parent(n,T->rightsibling,p);//поиск в поддеревьях братьях
 if (q>0) return q;//если успешно-выход

 return 0;
}

int Leftmostchild(int n,PNode *T)
{
 if (T==NULL) return 0; else//если пустое дерево-выход
 if (count==n)//если номер совпал
 {
   if (T->leftmchild!=NULL) return T->leftmchild->metka; else//возврат метки
   return 0;
 }
 count++;

   int t=Leftmostchild(n,T->leftmchild);
   if (t>0) return t;//если успешно-выход

   int q=Leftmostchild(n,T->rightsibling);
   if (q>0) return q;//если успешно-выход

 return 0;
}

int Rightsibling(int n,PNode *T)
{
 if (T==NULL) return 0; else//если пустое дерево-выход
 if (count==n)
 {
   if (T->rightsibling!=NULL) return T->rightsibling->metka; else//возврат метки
   return 0;
 }
 count++;
   int t=Rightsibling(n,T->leftmchild);
   if (t>0) return t;//если успешно-выход

   int q=Rightsibling(n,T->rightsibling);
   if (q>0) return q;//если успешно-выход
 return 0;

}




}   

int main()
{    printf(rus("\t\tПрограмма №1\t\t\n"));
     printf(rus("Данная программа составляет массив всех листов дерева\n"));
     printf(rus("\t\t\t\tавтор: Роман Новиков СВ-701\n\n"));
     printf(rus("Создание дерева\n"));
     printf(rus("Введите метку корня: "));
     int name,kol;
     scanf("%d",&name);
     printf(rus("Введите количество сыновей для корня : "));
     scanf("%d",&kol);
     Tree=new PNode();//создание корня
     Tree->metka=name;
     Tree->rightsibling=NULL;//правых братьев нет
     Tree->leftmchild=new PNode();//выделяем память
     createTree(Tree->leftmchild,1,name,kol);//строим дерево


     return 0;
}
 char bufrus[256];
        char* rus(const char* text){
        CharToOem(text, bufrus);
        return bufrus;
        }

jonie

Дата 11.5.2008, 13:18 (ссылка)

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

Загрузка ...

Эксперт

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

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

печать дерева всего делается например так :

Код


void printAZ(PNode lproot){
    if(lproot){
        printAZ(lproot->leftmchild);
        std::cout<<lproot->metka<<' ';
        printAZ(lproot->rightsibling);
    }
}

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

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

Romfkn

Дата 11.5.2008, 14:17 (ссылка)

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

Загрузка ...

Новичок

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

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

немного не понял этот код.То есть будет выдана метка и ее сыновья и братья?можешь объяснить поподробнее пожалуйста

Addidas

Дата 11.5.2008, 16:35 (ссылка)

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

Загрузка ...

Новичок

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

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

Цитата(jonie @ 11.5.2008, 13:18)

печать дерева всего делается например так :

Код


void printAZ(PNode lproot){
    if(lproot){
        printAZ(lproot->leftmchild);
        std::cout<<lproot->metka<<' ';
        printAZ(lproot->rightsibling);
    }
}

вообще то это обход методом инордер.. типа лево - корень - право... так Б дерево распечатается отсортированым...
а если обычная распечатка нужна то

Код


void printAZ(PNode lproot){
    if(lproot){
        printAZ(lproot->rightsibling);
        std::cout<<lproot->metka<<' ';
       printAZ(lproot->leftmchild); 
    }
}

То есть право - корень - лево...

А смысл всего этого - рекурсия... а на пальцах объяснять как работает функция которая сама себя вызывает - дико... ну я так считаю...

Это сообщение отредактировал(а) Addidas - 11.5.2008, 16:38

rrrFer

Дата 11.5.2008, 20:18 (ссылка)

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

Загрузка ...

Бывалый

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

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

а чтобы дерево выводилось деревом можно изменить:

Код


void printAZ(PNode lproot, int lev){
    if(lproot){
        printAZ(lproot->rightsibling);
        for(int i=0;i<lev;i++) std::cout<<"  ";
        std::cout<<lproot->metka<<' ';
       printAZ(lproot->leftmchild); 
    }
}

при вызове вместо printAZ(root); писать printAZ(root,0);

Это сообщение отредактировал(а) rrrFer - 11.5.2008, 20:19

Romfkn

Дата 12.5.2008, 10:59 (ссылка)

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

Загрузка ...

Новичок

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

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

спасибо за советы, разберемся

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