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

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

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

Проверить монотонность убывания ширины уровня дерева - C++

28.06.2012, 17:30. Просмотров 447. Ответов 7
Метки нет (Все метки)

Задача на бинарное дерево. Катастрофически не успеваю решить... Если кто-нибудь накидает код, буду премного! благодарен. Если, к сожалению, нету желания или времени, то можно хотя бы примеры полных программ построения бинарного дерева (с главной функцией). Я хотя бы там, возможно, что-то использовал...

Большое спасибо за внимание.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.06.2012, 17:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Проверить монотонность убывания ширины уровня дерева (C++):

Проверить на эквивалентность два AVL-дерева - C++
Такое вот задание: проверить на эквивалентность два АВЛ-дерева. Если они не являются информационно эквивалентными, указать минимальное по...

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

Создать полную копию исходного дерева и проверить узел - C++
У меня есть дерево выражения(двоичное дерево). По алгоритму происходит следующее: 1. Проверяю каждый узел дерева. 2. Если с ним...

Определить монотонность последовательности - C++
Задание. Разработать алгоритмы обработки одномерных целочисленных массивов (см. варианты). Представить алгоритм в виде блок-схемы и...

Определить монотонность последовательности - C++
С устройства ввода последовательно поступают целые числа. Признаком конца последовательности является 0. Определить, является ли...

Проверка булевой функции на монотонность - C++
Надо проверить является ли булева функция монотонной. Она задается вектором своих значений Как проверить на монотонность? (т.е....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MrGluck
Модератор
Эксперт CЭксперт С++
7210 / 4376 / 638
Регистрация: 29.11.2010
Сообщений: 11,887
28.06.2012, 18:40 #2
Просто строит и обходит:
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
#include <iostream>
#include <conio.h>
#include <fstream>
using namespace std;
 
struct  bin_tree
{
   int value;
   bin_tree *left, *right;
}*pHead = NULL; // ГіГЄГ*Г§Г*òåëü Г*Г* âåðøèГ*Гі Г°Г*ГўГҐГ* Г*óëþ
 
// äîáГ*âëåГ*ГЁГҐ ГЄГ®Г*êðåòГ*îãî óçëГ* äåðåâГ*
void add_node(bin_tree*, int); 
// ïðîâåðêГ* Г*Г* "ïóñòîòó" äåðåâГ*, åñëè ГіГЄГ*Г§Г*òåëü Г*Г* âåðøèГ*Гі Г°Г*ГўГҐГ* Г*óëþ, ñîçäГ*ГҐГІ óçåë
void add_bin_tree(int);
// îáõîä
void print(bin_tree*);
void traversal(bin_tree*, ofstream&);
int h_tree(bin_tree *);
 
int main()
{
    setlocale (LC_ALL, "Russian");
    int choose, el;
    cout<< "1. Г‡Г*ãðóçèòü ïîñëåäîâГ*òåëüГ*îñòü Г± ГґГ*éëГ*\n"
        << "2. Ââåñòè ïîñëåäîâГ*òåëüГ*îñòü âðó÷Г*ГіГѕ\n\n"
        << "Г‚Г*Гё âûáîð: ";
    do{ cin>> choose;} while(choose != 1 && choose != 2);
    if (choose == 1)
    {        
        ifstream iz("bin.txt");
        if (iz.bad()) return 1;
        while(!iz.eof() && iz>> el)
            add_bin_tree (el);     
        iz.close();
    }
    
    if (choose == 2)
    {
        cout<< "Г€Г*ôîðìГ*öèîГ*Г*ûå ïîëÿ âåðøèГ* äåðåâГ*:\n";
        while(cin>> el)
            add_bin_tree (el);
    }
    ofstream o("bin.txt");
    print (pHead);
    traversal (pHead, o);
    getch();
    o.close();
    return 0;
}
 
void add_node(bin_tree* tree, int value) // äîáГ*âëåГ*ГЁГҐ ГЄГ®Г*êðåòГ*îãî óçëГ* äåðåâГ*
{
    if(value < tree->value)
    { 
        if(tree->left != NULL) // åñëè Г§Г*Г*Г·ГҐГ*ГЁГҐ ìåГ*ГјГёГҐ, äâèãГ*åìñÿ ГЇГ® "ëåâîé ГўГҐГІГЄГҐ"
            add_node(tree->left, value);
        else
        {  
            tree->left = new bin_tree;
            tree->left->value = value;
            tree->left->left = NULL;
            tree->left->right = NULL;
        }
    }
 
    if(value > tree->value) // ГЁГ*Г*Г·ГҐ äâèãГ*åìñÿ ГЇГ® ГЇГ°Г*âîé 
    { 
        if(tree->right != NULL)
            add_node(tree->right, value);
        else
        {
            tree->right = new bin_tree;
            tree->right->value = value;
            tree->right->left=NULL;
            tree->right->right=NULL;
        }
    }
 
    if(value == tree->value)                
        cout<< value<< " is already in tree"<< endl;
}
 
void add_bin_tree(int value)
{
    if(pHead == NULL) // åñëè äåðåâî ïóñòîå - ñîçäГ*äèì ïåðâûé óçåë
    {
       pHead = new bin_tree;
       pHead->value = value;
       pHead->left = NULL;
       pHead->right = NULL;
    }
    else
        add_node(pHead, value); // åñëè Гў âåðøèГ*ГҐ óæå Г·ГІГ®-ГІГ® ГҐГ±ГІГј - äîáГ*âëÿåì ñëåâГ* èëè Г±ГЇГ°Г*ГўГ* 
}
 
void traversal(bin_tree* tree, ofstream &o)
{     
    if (tree != NULL)
    { 
        traversal(tree->left, o);
        o<< tree->value<< " ";
        traversal(tree->right, o);
    }
}
 
void print(bin_tree* tree)
{     
    if (tree != NULL)
    { 
        print(tree->left);
        cout<< tree->value<< " ";
        print(tree->right);
    }
}
 
int h_tree(bin_tree* tree)
{
     int h = 1, m = 0, s;
     if (tree == NULL)
        return 0;
     s = h_tree(tree->left);
     if (s > m)
         m = s;
     s = h_tree(tree->right);
     if (s > m)
         m = s;
     return h + m;
}
P.S. делал год-два назад
Beatles
1 / 1 / 0
Регистрация: 18.04.2012
Сообщений: 36
28.06.2012, 18:51  [ТС] #3
О, даже с файлом... Спасибо в который раз. А вы, случаем, её на Паскале не писали год-два назад?) Мне просто её ещё на Паскале придётся писать. Мало ли... Может "завалялась") И дальше только разбираться...)
MrGluck
Модератор
Эксперт CЭксперт С++
7210 / 4376 / 638
Регистрация: 29.11.2010
Сообщений: 11,887
28.06.2012, 18:57 #4
Цитата Сообщение от Beatles Посмотреть сообщение
О, даже с файлом... Спасибо в который раз. А вы, случаем, её на Паскале не писали год-два назад?) Мне просто её ещё на Паскале придётся писать. Мало ли... Может "завалялась") И дальше только разбираться...)
Нет, я паскаль не проходил. В школе на уроках информатики мы описывали алгоритм чистки ботинок и гоняли в екселе, кто быстрее доберется до последней строчки, а в универе уже занимались нормальным программированием на нормальном языке.
Beatles
1 / 1 / 0
Регистрация: 18.04.2012
Сообщений: 36
28.06.2012, 19:02  [ТС] #5
Вообще многие считают, что Паскаль сейчас проходить бессмысленно, т.к. он уже не актуален. Мне тоже так кажется, но так или иначе проходим, изучаем, мучаем... Спрашивается для чего, если всё равно вскоре его оставляют и программируют, как вы сказали, на "нормальном языке". Видимо, почувствовать разницу. Других мыслей нету
MrGluck
Модератор
Эксперт CЭксперт С++
7210 / 4376 / 638
Регистрация: 29.11.2010
Сообщений: 11,887
28.06.2012, 20:13 #6
Цитата Сообщение от Beatles Посмотреть сообщение
Вообще многие считают, что Паскаль сейчас проходить бессмысленно, т.к. он уже не актуален. Мне тоже так кажется, но так или иначе проходим, изучаем, мучаем... Спрашивается для чего, если всё равно вскоре его оставляют и программируют, как вы сказали, на "нормальном языке". Видимо, почувствовать разницу. Других мыслей нету
Паскаль - учебный язык, как язык программирования легче осваивается и не имеет, как говорят, такого жуткого пугающего синтаксиса. Но, спрашивается, зачем изучать то, что потом не будешь использовать.
Beatles
1 / 1 / 0
Регистрация: 18.04.2012
Сообщений: 36
28.06.2012, 20:15  [ТС] #7
Солидарен.
BumerangSP
01.07.2012, 22:32     Проверить монотонность убывания ширины уровня дерева
  #8

Не по теме:

Верите или нет, но некоторые люди и на делфи остаются. Мне, например, паскаль очень помог при освоении Си. Можно сказать, только синтаксис оставалось выучить))

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

Монотонность убывания ширины уровня бинарного дерева - C (СИ)
Собственно, задача в том, чтобы проверить монотонность убывания ширины уровня дерева. Что есть: есть программа: #include &lt;stdio.h&gt; ...

Проверить самодвойственность, монотонность и линейность логической функции - Логика и множества
Помогите выполнить ((x\oplus y)\rightarrow \bar{x})\rightarrow \bar{(\bar{x}\rightarrow (y\sim \bar{x}))} Добавлено через 47...

Определение уровня дерева - Delphi
Кто знает, подскажите пожааалуйстаа как можно определять уровни дерева? (Корень - считать первым уровнем...) З.Ы. Заранее спасибо...

Получить узел дерева нулевого уровня - C#
Добрый день!. Ест дерево - на 0 уровне имя ПК, на 1 уровне в соответствующей ветке имя ОРС сервера, и далее его содержимое - папки и тэги. ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
01.07.2012, 22:32
Ответ Создать тему
Опции темы

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