С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Vashtanerada
1 / 1 / 1
Регистрация: 29.11.2012
Сообщений: 143
1

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

29.05.2014, 16:26. Просмотров 870. Ответов 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
Ответы с готовыми решениями:

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

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

Сформировать бинарное дерево поиска и определить максимальную глубину дерева
Добрый день всем. По задаче необходимо сформировать бинарное дерево поиска и определить...

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

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

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

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

Добавлено через 1 час 40 минут
Вот именно как достать элементы и сформировать из них дерево поиска я понять не могу
0
grikukan
62 / 62 / 54
Регистрация: 23.09.2012
Сообщений: 212
30.05.2014, 15:31 6
Ну а можно хоть взглянуть, в каком виде хранится исходное дерево?
0
Vashtanerada
1 / 1 / 1
Регистрация: 29.11.2012
Сообщений: 143
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
62 / 62 / 54
Регистрация: 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 / 1
Регистрация: 29.11.2012
Сообщений: 143
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
62 / 62 / 54
Регистрация: 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
30.05.2014, 20:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.05.2014, 20:18

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

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

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


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

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