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

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

Восстановить пароль Регистрация
 
Beatles
1 / 1 / 0
Регистрация: 18.04.2012
Сообщений: 36
28.06.2012, 17:30     Проверить монотонность убывания ширины уровня дерева #1
Задача на бинарное дерево. Катастрофически не успеваю решить... Если кто-нибудь накидает код, буду премного! благодарен. Если, к сожалению, нету желания или времени, то можно хотя бы примеры полных программ построения бинарного дерева (с главной функцией). Я хотя бы там, возможно, что-то использовал...

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

Создать полную копию исходного дерева и проверить узел C++
C++ Проверить упорядочены ли элементы вектора. Если нет, то упорядочить в порядке убывания методом стандартного обмена
C++ Вывод бинарного дерева на экран в виде "дерева"
Написать шаблон бинарного дерева с функцией распечатки дерева C++
Проверить на эквивалентность два AVL-дерева C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
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
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
28.06.2012, 18:57     Проверить монотонность убывания ширины уровня дерева #4
Цитата Сообщение от Beatles Посмотреть сообщение
О, даже с файлом... Спасибо в который раз. А вы, случаем, её на Паскале не писали год-два назад?) Мне просто её ещё на Паскале придётся писать. Мало ли... Может "завалялась") И дальше только разбираться...)
Нет, я паскаль не проходил. В школе на уроках информатики мы описывали алгоритм чистки ботинок и гоняли в екселе, кто быстрее доберется до последней строчки, а в универе уже занимались нормальным программированием на нормальном языке.
Beatles
1 / 1 / 0
Регистрация: 18.04.2012
Сообщений: 36
28.06.2012, 19:02  [ТС]     Проверить монотонность убывания ширины уровня дерева #5
Вообще многие считают, что Паскаль сейчас проходить бессмысленно, т.к. он уже не актуален. Мне тоже так кажется, но так или иначе проходим, изучаем, мучаем... Спрашивается для чего, если всё равно вскоре его оставляют и программируют, как вы сказали, на "нормальном языке". Видимо, почувствовать разницу. Других мыслей нету
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
28.06.2012, 20:13     Проверить монотонность убывания ширины уровня дерева #6
Цитата Сообщение от Beatles Посмотреть сообщение
Вообще многие считают, что Паскаль сейчас проходить бессмысленно, т.к. он уже не актуален. Мне тоже так кажется, но так или иначе проходим, изучаем, мучаем... Спрашивается для чего, если всё равно вскоре его оставляют и программируют, как вы сказали, на "нормальном языке". Видимо, почувствовать разницу. Других мыслей нету
Паскаль - учебный язык, как язык программирования легче осваивается и не имеет, как говорят, такого жуткого пугающего синтаксиса. Но, спрашивается, зачем изучать то, что потом не будешь использовать.
Beatles
1 / 1 / 0
Регистрация: 18.04.2012
Сообщений: 36
28.06.2012, 20:15  [ТС]     Проверить монотонность убывания ширины уровня дерева #7
Солидарен.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.07.2012, 22:32     Проверить монотонность убывания ширины уровня дерева
Еще ссылки по теме:

C++ Проверка булевой функции на монотонность
Определить монотонность последовательности C++
C++ Определить монотонность последовательности

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

Или воспользуйтесь поиском по форуму:
BumerangSP
01.07.2012, 22:32     Проверить монотонность убывания ширины уровня дерева
  #8

Не по теме:

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

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

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