Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Vashtanerada
1 / 1 / 0
Регистрация: 29.11.2012
Сообщений: 142
#1

Преобразование идельно сбалансированного дерева в дерево поиска - C++

29.05.2014, 16:26. Просмотров 677. Ответов 9
Метки нет (Все метки)

Здравствуйте, уважаемые специалисты!
Вынуждена просить у вас помощи, ибо самой справиться не получается.
Имеется задание:
1. Формирование однонаправленного списка;
2. Печать однонаправленного списка;
3. Удаление всех элементов с четными номерами;
4. Удаление однонаправленного списка из памяти;
5. Формирование двунаправленного списка;
6. Печать двунаправленного списка;
7. Добавление в список элементов с нечетными номерами;
8. Удаление двунаправленного списка из памяти;
9. Формирование идеально сбалансированного бинарного дерева;
10. Печать бинарного дерева;
11. Поиск максимального элемента в дереве;
12. Преобразовать бинарное дерево в дерево поиска;
С первого по одиннадцатое задания я благополучно выполнила, осталось преобразовать идеально сбалансированное дерево в дерево поиска.
Что такое дерево поиска я понимаю, но не могу понять как реализовать.
Знаю только, что фактически нужно сформировать новое дерево, используя значения из предыдущего.
Имеются кое какие наработки:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//Запись одного элемента
ISBD* Ferst_TT(int d)
{
    ISBD* p=new ISBD;
    p->data=d;
    p->left=0;
    p->right=0;
    return p;
}
 
ISBD* Trans_Tree(ISBD* beg, int d)
{
    ISBD* p=beg;
    ISBD* r;
//Проверяем существование элемента в дереве
    bool y=false;
    while(p&&!y)
    {
        r=p;
        if(d==p->data)
        {
            y=true;//элемент существует
        }
        else
        {
            if(d<p->data)
            {
                p=p->left;//идем в левое поддерево
            }
            else
            {
                p=p->right;//идем в правое поддерево
            }
        }
    }
        if(y)
        {
            return p;//элемет найден, не добавляем
        }
        //создание узла
        ISBD* New=new ISBD();//выделили память
        New->data=d;
        New->left=0;
        New->right=0;
        // если d<r->key, то добавляем его в левое поддерево
        //if(d<r->data)r->left=New;
        // если d>r->key, то добавляем его в правое поддерево
        //else r->right=New;
        return New;
}
Это сами функции

C++
1
2
3
4
5
6
7
8
case 12://system("cls");
        for (int i=0; i<=n; i++)
        {
            Ferst_TT(d);
            Trans_Tree(second, d);
        }
        Print_Tree(second,n);
        break;
А это, собственно попытка вызвать данные функции в main.
Ошибок не выдает, все прекрасно выводит, но выводит то же самое дерева которое имелось ранее.

Будьте добры, подскажите, что я делаю не так и как исправить сложившуюся ситуацию.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2014, 16:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Преобразование идельно сбалансированного дерева в дерево поиска (C++):

Преобразование сбалансированного дерева в дерево поиска - C++
пишу программу по примерам не могу найти как преобразовать сбалансированное дерево в дерево поиска вот пример моего кода # include...

Удаление элементов из бинарного дерева (не дерево поиска) - C++
Задание заключается в создании бинарного дерева, из букв введенной строки, обходе дерева и удалении согласных букв из дерева. проблема...

Создание и обработка сбалансированного дерева - C++
Имеется программа: #include &quot;stdafx.h&quot; #include &quot;windows.h&quot; #include &quot;stdio.h&quot; #include &quot;conio.h&quot; #include &quot;math.h&quot; ...

Алгоритм построения сбалансированного дерева - C++
Ребят очень очень нужна ваша помощь. Объясните алгоритм построения сбаланс дерева.. в инете кодов куча, но разобраться ни в одном не...

Поиск минимального элемента идеально сбалансированного дерева - C++
Как найти минимальный элемент? Вообще не представляю. зы. Дерево поиска другой разговор.

Деревья (алгоритм создания СБАЛАНСИРОВАННОГО бинарного дерева) - C++
Здравствуйте! Подскажите пожалуйста алгоритм создания СБАЛАНСИРОВАННОГО бинарного дерева. Код не нужен, просто по пунктам напишите...

9
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
29.05.2014, 16:31 #2
Я не очень понял задание. Бинарное дерево это и есть дерево поиска...
0
Vashtanerada
1 / 1 / 0
Регистрация: 29.11.2012
Сообщений: 142
29.05.2014, 17:26  [ТС] #3
возможно я не совсем верно написала в задании.
преобразование идеально сбалансированного дерева в дерево поиска

