Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
1 / 1 / 0
Регистрация: 18.04.2012
Сообщений: 36
1

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

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

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

Большое спасибо за внимание.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.06.2012, 17:30
Ответы с готовыми решениями:

Проверить монотонность последовательности
Пользователь вводит массив из 7 чисел, программа выясняет все ли числа идут в порядке возрастания

Монотонность убывания ширины уровня бинарного дерева
Собственно, задача в том, чтобы проверить монотонность убывания ширины уровня дерева. Что есть:...

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

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

7
Форумчанин
Эксперт CЭксперт С++
8169 / 5017 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
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. делал год-два назад
1
1 / 1 / 0
Регистрация: 18.04.2012
Сообщений: 36
28.06.2012, 18:51  [ТС] 3
О, даже с файлом... Спасибо в который раз. А вы, случаем, её на Паскале не писали год-два назад?) Мне просто её ещё на Паскале придётся писать. Мало ли... Может "завалялась") И дальше только разбираться...)
0
Форумчанин
Эксперт CЭксперт С++
8169 / 5017 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
28.06.2012, 18:57 4
Цитата Сообщение от Beatles Посмотреть сообщение
О, даже с файлом... Спасибо в который раз. А вы, случаем, её на Паскале не писали год-два назад?) Мне просто её ещё на Паскале придётся писать. Мало ли... Может "завалялась") И дальше только разбираться...)
Нет, я паскаль не проходил. В школе на уроках информатики мы описывали алгоритм чистки ботинок и гоняли в екселе, кто быстрее доберется до последней строчки, а в универе уже занимались нормальным программированием на нормальном языке.
0
1 / 1 / 0
Регистрация: 18.04.2012
Сообщений: 36
28.06.2012, 19:02  [ТС] 5
Вообще многие считают, что Паскаль сейчас проходить бессмысленно, т.к. он уже не актуален. Мне тоже так кажется, но так или иначе проходим, изучаем, мучаем... Спрашивается для чего, если всё равно вскоре его оставляют и программируют, как вы сказали, на "нормальном языке". Видимо, почувствовать разницу. Других мыслей нету
0
Форумчанин
Эксперт CЭксперт С++
8169 / 5017 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
28.06.2012, 20:13 6
Цитата Сообщение от Beatles Посмотреть сообщение
Вообще многие считают, что Паскаль сейчас проходить бессмысленно, т.к. он уже не актуален. Мне тоже так кажется, но так или иначе проходим, изучаем, мучаем... Спрашивается для чего, если всё равно вскоре его оставляют и программируют, как вы сказали, на "нормальном языке". Видимо, почувствовать разницу. Других мыслей нету
Паскаль - учебный язык, как язык программирования легче осваивается и не имеет, как говорят, такого жуткого пугающего синтаксиса. Но, спрашивается, зачем изучать то, что потом не будешь использовать.
0
1 / 1 / 0
Регистрация: 18.04.2012
Сообщений: 36
28.06.2012, 20:15  [ТС] 7
Солидарен.
0
BumerangSP
01.07.2012, 22:32     Проверить монотонность убывания ширины уровня дерева
  #8

Не по теме:

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

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.07.2012, 22:32

Помощь в написании контрольных, курсовых и дипломных работ здесь.

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

Подсчитать число вершин на n – ом уровне непустого дерева Т (корень считать вершиной нулевого уровня)
Дана такая задача: &quot;Подсчитать число вершин на n – ом уровне непустого дерева Т (корень считать...

Разработать функцию, которая находит минимальный элемент среди элементов заданного уровня бинарного дерева
Разработать функцию, которая находит минимальный элемент среди элементов заданного уровня бинарного...

Проверить гипотезу для заданного уровня значимости.
Помогите с решение задачи, пожалуйста) нужно три способа, как я понимаю


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

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

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