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

@bootleanC · Регистрация: 28.04.2009

Студворк — интернет-сервис помощи студентам

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

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

Размер: 14.7 Кб

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

Размер: 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 · 06.11.2012, 20:57 **[ТС]**

Сообщение от bootleanC

t.pn=t.add_node(mas1[i],t.pn);

когда в этой строке(51) убираешь t.pn= то вообще не запускается...хотя по идее должно быть так...или я просто что то не догоняю

@MrGrig · 07.11.2012, 00:27

Сообщение от 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 · 07.11.2012, 20:05 **[ТС]**

Сообщение от 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 · 08.11.2012, 08:19

Сообщение от 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 · 08.11.2012, 19:33 **[ТС]**

Сообщение от 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 · 08.11.2012, 19:36 **[ТС]**

@MrGrig · 08.11.2012, 21:09

Сообщение от bootleanC

возник другой вопрос: как сделать так чтобы программа вывела в строчку с начало элементы левого поддерева потом корень и потом правое поддерево?

вообще то нужно наоборот сначала правое поддерево потом корень потом левое вывечти красиво нужно так.
делаем обход с права на лево
добавляется новая переменная n которая будет показывать глубину дерева например в шапке она равна 0 в первых 2х ветках 1 во вторых 4х ветках 2. т.е. если у нас делается операция pn->left или pn->right n++, потом n--; соответственно столько раз мы печатаем символ \t а после этого выводим наш ключ/данные. и переход на новую строчку. выйдет довольно красиво

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@bootleanC 6 / 6 / 2 Регистрация: 28.04.2009 Сообщений: 106
	08.11.2012, 19:36 [ТС]
	0