0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 4
1

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

12.12.2013, 15:55. Показов 895. Ответов 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;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.12.2013, 15:55
Ответы с готовыми решениями:

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

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

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

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

3
17 / 17 / 5
Регистрация: 06.12.2012
Сообщений: 46
12.12.2013, 18:17 2
Попробуй ввести переменную в структуру - глубина, int deep; и заполняй ее - глубина root = 0; потом обход и вывод с определенной глубиной.
1
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 4
12.12.2013, 18:22  [ТС] 3
Я не знаю как это реализовать. Если не затруднит, исправьте исходник пожалуйста.
Заранее благодарен.
0
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 4
14.12.2013, 00:41  [ТС] 4
Все сделал. Можно закрывать тему.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.12.2013, 00:41
Помогаю со студенческими работами здесь

Функция: есть ли в бинарном дереве внутренний узел, у которого только один потомок?
Здравствуйте. Помогите пожалуйста. Надо написать функцию,проверяющую есть ли в дереве внутренний...

Поиск в бинарном дереве
Привет всем! Нужно написать код, с которым в бинарном дереве можно найти заданное пользователем...

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

Строки в бинарном дереве
Есть шаблонный класс бинарного дерева. Со числами он работает нормально, но при добавлении строки в...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru