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

Doc_d0s

Дата 9.5.2005, 18:50 (ссылка)

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

Загрузка ...

Бывалый

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

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

Есть дерево, необходимо найти самую короткую и самую правую из самых коротких ветвей smile

))

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

Админ- это вождь Apache'й :)

_hunter

Дата 10.5.2005, 10:41 (ссылка)

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

Загрузка ...

Эксперт

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

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

ну так в чем проблема?
пишем рекурсивную функцию, в которую передается ветвь и ее смещение
и вызывай ее для всех корневых ветвей ( а она сама-себя вызовет для всех остальных )
топологию дерева сам определи

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

Tempora mutantur, et nos mutamur in illis...

Doc_d0s

Дата 10.5.2005, 16:18 (ссылка)

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

Загрузка ...

Бывалый

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

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

Да нет саму задачу я понял, вопрос в основном в терминологии, что такое ветвь?

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

Админ- это вождь Apache'й :)

_hunter

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

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

Загрузка ...

Эксперт

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

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

условная связь между двумя узлами smile

Присоединённый файл ( Кол-во скачиваний: 20 )

__________.GIF

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

Tempora mutantur, et nos mutamur in illis...

kometa_triatlon

Дата 10.5.2005, 17:26 (ссылка)

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

Загрузка ...

Опытный

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

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

Гм. По-моему не совсем. В данной задаче это последовательность листьев дерева, которые образуют ветвь. То есть, если пронумеровать листья, искомая ветвь - массив номеров листьев.

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

Всё очень просто: сказки обман,
Солнечный остров скрылся в туман,
Замков воздушных не носит земля,
Кто-то ошибся, ты или я.
--------------
Программирование - самое большое удовольствие, которое вы можете получить, будучи одетым.

Doc_d0s

Дата 15.5.2005, 17:20 (ссылка)

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

Загрузка ...

Бывалый

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

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

проблема в том, что мне надо пройти по ветви(!!!ветвь-это маршрут от корня до эл-та без потомков!!!) и посчитать кол-во пройденых элементов

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

Админ- это вождь Apache'й :)

kometa_triatlon

Дата 15.5.2005, 20:58 (ссылка)

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

Загрузка ...

Опытный

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

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

Так ты до сих пор не написал прогу? smile

Кстати, какое дерево? Бинарное?
Если да, то строим дерево, пишем функцию обхода с параметром - направлением дальнейшего движения. Если нужно найти самую правую, рекурсивно вызываем ее с параметром "вправо".
А самую короткую... Ну точно не знаю, здесь наверное поиск в ширину нужно использовать...

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

Doc_d0s

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

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

Загрузка ...

Бывалый

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

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

Да я написал, но она не работет, обходить обходит, но находит не то что надо smile

Код


#include <iostream.h>
#include <conio.h>
#include <math.h>
#include <stdio.h>

struct node
{
    int key;
    node* l,*r;
};

int sum=0,count=0,min=0;
float midarifm;

node *tree(node*p,int x);
void tree_print(node*p);
void preorder(node *t);

int main()
{
    node*root=NULL;
    FILE*f;
    char*s="C:\\in.put";
    int h;
    
    if ((f=fopen(s,"r"))!=NULL)
        {
            while(!feof(f))
            {
                fscanf(f,"%d",&h);
                root=tree(root,h);
            }
            fclose(f);
        }

        else

        {
            printf("!!!ERROR!!!\n");
            return 0;
        }
        tree_print(root);
        printf("\n");
        preorder(root);
        printf("\n");
        printf("\t\t%d %f\n",min,midarifm);

    getch();
    return 0;
}

node *tree(node*p,int x)
{
    if(p==NULL)
    {
        p= new node;
        p->key=x;
        p->l=NULL;
        p->r=NULL;
    }
    else
        if(x<p->key)
            p->l=tree(p->l,x);
        else
            p->r=tree(p->r,x);
        return p;
    
}

void tree_print(node*p)
{
    if(p!=NULL)
    {
        tree_print(p->l);
        printf("  %d",p->key);
        tree_print(p->r);
    }
}//2.01
int preorder(node *t)
{
    sum=sum+t->key;
    count++;
    printf("\n%d ",t->key);
    if(t->l==NULL && t->r==NULL && count)
    {
        if (!min)
        {
            min=count;
        }
        if (count<min)
            min=count;
        midarifm=(float)sum/(float)min;
        count=0;
        sum=0;
        getch();
    }
    if(t->l!=NULL)
            preorder(t->l);
    if(t->r!=NULL)
        preorder(t->r);
    return 0;
}

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

Админ- это вождь Apache'й :)

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