Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

11.03.2013, 18:07. Просмотров 857. Ответов 0
Метки нет (Все метки)

Народ меня тут 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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2013, 18:07
Здравствуйте! Я подобрал для вас темы с ответами на вопрос По входной последовательности построить дерево бинарного поиска и найти количество узлов, имеющих только одного левого потомка (C++):

Дерево бинарного поиска - C++
Никак не могу понять как изменить бинарный поиск. Код выводит значения элементов для которых высота левого поддерева больше высоты правого,...

Дерево бинарного поиска - C++
Всем привет! Есть рабочий код бинарного поиска template &lt;class Item, class Key&gt; class ST { private: struct node { Item item;...

Дополнить дерево бинарного поиска - C++
Помогите дополнить программу методом подсчета числа узлов заданного бинарного дерева и методом подсчета числа листьев заданного бинарного...

Удалить из бинарного дерева всех отцов, имеющих одного сына - C++
Написала класс по работе с бинарным деревом. Помогите, пожалуйста, написать функцию по удалению из дерева всех однодетных отцов. Сижу уже...

Определение количество узлов, имеющих лишь одного потомка - C (СИ)
Функция (potomki) считает значение некорректно. Прошу помощи знающих людей. #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include...

Функция, определяющая количество вершин дерева, имеющих только одного потомка - C#
public class Node { public readonly int value; public readonly List&lt;Node&gt; leaves = new List&lt;Node&gt;(); ...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.03.2013, 18:07
Привет! Вот еще темы с ответами:

В дереве бинарного поиска найти для него количество четных значений узлов дерева - C#
В файле input.txt хранится последовательность целых чисел. По входной последовательности построить дерево бинарного поиска и найти для...

Монотонная последовательность узлов бинарного дерева поиска - C#
Добрый день. есть бинарное дерево поиска и какое-то заданное число S. Нужно найти все монотонные последовательности узлов дерева, сумма...

Дерево бинарного поиска - PascalABC.NET
Вывести дерево двоичного поиска по уровням В input: 30 25 26 15 35 33 40

Найти количество строк матрицы, не имеющих ни одного нулевого элемента - Pascal
дана целочисленная прямоугольная матрица размерность задать константами все необходимые даннные задаются в подпрограмме ...


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

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

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