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

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

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

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

12.12.2013, 15:55. Просмотров 359. Ответов 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++
Здравствуйте! Помогите ещё с задачками) 1.Поиск ключа в бинарном дереве поиска (точное соответствие). 2. Поиск ключа в бинарном...

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

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

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

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

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

Оператор присвоения в бинарном дереве - C++
Не смог разобраться. Прокомментируйте, будьте добры. Задание такое, определите стандартный конструктор и функции управления...

Поиск дубликатов в бинарном дереве - C++
Требуется создать функцию поиска дубликатов ИНФОРМАЦИОННОЙ ЧАСТИ, НЕ КЛЮЧА в бинарном дереве. Ничего похожего в гугле и здесь на...

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

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

Удалить узел в бинарном дереве - C++
Добрый вечер. В задании нужно найти узел дерева с наибольшим показателем счетчика, после чего удалить найденный узел из дерева. В структуре...

Сумма чисел в бинарном дереве - C++
Выбрать уровень(глубину, высоту) бинарного дерева и посчитать сумму чисел(в вершинах), находящихся на этом уровне. P.S. Дерево построено,...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
Все сделал. Можно закрывать тему.
Yandex
Объявления
14.12.2013, 00:41     Необычная функция в бинарном дереве поиска
Ответ Создать тему
Опции темы

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