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

Составить поисковое дерево - C++

Восстановить пароль Регистрация
 
bootleanC
 Аватар для bootleanC
6 / 6 / 1
Регистрация: 28.04.2009
Сообщений: 106
06.11.2012, 18:30     Составить поисковое дерево #1
Короче программа должна из случайно сформированного массива mas1, составить поисковое дерево(то бишь программа должна сделать так чтобы в верху был наименьший элемент далее с ссылкой на соседние элементы вниз по уровням)вот примерно как на рисунке

Название: 9749_original.png
Просмотров: 226

Размер: 14.7 Кб
и надо как то вывести это красиво. чтобы было понятно что это дерево. либо вертикально либо горизонтально(когда самый левый это корень дерева)
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// lab2.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
 
class tree
{
 
private: struct node
    {
        int info;
        node *left, *right;
    };
public:
    node *pn;
    /*создание нового узла*/
    node *new_node(int x);
    /*добавление узла к дереву*/
    node *add_node(int x, node *pn);
    /*обход дерева в симметричном порядке*/
    void print_sim(node *pn);
    /*удаление всего дерева*/
    void del_tree(node *pn);
    tree();
    ~tree();
}t;
int _tmain(int argc, _TCHAR* argv[])
{
    const int n=18;
    int mas1[n];
    srand(static_cast<unsigned>(time(NULL)));
    mas1[0] = rand()%901+100;
    for(int i=1; i<n; ++i)
        {
            mas1[i] = rand()%901+100;
            for(int j=1; j<=i; ++j)
                topr:if(mas1[i]==mas1[i-j])
                {
                    mas1[i] = rand()%901+100;
                    goto topr;
                }
        }
    std::cout<<"Ishodnii massiv"<<'\n';
    for(int i=0; i<n; ++i)
        std::cout<<i<<"   "<<mas1[i]<<'\n';
    for(int i=0;i<n;++i)
        t.pn=t.add_node(mas1[i],t.pn);
    for(int i=0;i<n;++i)
        t.print_sim(t.pn);
 
    _getch();
    return 0;
}
tree::tree()
{
    pn=NULL;
}
tree::~tree()
{
    del_tree(pn);
}
tree::node *tree::new_node(int x)
{
    node *ptr;
    ptr=new node;
    ptr->info = x;
    ptr->left=ptr->right=NULL;
    return ptr;
}
tree::node *tree::add_node(int x,node *pn)
{
    node *ptr=pn;
    //Если дерево не существует, то созаем его.
    if(pn==NULL) return new_node(x);
    //Если добавляемое значение меньше информационного поля узла, то
    if(x<pn->info)
        add_node(x,pn->left);
    //Добавляем его в левре поддерево, иначе - в правое
    else
        add_node(x,pn->left);
    return ptr;
}
void tree::print_sim(node*pn)
{
    //Если левое поддерево существует, то обходим его.
    if(pn->left)
        print_sim(pn->left);
    std::cout<<pn->info<<" ";
    //Попадаем в корень.
    //Если существует правое поддерево, то обходим и его.
    if(pn->right)
        print_sim(pn->right);
}
void tree::del_tree(node* pn)
{
    //Если левое поддерево существует,удаляем его.
    if(pn->left)
        del_tree(pn->left);
    //Если существует правое поддерево, его тоже удаляем.
    if(pn->right)
        del_tree(pn->right);
    //Удаляем корень.
    delete pn;
}
очень прошу помочь...хотя бы помогите понять где я допускаю ошибку ведь программа выводит только первый элемент дерева...как будто происходит зацикливание
Составить поисковое дерево
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
bootleanC
 Аватар для bootleanC
6 / 6 / 1
Регистрация: 28.04.2009
Сообщений: 106
06.11.2012, 20:57  [ТС]     Составить поисковое дерево #2
Цитата Сообщение от bootleanC Посмотреть сообщение
t.pn=t.add_node(mas1[i],t.pn);
когда в этой строке(51) убираешь t.pn= то вообще не запускается...хотя по идее должно быть так...или я просто что то не догоняю
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
07.11.2012, 00:27     Составить поисковое дерево #3
Цитата Сообщение от bootleanC Посмотреть сообщение
составить поисковое дерево
Цитата Сообщение от bootleanC Посмотреть сообщение
чтобы в верху был наименьший элемент далее с ссылкой на соседние элементы вниз по уровням
рисунок сами делали? вообще в курсе что такое дерево поиска? это не то что вы нарисовали, дерево поиска есть вид упорядоченного массива отличных друг от друга ключей, от меньшего к большему, с лева на право. т.е. самый нижний левый ключ будет наименьшим, выше на ступень чуть больше, на ступень ниже с права, еще чуть выше, на 2 ступени выше еще чуть больше. максимальный элемент это нижний правый. Поиск осуществляется по ключу, на вашем рисунке я аже боюсь представить каким образом будет осуществляться поиск, особенно если учесть что ключи у вас повторяются.

Добавлено через 2 минуты
Цитата Сообщение от bootleanC Посмотреть сообщение
C++
1
2
3
4
topr:if(mas1[i]==mas1[i-j])
* * * * * * * * {
* * * * * * * * * * mas1[i] = rand()%901+100;
* * * * * * * * * * goto topr;
* * * * * * * * }
это вообще быдлокод, извиняюсь за выражение, какойто причем тут будет зацикливание ибо ни i ни j с места не сдвигаются

Добавлено через 16 минут
в мэйне же инициализации структуры вообще нет оО
Цитата Сообщение от bootleanC Посмотреть сообщение
C++
1
2
for(int i=0;i<n;++i)
* * * * t.pn=t.add_node(mas1[i],t.pn);
вы кстати почему то пихаете постояннно в левую часть дерева
Цитата Сообщение от bootleanC Посмотреть сообщение
C++
1
2
3
4
5
if(x<pn->info)
* * * * add_node(x,pn->left);
* * //Добавляем его в левре поддерево, иначе - в правое
* * else
* * * * add_node(x,pn->left);
Цитата Сообщение от bootleanC Посмотреть сообщение
C++
1
2
for(int i=0;i<n;++i)
* * * * t.print_sim(t.pn);
зачем вам цикл если у вас есть метод в котором обходятся все ветки дерева?
Цитата Сообщение от bootleanC Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
void tree::print_sim(node*pn)
{
* * //Если левое поддерево существует, то обходим его.
* * if(pn->left)
* * * * print_sim(pn->left);
* * std::cout<<pn->info<<" ";
* * //Попадаем в корень.
* * //Если существует правое поддерево, то обходим и его.
* * if(pn->right)
* * * * print_sim(pn->right);
}
Добавлено через 6 минут
Цитата Сообщение от bootleanC Посмотреть сообщение
когда в этой строке(51) убираешь t.pn= то вообще не запускается...хотя по идее должно быть так...или я просто что то не догоняю
не догоняете функция возвращает указатель на очередную ветку и её куда то нужно присваивать

Добавлено через 1 минуту
кстати отсюда и ошибка вы все время создаете листки и её присваиваете вершине, соответственно у вас вершина получается без детей

Добавлено через 21 минуту
Визуализатор красно-черного дерева
возможно поможет вам представить как все выглядит
bootleanC
 Аватар для bootleanC
6 / 6 / 1
Регистрация: 28.04.2009
Сообщений: 106
07.11.2012, 20:05  [ТС]     Составить поисковое дерево #4
Цитата Сообщение от MrGrig Посмотреть сообщение
Добавлено через 2 минуты
Сообщение от bootleanC Код C++1
2
3
4
topr:if(mas1[i]==mas1[i-j])
* * * * * * * * {
* * * * * * * * * * mas1[i] = rand()%901+100;
* * * * * * * * * * goto topr;* * * * * * * * } это вообще быдлокод, извиняюсь за выражение, какойто причем тут будет зацикливание ибо ни i ни j с места не сдвигаются
Сдесь все нормально создается массив...это условие чтобы небыло повторяющихся элементов...
C++
1
2
3
4
5
6
7
8
9
10
11
mas1[0] = rand()%901+100; 
for(int i=1; i<n; ++i)
        {
            mas1[i] = rand()%901+100;
            for(int j=1; j<=i; ++j)
                topr:if(mas1[i]==mas1[i-j])
                {
                    mas1[i] = rand()%901+100;
                    goto topr;
                }
        }
вот же полный текст заполнения массива случайными числами
Рисунок не сам рисовал. в инете первый нашел чтобы нагляднее было что такое поисковое дерево...
да я понимаю что косяков много...посмотреть и как то посоветовать с вашей точки зрения что надо тут переделать???
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
08.11.2012, 08:19     Составить поисковое дерево #5
Цитата Сообщение от bootleanC Посмотреть сообщение
C++
1
goto topr;
использование этого оператора это 95% то что программист что-то криво сделал и вставил костыль.
и вообще использование его является по большей части плохим тоном, нас обычно за такое преподы линейкой по рукам били, не в прямом смысле конечно, но все же =)
далее, я вам дал подсказку что при создании вы все время вставляете элементы в левую часть будь то она больше или меньше предыдущей это раз

Цитата Сообщение от bootleanC Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
tree::node *tree::add_node(int x,node *pn)
{
* * node *ptr=pn;
* * //Если дерево не существует, то созаем его.
* * if(pn==NULL) return new_node(x);
* * //Если добавляемое значение меньше информационного поля узла, то
* * if(x<pn->info)
* * * * add_node(x,pn->left);
* * //Добавляем его в левре поддерево, иначе - в правое
* * else
* * * * add_node(x,pn->left);
* * return ptr;
}
увидел где ваша инициализация идет
Цитата Сообщение от bootleanC Посмотреть сообщение
C++
1
}t;
так делать плохо, просто ; ставите в мэйне прописываете вот это

C++
1
2
3
tree t;
//или 
tree *t=new tree;
будет опять же правильнее в смысле хорошего тона программирования
еще одна подсказка
Цитата Сообщение от MrGrig Посмотреть сообщение
вы все время создаете листки и её присваиваете вершине, соответственно у вас вершина получается без детей
у вас получается при создании очередного листка все что создано было ранее теряется

Добавлено через 13 минут
добавление нового листка лучше делать функцией типа bool.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool add(node* pn, int key, int data){ //где key это оригинальный ключ по которому вы вставляете, а data значение которое нужно вставить
    if(pn->key==key){
        cout<<"Ключ уже есть в дереве вставка невозможна";
        return false;
    }
    if(pn!=NULL)
        if(pn->key>key)
            add(pn->right,key,data);
        else
            add(pn->left,key,data);
    else{
        pn->key=key;
        pn->data=data;
        pn->left=pn->right=NULL;
        return true;
    }
}
Добавлено через 2 минуты
Цитата Сообщение от bootleanC Посмотреть сообщение
C++
1
2
3
4
private: struct node{
    int info;
    node *left, *right;
};
соответственно структура должна быть такая
C++
1
2
3
4
5
private: struct node{
    int key;
    int data;
    node *left, *right;
};
bootleanC
 Аватар для bootleanC
6 / 6 / 1
Регистрация: 28.04.2009
Сообщений: 106
08.11.2012, 19:33  [ТС]     Составить поисковое дерево #6
Цитата Сообщение от MrGrig Посмотреть сообщение
Сообщение от bootleanC Код C++1
goto topr; использование этого оператора это 95% то что программист что-то криво сделал и вставил костыль.
и вообще использование его является по большей части плохим тоном, нас обычно за такое преподы линейкой по рукам били, не в прямом смысле конечно, но все же =)
а как сделать более правильнее чтобы массив генерировался автоматически (трехзначные числа) и при этом не было повторений?

Добавлено через 54 минуты
Вот решил сделать по другому немного но теперь ругается на root в 38 и 39 строке
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// lab2.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
 
struct Node{
    int d;
    Node *left;
    Node *right;
};
Node * first(int d);
Node * search_insert(Node *root, int d);
void print_tree(Node *root, int l);
//-----------------------------------------------------
int _tmain(int argc, _TCHAR* argv[])
{
    const int n=18;
    int mas1[n];
    srand(static_cast<unsigned>(time(NULL)));
    mas1[0] = rand()%901+100;
    for(int i=1; i<n; ++i)
        {
            mas1[i] = rand()%901+100;
            for(int j=1; j<=i; ++j)
                topr:if(mas1[i]==mas1[i-j])
                {
                    mas1[i] = rand()%901+100;
                    goto topr;
                }
        }
    std::cout<<"Ishodnii massiv"<<'\n';
    for(int i=0; i<n; ++i)
        std::cout<<i<<"   "<<mas1[i]<<'\n';
    for(int i=0;i<n;++i)search_insert(root,mas1[i]);
    print_tree(root,0);
    _getch();
    return 0;
}
//------------------------------------------------------
//Формирование первого элемента дерева
Node * first(int d){
    Node *pv = new Node;
    pv->d = d;
    pv->left = 0;
    pv->right = 0;
    return pv;
}
//------------------------------------------------------
//Поиск с выключением
Node * search_insert(Node *root, int d){
    Node *pv = root, *prev;
    bool found = false;
    while(pv && !found){
        prev = pv;
        if (d == pv->d) found = true;
        else if(d < pv->d) pv = pv->left;
        else pv = pv->right;
    }
    if(found) return pv;
    //Создание нового узла:
    Node *pnew = new Node;
    pnew->d = d;
    pnew->left = 0;
    pnew->right = 0;
    if(d < prev->d)
        //Присоединение к левому поддереву предка:
        prev->left = pnew;
    else
        //Присоединение к правому поддереву предка:
        prev->right = pnew;
    return pnew;
}
//------------------------------------------------------
//Обход дерева
void print_tree(Node *p, int level){
    if(p){
        print_tree(p->left,level + 1);        // вывод левого поддерева
        for(int i = 0;i<level;++i) std::cout <<"   ";
        std::cout << p->d <<std::endl;                  //вывод корня поддерева
        print_tree(p->right, level + 1);      //вывод правого поддерева
    }
}
Добавлено через 48 минут
все сделал забыл строчку перед циклом добавить в майн
C++
1
    Node *root =first(mas1[0]);
Добавлено через 18 минут
возник другой вопрос: как сделать так чтобы программа вывела в строчку с начало элементы левого поддерева потом корень и потом правое поддерево?
bootleanC
 Аватар для bootleanC
6 / 6 / 1
Регистрация: 28.04.2009
Сообщений: 106
08.11.2012, 19:36  [ТС]     Составить поисковое дерево #7
Составить поисковое дерево
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2012, 21:09     Составить поисковое дерево
Еще ссылки по теме:

C++ Составить дерево из списка отцов и детей.
Из сыновей, для каждого из которых известен отец, составить бинарное дерево C++
C++ Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру

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

Или воспользуйтесь поиском по форуму:
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
08.11.2012, 21:09     Составить поисковое дерево #8
Цитата Сообщение от bootleanC Посмотреть сообщение
возник другой вопрос: как сделать так чтобы программа вывела в строчку с начало элементы левого поддерева потом корень и потом правое поддерево?
вообще то нужно наоборот сначала правое поддерево потом корень потом левое вывечти красиво нужно так.
делаем обход с права на лево
добавляется новая переменная n которая будет показывать глубину дерева например в шапке она равна 0 в первых 2х ветках 1 во вторых 4х ветках 2. т.е. если у нас делается операция pn->left или pn->right n++, потом n--; соответственно столько раз мы печатаем символ \t а после этого выводим наш ключ/данные. и переход на новую строчку. выйдет довольно красиво
Yandex
Объявления
08.11.2012, 21:09     Составить поисковое дерево
Ответ Создать тему
Опции темы

Текущее время: 15:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru