VPF::бинарные деревья - Форум программистов

qwee

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

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

Загрузка ...

Новичок

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

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

Здравствуйте проблемы в решении следующей задачи:назовем пару различных вершин дерева двойниками,если их значения и уровни совпадают.Найти всех двойников в данном целочисленном бинарном дереве.
написала ввод и вывод,но выводит не правильно

Код


#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <clocale>
using namespace std;
//Наша структура
struct node
{
    int d;//элементы дерева
    node *l, *r;//Левая и Правая часть дерева
};

void MakeSubTrees(node *leaf)
{
    node *Top;int key;
    cout<<"введите текущий узел";
    cin>>leaf->d;
    cout<<"он имеет левое поддерево?";
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->l=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->l=NULL;
    cout<<"он имеет правое поддерево?";
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->r=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->r=NULL;
}

void MakeTree(node **Top)
{
    (*Top)=new node;
    MakeSubTrees(*Top);
}

int High(node *Top)
{ 
    int Highleft,Highright,H;
    if (Top==NULL)
        H=0;
    else
    {
        Highleft=High(Top->l);
        Highright=High(Top->r);
        if (Highleft>Highright)
            H=Highleft+1;
        else
        H=Highright+1;
    }
    return H;
}
void WayHoriz(node *Top,int level)
{
    if (Top!=NULL)
        if (level==1)
            cout<<Top->d;
        else
        {
            WayHoriz(Top->l,level-1);
            WayHoriz(Top->r,level-1);
        }
}
void ViewTree(node Top)
{
    int i,HighTree;
    HighTree=High(&Top);
    for (int i=0;i<HighTree;i++)
    {
        WayHoriz(&Top, i);
    }
}
void main()
{
    setlocale(LC_CTYPE, "Russian");
    node *Top;
    MakeTree(&Top);
    ViewTree(*Top);
    getch();
    return;
}

feodorv

Дата 23.10.2013, 20:07 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

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

Цитата(qwee @ 23.10.2013, 19:50

)

написала ввод и вывод,но выводит не правильно

Выводит всё дерево (по-уровнево), так? Что конкретно не правильно?

Добавлено через 6 минут и 35 секунд

Цитата(qwee @ 23.10.2013, 19:50

)

void ViewTree(node Top)

Какой смысл здесь передавать не указатель на struct node?

При печати проверяется

Цитата(qwee @ 23.10.2013, 19:50

)

if (level==1)

Но ранее

Цитата(qwee @ 23.10.2013, 19:50

)

    for (int i=0;i<HighTree;i++)
    {
        WayHoriz(&Top, i);
    }

Значит, возможен вызов WayHoriz(&Top, 0) и level никогда с 1 не сравнится. Может, имелось в виду

Код


    for (int i=1;i<=HighTree;i++)
    {
        WayHoriz(&Top, i);
    }

Ну и

Цитата(qwee @ 23.10.2013, 19:50

)

Найти всех двойников в данном целочисленном бинарном дереве

в коде никак не решается...

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

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

qwee

Дата 23.10.2013, 21:13 (ссылка)

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

Загрузка ...

Новичок

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

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

если вводить к примеру числа 2,6,10,8(где 2-вершина,6-левое поддерево 2,8-правое поддерево 2,10-левое поддерево 6),то выводит 268,а должно быть:
2
68
10
(по уровню)при замене i=0,на i=1 ничего не поменялось

а найти двойников не получается...

feodorv

Дата 24.10.2013, 01:52 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

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

Цитата(qwee @ 23.10.2013, 22:13

)

а должно быть

Ну, если уровни не отделять переводом строки

Цитата(qwee @ 23.10.2013, 19:50

)

    for (int i=0;i<HighTree;i++)
    {
        WayHoriz(&Top, i);
        cout << endl;
    }

то так и должно получиться.

Цитата(qwee @ 23.10.2013, 22:13

)

при замене i=0,на i=1 ничего не поменялось

Там нужно было еще <= поставить в нужном месте, а то один уровень потерялся. Знаете что, сделайте проще. Оставьте

Цитата(qwee @ 23.10.2013, 19:50

)

for (int i=0;i<HighTree;i++)

но в WayHoriz сравнивайте level с нулём, а не с единицей:

Цитата(qwee @ 23.10.2013, 19:50

)

if (level==0)

Ввод дерева не очевиден. Вместо "он" лучше печатать значение узла:

Цитата(qwee @ 23.10.2013, 19:50

)

cout<<leaf->d<<" имеет левое поддерево? ";
cin>>key;

Цитата(qwee @ 23.10.2013, 19:50

)

cout<<leaf->d<<" имеет правое поддерево? ";
cin>>key;

Ну и для красоты отделите распечатываемые значения пробелом:

Цитата(qwee @ 23.10.2013, 19:50

)

    if (Top!=NULL)
        if (level==1)
            cout<<Top->d<<" ";

А так всё путём. Осталось

Цитата(qwee @ 23.10.2013, 22:13

)

найти двойников

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

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

qwee

Дата 28.10.2013, 19:40 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Код


//назовем пару различных вершин дерева двойниками,если их значения и уровни совпадают.найти 
//всех двойников в данном целочисленном бинарном дереве
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <clocale>
using namespace std;

struct node
{
    int d;//элементы дерева
    node *l, *r;//Левая и Правая часть дерева
};

//создание поддерева
void MakeSubTrees(node *leaf)
{
    node *Top;int key;
    cout<<"введите текущий узел"<<endl;
    cin>>leaf->d;
    cout<<leaf->d<<" имеет левое поддерево?"<<endl;
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->l=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->l=NULL;
    cout<<leaf->d<<" имеет правое поддерево?"<<endl;
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->r=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->r=NULL;
}

//создание дерева
void MakeTree(node **Top)
{
    (*Top)=new node;
    MakeSubTrees(*Top);
}

void ViewTree(node *Top,int level)
{
    if (Top){
        ViewTree(Top->l,level+1);
        for (int i=0;i<level;i++)
            cout<<"   ";
        cout<<Top->d<<endl;
        ViewTree(Top->r,level+1);
    }
}

void main()
{
    setlocale(LC_CTYPE, "Russian");
    node *Top;
    MakeTree(&Top);
    ViewTree(Top,0);
    getch();
    return;
}

qwee

Дата 12.11.2013, 18:23 (ссылка)

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

Загрузка ...

Новичок

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

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

вот сделала прямой обход дерева

Код


void WayUpDown(node *Top)
{ 
    if (Top==NULL)
        return;
    cout<<Top->d;
    WayUpDown(Top->l);
    WayUpDown(Top->r);
}

а как дальше?(подсказали,что нужно взять какую-то вершину k с L уровня и перебирать дерево с корня до этого уровня L,затем если k==ai, то выводим пару двойников)

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