Довести до ума программу про бинарному дереву

@HanteR · Регистрация: 23.10.2009

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

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

Вот что у меня имеется:
* Функция которая за заданным массивом организовывает бинарное дерево:

C++
1
2
3
4
5
6
7
8
9
10
11
12
bntrp build (int a[], int n)
{   bntrp p;
    int c;
    p = NULL;
   if (n) {  c = n/2;
               p = (bntrp) calloc (1, sizeof (bntrn));
               p->val = a[c];
               p->l = build (&a[0], c);
               p->r = build (&a[c+1], n-c-1);
            }
   return p;
}

* Функция включения элемента в это дерево:

C++
1
2
3
4
5
6
bntrp insert (bntrp p, int d)
{ if (!p) return new(d);
   if (p->val > d) p->l = insert(p->l, d);
     else p->r = insert(p->r, d);
   return p;
}

помогите соединить все это, что-бы работало. Заранее спасибо.

@Vladimir. · 06.12.2010, 18:45

C++
1
 if (!p) return new(d);

поясните, что вы делаете в этой строке.

@HanteR · 06.12.2010, 20:46 **[ТС]**

Сообщение от Vladimir.

C++
1
 if (!p) return new(d);

поясните, что вы делаете в этой строке.

я взял эти примеры из лабораторных

@Vladimir. · 06.12.2010, 21:37

если оператор new не перегружен (а в лабораторной это скорее всего так) то строка должна быть чем-то вроде:

if (!p) return *(new bntrp(d));

так же не очень понятно зачем создавать узлы дерева через calloc, если есть тот же new, не понимаю этой хитрости, разве что для инициализации полей bntrp нулями..

@HanteR · 06.12.2010, 21:43 **[ТС]**

а можете сделать программу так, как Вы правильным?

@Vladimir. · 07.12.2010, 07:20

Я бы начал с того что описал бы класс дерево, а потом постепенно добавлял к нему функционал.
Что-то вроде такого для начала:

код

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
#include<time.h>
#include<stdlib.h>
 
#include<iostream>
struct nodes{
    int     data;
 
    nodes*  left;
    nodes*  right;
};
class trees{
    private:
        nodes*  root; // старший предок. начало дерева.
    
        nodes*  add_node(int data, nodes* ptr);
        void    traverse_show(nodes* ptr);
    
    public:
        trees() {root = NULL;}
        ~trees(){};
        
        void    add(int data);
        void    show() {traverse_show(root);}
};
 
void trees::add(int data){ 
    
    if (root != NULL){ add_node(data, root); return;}
    
    root = add_node(data, root);
}
 
nodes* trees::add_node(int x,nodes* p){
    if(p == NULL){ //возникает в случае пустого дерева.
        p = new nodes;
        p->left = NULL;
        p->right = NULL;
        p->data = x;    
        return p;
    }
    
    if((x > p->data)&&(p->right == NULL)){ //правый лист.
        p->right = new nodes;
        p->right->right = NULL;
        p->right->left = NULL;
        p->right->data = x;
        return p->right;
    }
    else if((x <= p->data)&&(p->left == NULL)){ //левый лист.
        p->left = new nodes;
        p->left->left = NULL;
        p->left->right = NULL;
        p->left->data = x;
        return p->left;
    }
    else{ //спускаемся по дереву
    p = (p->data <= x)? p->left : p->right; // ключ - данные.
    return (add_node(x, p)); 
    }
    
}

@HanteR · 07.12.2010, 17:16 **[ТС]**

Сообщение от Vladimir.

Я бы начал с того что описал бы класс дерево, а потом постепенно добавлял к нему функционал.
Что-то вроде такого для начала:

код

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
#include<time.h>
#include<stdlib.h>
 
#include<iostream>
struct nodes{
    int     data;
 
    nodes*  left;
    nodes*  right;
};
class trees{
    private:
        nodes*  root; // старший предок. начало дерева.
    
        nodes*  add_node(int data, nodes* ptr);
        void    traverse_show(nodes* ptr);
    
    public:
        trees() {root = NULL;}
        ~trees(){};
        
        void    add(int data);
        void    show() {traverse_show(root);}
};
 
void trees::add(int data){ 
    
    if (root != NULL){ add_node(data, root); return;}
    
    root = add_node(data, root);
}
 
nodes* trees::add_node(int x,nodes* p){
    if(p == NULL){ //возникает в случае пустого дерева.
        p = new nodes;
        p->left = NULL;
        p->right = NULL;
        p->data = x;    
        return p;
    }
    
    if((x > p->data)&&(p->right == NULL)){ //правый лист.
        p->right = new nodes;
        p->right->right = NULL;
        p->right->left = NULL;
        p->right->data = x;
        return p->right;
    }
    else if((x <= p->data)&&(p->left == NULL)){ //левый лист.
        p->left = new nodes;
        p->left->left = NULL;
        p->left->right = NULL;
        p->left->data = x;
        return p->left;
    }
    else{ //спускаемся по дереву
    p = (p->data <= x)? p->left : p->right; // ключ - данные.
    return (add_node(x, p)); 
    }
    
}

спасибо. а можно программу целиком?

Новые блоги и статьи Все статьи Все блоги /
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.

@Vladimir. 377 / 228 / 79 Регистрация: 24.11.2009 Сообщений: 695
	06.12.2010, 21:37
	если оператор new не перегружен (а в лабораторной это скорее всего так) то строка должна быть чем-то вроде: if (!p) return (new* bntrp(d)); так же не очень понятно зачем создавать узлы дерева через calloc, если есть тот же new, не понимаю этой хитрости, разве что для инициализации полей bntrp нулями.. 0

@HanteR 1 / 1 / 0 Регистрация: 23.10.2009 Сообщений: 53
	06.12.2010, 21:43 [ТС]
	а можете сделать программу так, как Вы правильным? 0