Дерево поиска является бинарным, но бинарное дерево не обязательно является деревом поиска. Если я правильно понимаю теорию.
0
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
30.05.2014, 12:32 #4
Ну в данной ситуации легче всего будет не переделвыть абы какое дерево в дерево поиска, а просто достать все элементы и построить дерево с нуля...
0
Vashtanerada
1 / 1 / 0
Регистрация: 29.11.2012
Сообщений: 142
30.05.2014, 15:24  [ТС] #5
У меня по заданию в дереве поиска должны содержаться те же элементы, что и в ранее созданном идеально сбалансированном дереве

Добавлено через 1 час 40 минут
Вот именно как достать элементы и сформировать из них дерево поиска я понять не могу
0
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
30.05.2014, 15:31 #6
Ну а можно хоть взглянуть, в каком виде хранится исходное дерево?
0
Vashtanerada
1 / 1 / 0
Регистрация: 29.11.2012
Сообщений: 142
30.05.2014, 15:36  [ТС] #7
Формируем корень дерева
C++
1
2
3
4
5
6
7
8
9
10
11
ISBD* root()
{
    int d;
    ISBD* p=new ISBD;
    cout<<"Ввелите число: ";
    cin>>d;
    p->data=d;
    p->left=0;
    p->right=0;
    return p;
}
Формирование самого дерева
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ISBD* Tree(int n,ISBD* beg)
{
    ISBD*r;
    ISBD*p;
    int k,s;
    if(n==0)
    {
        p=NULL;
        return p;
    }
    k=n/2;
    s=n-k-1;
    r=new ISBD;
    cout<<"Введите число: ";
    cin>>r->data;
    r->left=Tree(k,r->left);
    r->right=Tree(s,r->right);
    p=r;
    return p;
}
И печать
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Print_Tree(ISBD* beg, int n)
{
    ISBD *p=beg;//Начало списка
    //обход слева направо
    if(p)
    {
        Print_Tree(p->left,n+1);
        for(int i=0;i<n;i++)
        {
            cout<<"\t";
        }
        cout <<"("<< p->data <<")"<< "\n";
        Print_Tree(p->right,n+1);
    }
 
cout<<"\n\n";
}
0
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
30.05.2014, 15:42 #8
Ну обходим дерево,как когда печатаем, и кидаем в вектор все числа.
Затем делаем уже настоящее бинарное дерево
C++
1
2
3
4
5
6
7
8
9
edge* new_edge(long value)
{
    edge *a=new edge;
    a->val=value;
    a->l=NULL;
    a->r=NULL;
    a->p=NULL;
    return a;
}
шаблон чистой вершины
C++
1
2
3
4
5
6
7
8
9
edge* new_edge(long value)
{
    edge *a=new edge;
    a->val=value;
    a->l=NULL;
    a->r=NULL;
    a->p=NULL;
    return a;
}
Соответственно где-то в int main() создаем вершину и объявляем ее корнем.

Пишем процедуру добавления в дерево
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void ins(edge *root, edge *add)
{
    if(root->l!=NULL && root->val>add->val)
    {
        return ins(root->l,add);
    }
    else
    if(root->r!=NULL && root->val<add->val)
    {
         return ins(root->r,add);
    }
    else if(root->val>add->val)
    {
        root->l=add;
        add->p=root;
    }
    else
    {
        root->r=add;
        add->p=root;
    }
 
 
}
А потом просто в int main() по очереди вызываем добавление каждого элемента вектора в дерево
0
Vashtanerada
1 / 1 / 0
Регистрация: 29.11.2012
Сообщений: 142
30.05.2014, 17:47  [ТС] #9
Пытаюсь записать числа в массив, проходя от корня, получается что-то такое:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ISBD* Run(ISBD* p)
// left ->right
{
    if (p)
    {
        Run(p->left);
        Run(p->right);
    }
    return p;
}
void MASS(ISBD*beg,int n)
{
    ISBD* p=beg;
    int mas[n];
    if(p)
    {
        for (int i=0; i<=n; i++)
        {
            mas[i]=p->data;
            Run(p->left);
            Run(p->right);
        }
    }
    for (int i=0; i<=n; i++)
    {
        cout<<mas[i]<<"\t";
    }
}
Но что-то я делаю неправильно, он у меня выводит только первый элемент
Подскажите в чем моя беда
0
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
30.05.2014, 20:18 #10
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<long> ans;
ISBD* Run(ISBD* p)
{
    ans.push_back(p->data)
    if (p->left)
    {
        run(p->left);
    }
    if(p->right)
    {
        run(p->right);
    }
    
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.05.2014, 20:18
Привет! Вот еще темы с ответами:

Построение идеально сбалансированного дерева, значения читаются из текстового файла - C++
Разработать программу построения идеально сбалансированного дерева, элементами которого являются целые числа, которые читаются из...

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой - C++
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру - C++
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру. вот...

Бинарное Дерево(обход дерева) - C++
добрый вечер всем!) в универе задали написать бинарное дерево со всеми видами обхода и т.п. я их написал.. но еще дали 1 вывод его надо...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Yandex
Объявления
30.05.2014, 20:18
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru