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

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

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

Необычная функция в бинарном дереве поиска - C++

12.12.2013, 15:55. Просмотров 370. Ответов 3
Метки нет (Все метки)

Здравствуйте, уважаемые форумчане.
Очень прошу Вашей помощи.

Задание: Реализовать структуру данных двоичное дерево поиска, реализовать функции вычисления высоты дерева, обходов дерева, вывода всех элементов которые расположены на уровне N.

Сделал всё, кроме последней функции. Помогите пожалуйста.

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <stdio.h>
#include <string.h>
#include <windows.h>
#include <conio.h>
#include <algorithm>
using namespace std;
typedef int newtp;
struct node//îïèñГ*Г*ГЁГҐ ñòðóêòóðû
{
    newtp data;
    node *left;
    node *right;
} *head=NULL;
 
int compare(newtp a,newtp b){return (int)a>(int)b?1:(int)a==(int)b?0:-1;}//ôóêöèÿ Г±Г°Г*ГўГ*ГЁГўГ*Г*ГЁГї ýëåìåГ*òîâ
 
void add(node *&t,newtp dt)//äîáГ*ГўГЁГІГј óçåë Гў äåðåâî
{
    if(t==NULL)//ñîçäГ*ВёГ¬ ГіГЅГҐГ« ГЁ äîáГ*âëÿåì ГЄ ГЄГ®Г*öó ГўГҐГІГЄГЁ
    {
        t=new node;
        t->data=dt;
        t->left=t->right=NULL;
        return ;
    }
    if(compare(t->data,dt)==1)//Г±Г°Г*ГўГ*ГЁГўГ*ГҐГ¬ äâГ* Г§Г*Г*Г·ГҐГ*ГЁГї ГЁ âûáèðГ*ГҐГ¬ ГЄ ГЄГ*êîé ГўГҐГІГЄГЁ äîáГ*ГўГЁГІГј ГЄ ëåâîé èëè ГЇГ°Г*âîé
        add(t->left,dt);
    else
        add(t->right,dt);
 
}
 
node* serch(node *t,newtp dt)//ïîèñê óçëГ*
{
    if(t==NULL) return NULL;// ГўГҐГІГЄГ* ГЇГіГ±ГІГ*
    if(compare(t->data,dt)==0) return t;
    if(compare(t->data,dt)==1)//Г±Г°Г*ГўГ*ГЁГўГ*ГҐГ¬ äâГ* Г§Г*Г*Г·ГҐГ*ГЁГї ГЁ âûáèðГ*ГҐГ¬ ГЇГ® ГЄГ*êîé ГўГҐГІГЄГЁ ïðîäîëæГ*ГІГј ïîèñê ëåâîé èëè ГЇГ°Г*âîé
        serch(t->left,dt);
    else
        serch(t->right,dt);
}
 
void clean(node *t)//ГіГ¤Г*ëèòü ГўГ±ГҐ ýëåìåГ*ГІГ» ГЁГ§ äåðåâГ*
{
    if(t==NULL)return ;
    clean(t->left);
    delete t;
    clean(t->right);
}
 
void view1(node *t)// Îáõîä â ïðÿìîì ïîðÿäêå
{
    if(t==NULL)return ;
    printf ("%d \n",(int)t->data);
    view1(t->left);
    view1(t->right);
}
 
void view2(node *t)// Ñèììåòðè÷Г*ûé îáõîä
{
    if(t==NULL)return ;
    view2(t->left);
    printf ("%d \n",(int)t->data);
    view2(t->right);
}
 
void view3(node *t)// Îáõîä Гў îáðГ*ГІГ*îì ïîðÿäêå
{
    if(t==NULL)return ;
    view3(t->left);
    view3(t->right);
    printf ("%d \n",(int)t->data);
}
 
int height(node *p)// âû÷èñëåГ*ГЁГҐ âûñîòû äåðåâГ*
{
    struct node *temp=p;
    int h1=0,h2=0;
    if(p==NULL)return(0);
    if(p->left){h1=height(p->left);}
    if(p->right){h2=height(p->right);}
    return(max(h1,h2)+1);
}
 
 
int main(int args,char *argv[])
{
    char command[10];
    int znach;
    while(1)
    {
    printf ("1) ÄîáГ*âëåГ*ГЁГҐ Г*îâîãî óçëГ*.\n2) Ïîèñê ýëåìåГ*ГІГ*.\n3) Âû÷èñëèòü âûñîòó äåðåâГ*.\n4) ГЋГ·ГЁГ±ГІГЁГІГј äåðåâî.\n5) ÏðåôèêñГ*ûé îáõîä.\n6) Г€Г*ГґГЁГЄГ±Г*ûé îáõîä.\n7) ÏîñòôèêñГ*ûé îáõîä.\n");
    printf ("Ââåäèòå êîììГ*Г*äó : \n");
    scanf("%s",command);
    printf ("\n");
        if(strcmp(command,"1")==0)
        {
            printf ("ÄîáГ*ГўГЁГІГј :\n");
            if(scanf("%d",&znach))
            {
                if(head!=NULL)
                {
                    node *t=head;
                    add(t,(int)znach);
                }
                else
                    add(head,(int)znach);
            }
        }
        else if(strcmp(command,"2")==0)
        {
            printf ("ГЌГ*éòè :\n");
            if(scanf("%d",&znach))
            {
                node *t=head;
                t=serch(t,znach);
                if(t==NULL)
                    printf ("ГЌГҐ Г*Г*éäåГ*Г®.\n");
                else
                    printf ("ГЌГ*éäåГ* ýëåìåГ*ГІ %d\n.",(int)t->data);
            }
        }
        else if(strcmp(command,"3")==0)
        {
            printf ("ÂûñîòГ* äåðåâГ* = %d\n",height(head));
        }
        else if(strcmp(command,"4")==0)
        {
            clean(head);
            head=NULL;
            printf ("ГЋГ·ГЁГ№ГҐГ*Г®!\n");
        }
        else if(strcmp(command,"5")==0)
        {
            node *t=head;
            view1(t);
        }
        else if(strcmp(command,"6")==0)
        {
            node *t=head;
            view2(t);
        }
        else if(strcmp(command,"7")==0)
        {
            node *t=head;
            view3(t);
        }
        else
        {
            printf ("ÍåèçâåñГ*Г*Гї êîììГ*Г*Г¤Г*!\n");
        }
        printf ("\nÄëÿ ïðîäîëæåГ*ГЁГї Г°Г*áîòû ïðîãðГ*ììû Г*Г*æìèòå ëþáóþ ГЄГ«Г*ГўГЁГёГі!");
        getch();
        system("cls");
    }
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2013, 15:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Необычная функция в бинарном дереве поиска (C++):

Функция поиска в бинарном дереве - C++
Я понимаю как реализовать эту функцию если в бинарном дереве хранятся обычные числа(последовательно сравниваем и двигаемся по дереву в...

Поиск ключа в бинарном дереве поиска - C++
Здравствуйте! Помогите ещё с задачками) 1.Поиск ключа в бинарном дереве поиска (точное соответствие). 2. Поиск ключа в бинарном...

Найти сумму листьев в бинарном дереве поиска - C++
Дано бинарное дерево поиска(ключи-целые числа).Найти сумму листьев. Вот мой код.Но он не работает.Скажите почему и исправьте.Спасибо ...

Функция для нахождения количества элементов в бинарном дереве - C++
Помогите написать функцию для нахождения количества элементов в бинарном дереве. реализуйте функцию итеративно и рекурсивно. #include...

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

Разобраться в бинарном дереве - C++
Нашел вот такой вариант построения бинарного дерева. Просьба прокомментировать строки кода которые выделил ниже: #include...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Black_Thorn
17 / 17 / 1
Регистрация: 06.12.2012
Сообщений: 46
12.12.2013, 18:17 #2
Попробуй ввести переменную в структуру - глубина, int deep; и заполняй ее - глубина root = 0; потом обход и вывод с определенной глубиной.
Yukimura
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 4
12.12.2013, 18:22  [ТС] #3
Я не знаю как это реализовать. Если не затруднит, исправьте исходник пожалуйста.
Заранее благодарен.
Yukimura
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 4
14.12.2013, 00:41  [ТС] #4
Все сделал. Можно закрывать тему.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.12.2013, 00:41
Привет! Вот еще темы с ответами:

Строки в бинарном дереве - C++
Есть шаблонный класс бинарного дерева. Со числами он работает нормально, но при добавлении строки в соответствующий объект этого класса на...

Поиск в Бинарном Дереве! - C++
Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента. Вывести на экран все одинаковые элементы в...

Количество листьев в бинарном дереве - C++
Задача: Найти количество листьев в дереве. Собственно ввод и вывод дерева есть: #include &lt;iostream.h&gt; #include &lt;iomanip.h&gt; ...

Подсчет вершин в бинарном дереве - C++
Здравствуйте,помогите написать функцию ,которая подсчитывает число вершин на N-ом уровне бинарного дерева T(корень считать вершиной 0-го...


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

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

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