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

По входной последовательности построить дерево бинарного поиска и найти количество узлов, имеющих только одного левого потомка - C++

Восстановить пароль Регистрация
 
Priorzivil
0 / 0 / 0
Регистрация: 11.03.2013
Сообщений: 11
11.03.2013, 18:07     По входной последовательности построить дерево бинарного поиска и найти количество узлов, имеющих только одного левого потомка #1
Народ меня тут 11 задач мне нужно их подробно прокомментировать какая строчка что делает(пример первая задача) помогите плиз кому не сложно хотя бы по одной задачке буду очень благодарен

Задача 8 Деревья 1

в файле input.txt хранится последовательность целых чисел. По входной последовательности построить дерево бинарного поиска и найти количество узлов, имеющих только одного левого потомка
Input:
Код
15 10 9 13 12 8 18
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
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
 
using namespace std;
 
class tree {
private:
 
    struct el {
        int val;
        el *l_tree;
        el *r_tree;
 
        el() {
            l_tree = 0;
            r_tree = 0;
        }
    };
 
    el *root;
 
public:
 
    tree() {root = 0;}
 
 
    void push (int x, el *&b) {
        if (!b) {
            el *t = new el;
            t->val = x;
            t->l_tree = t->r_tree = NULL;
            b = t;
        }
 
        if (b->val > x)
            push (x, b->l_tree);
        else
            if (b->val < x)
                push (x, b->r_tree);
    }
 
    void add (int x) {
        push(x, root);
    }
 
    //метод выводящий дерево в симметрическом порядке
    void print (el *r = 0) {
        if (r == 0)
            r = root;
 
        if (r->l_tree != 0)
            print (r->l_tree);
 
        cout << r->val << ' ';
 
        if (r->r_tree != 0)
            print (r->r_tree);
    }
 
    //метод ищущий ответ на задачу
    int ans (el *r = 0) {
        if (r == 0)
            r = root;
 
        int cnt = 0;
 
        if (r->l_tree != NULL) {
            cnt += ans (r->l_tree);
        }
 
        if (r->r_tree != NULL) {
            cnt += ans (r->r_tree);
        }
 
        if (r->l_tree != NULL && r->r_tree == NULL)
            ++cnt;
 
        return cnt;
    }
 
};
 
int main () {
    freopen("input.txt", "r", stdin);
    
    int x;
 
    tree derevo;
 
    while (cin >> x) {
        derevo.add(x);
    }
 
    cout << "Bin tree search:";
    derevo.print();
    cout << endl << "Answer:" << endl;
    cout << derevo.ans() << endl;
    return 0;
}
output:
Код
Bin tree search: 8 9 10 12 13 15 18
Answer: 2
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2013, 18:07     По входной последовательности построить дерево бинарного поиска и найти количество узлов, имеющих только одного левого потомка
Посмотрите здесь:

C++ Дерево бинарного поиска
C++ Структура, по строкам построить бинарное дерево поиска
Описать строку А. Из входной последовательности символов записать в строку А только цифры C++
C++ Удалить из бинарного дерева всех отцов, имеющих одного сына
C++ Найти среднее арифметическое узлов бинарного дерева целых чисел
C++ Построить односвязный список из входной последовательности чисел
C++ Создание бинарного дерева и ограничение на количество узлов в ней
C++ Удаление элементов из бинарного дерева (не дерево поиска)

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 07:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru