Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/9: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Форумчанин
Эксперт CЭксперт С++
8159 / 5007 / 1436
Регистрация: 29.11.2010
Сообщений: 13,458
1

бинарные деревья

22.10.2011, 00:53. Просмотров 1723. Ответов 5
Метки нет (Все метки)

Вот у меня есть программа, которая создает бинарное дерево из массива целых чисел.
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
#include <iostream>
#include <conio.h>
using namespace std;
 
struct  bin_tree
{
   int value;
   bin_tree *left, *right;
}*pHead = NULL; // óêàçàòåëü íà âåðøèíó ðàâåí íóëþ
 
// äîáàâëåíèå óçëà äåðåâà
void add_node(bin_tree* tree, int value); 
// ïðîâåðêà íà "ïóñòîòó" äåðåâà, åñëè óêàçàòåëü íà âåðøèíó ðàâåí íóëþ, ñîçäàåò óçåë
void add_bin_tree(int value);
//Ðåêóðñèâíî ðàñïå÷àòûâàåì ýòî äåðåâî îò ìåíüøåãî ýëåìåíòà ê áîëüøåìó
void print(bin_tree* tree, int level);
 
int main()
{
    int mass[] = {10, 12, 19, 92, 1, 9, 20, 10, 91, 61, 14, 88, 9};
    for (int i = 0; i < sizeof(mass) / sizeof(int); i++)
        add_bin_tree(mass[i]);
    print(pHead, 0);
    //cout<< pHead->value<< " "<< pHead->left->value<< " "<< pHead->right->value<< " ";
    getch();
    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 print(bin_tree* tree, int level)
{      
    if (tree->left != NULL) 
        print(tree->left, level + 1);
    for (int i = 0; i < level; i++)
         cout<< " ";
    cout<< tree->value<< endl;
    if (tree->right != NULL) 
       print(tree->right, level + 1);
}
2 вопроса:
1. Как можно сделать так, чтобы бинарное дерево создавалось с как можно меньшим количеством ярусов? Впринципе вот что пока на уме: отсортировать массив, взять за вершину дерева число, стоящее под индексом, равным размерности массива/2 либо (размерности массива/2 + 0,5). Но как тогда поступать, если нужно добавить новый элемент? Использовать вектор, или вобще все это изврат?
2. Хотелось бы создать функцию печати, чтобы видно было саму структуру дерева, но никаких идей на уме.

В интернете ничего дельного не нашел.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.10.2011, 00:53
Ответы с готовыми решениями:

Бинарные деревья
Ребят, кто может помочь с написанием алгоритма программы? Сам код есть

бинарные деревья
Здравствуйте! Помогите пожалуйста доделать задачу на бинарные деревья. Язык только начали...

Бинарные деревья
Имею три файла: Скажите пожалуйста почему я не могу создать э-т m?(Класс tree) Он мне пишет - ...

Бинарные деревья
Компилятор выдаёт ошибки в 9, 10 и 12, 13 строках: invalid conversion from 'int' to 'sNode*' ...

5
10 / 10 / 3
Регистрация: 22.10.2011
Сообщений: 19
22.10.2011, 05:42 2
У Вирта довольно подробно описано построение сбалансированного дерева. Там же по-моему можно найти форматированный вывод дерева. Найти такую книжку в интернетах не проблема

Добавлено через 54 минуты
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
# include <iostream>
 
using namespace std;
 
class Tree          // tree
{
public:
    struct Node     // struct of Tree's elem
    {
        int key;
        Node *left;     
        Node *right;
        void PrintEl(int lvl);
    };
 
private:
    Node *root;     // ук-ль на корень дерева
    void Insert(int k, Node *&root);    // поиск и вставка эл-та
public:
    Tree() {root = 0;}
    Node* GetRoot() {return *&root ;}
    void BuildTree();   // build tree (:
    void TraceLeft(Node *root);
    void PrintTree();
};
 
int main()
{
    Tree tree;
    tree.BuildTree();
    cout << "It's your tree (:" << endl;
    //tree.TraceLeft(tree.GetRoot());
    tree.PrintTree();
    return 0;
}
 
void Tree::BuildTree()
{
    int k;      // it's temporary for key
    cout << "Enter key" << endl;
    while (cin >> k)
        Insert(k, root);
}
 
void Tree::Insert(int k, Node *&root)
{
    if (root == 0)
    {
        root = new Node;
        root->key = k;
        root->left = 0; root->right = 0;
    }
    else if (k < root->key)
            Insert(k, root->left);
        else if (k > root->key)
            Insert(k, root->right);
}
void Tree::TraceLeft(Node *root)
{
    if (root != 0)
    {
        TraceLeft(root->left);
        cout << root->key << " ";
        TraceLeft(root->right);
    }
}
void Tree::PrintTree()
{
    cout << endl;
    if (root)
        root->PrintEl(0);
}
void Tree::Node::PrintEl(int lvl)
{
    for (int i  = 0; i < lvl; i++)
        cout << " ";
    cout << key << endl;
    if (left)
        left->PrintEl(lvl + 1);
    if (right)
        right->PrintEl(lvl + 1);
}
Вот я кое-что наваял. Только весь код лучше не оценивать, мне за него немножко стыдно, а нужные функции форматированного вывода вроде нормально работают
1
Форумчанин
Эксперт CЭксперт С++
8159 / 5007 / 1436
Регистрация: 29.11.2010
Сообщений: 13,458
26.10.2011, 12:08  [ТС] 3
Столкнулся с новой проблемой. Необходимо обойти бинарное дерево и сохранить последовательность прохождения вершин в файл. У меня записывает только корень дерева.

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <iostream>
#include <clocale>
#include <conio.h>
#include <fstream>
using namespace std;
 
struct node
{
    int Key; 
    int Count; 
    int bal; 
    node *Left, *Right;
};
 
class TREE 
{
  private:
    // h - ôëàã, ñèãíàëèçèðóþùèé îá óâåëè÷åíèè âûñîòû ïîääåðåâà:
    // true - âûñîòà ïîääåðåâà óâåëè÷èëàñü, 
    // false - âûñîòà ïîääåðåâà íå óâåëè÷èëàñü.
    bool h;
    node *Tree;
  public:
    TREE() {Tree = NULL; h = false;}
    void Search (int, node **);
    void Print (node **, int);
    void Traversal (node **);
    node** GetTree() {return &Tree;}
};
 
int main ()
{
    setlocale(LC_ALL, "Russian");
    TREE A;
    int el, n;
    cout<< "Êîëè÷åñòâî âåðøèí â äåðåâå: "; 
    cin>> n;
    cout<< "Èíôîðìàöèîííûå ïîëÿ âåðøèí äåðåâà:\n";
    for (int i=0; i < n; i++)
    { 
        cin>> el;
        A.Search (el, A.GetTree());
    }
    cout<< "\nÀÂË-äåðåâî:\n\n"; 
    A.Print (A.GetTree(), 0);
    A.Traversal (A.GetTree());
    getch();
    return 0;
}
 
void TREE::Search (int x, node **p)
// x - êëþ÷ âåðøèíû, ïîìåùàåìîé â ÀÂË-äåðåâî.
// *p - óêàçàòåëü íà êîðåíü ÀÂË-äåðåâà.
// h - ôëàã, ñèãíàëèçèðóþùèé îá óâåëè÷åíèè âûñîòû ïîääåðåâà:
// true - âûñîòà ïîääåðåâà óâåëè÷èëàñü, 
// false - âûñîòà ïîääåðåâà íå óâåëè÷èëàñü.
// Ïðè ïåðâîì îáðàùåíèè ê ôóíêöèè Search() h=false.
{
    node *p1, *p2;
    h = false;
    if (*p == NULL) // åñëè óêàçàòåëü íà äåðåâî ðàâåí 0
    {  
        *p = new(node);
        h = true; 
        (**p).Key = x; 
        (**p).Count = 1; 
        (**p).Left = (**p).Right = NULL;
        (**p).bal = 0; 
    }
    else 
    if (x <= (**p).Key) 
    {
        Search (x, &((**p).Left)); 
        if (h == true)
            switch ((**p).bal) 
            { 
                case 1 :  (**p).bal = 0; h = false; break; 
                case 0 : (**p).bal = -1; break; 
                case -1: 
                          p1 = (**p).Left; 
                          if ((*p1).bal==-1) 
                          {    
                              (**p).Left = (*p1).Right; 
                              (*p1).Right = *p; 
                              (**p).bal = 0; 
                              *p = p1; 
                          } 
                          else 
                          {
                              p2 = (*p1).Right; 
                              (*p1).Right = (*p2).Left; 
                              (*p2).Left = p1; 
                              (**p).Left = (*p2).Right; 
                              (*p2).Right = *p;
                              if ((*p2).bal == -1) 
                                  (**p).bal = 1; 
                              else 
                                  (**p).bal = 0; 
                              if ((*p2).bal == 1) 
                                  (*p1).bal = -1; 
                              else 
                                  (*p1).bal = 0;
                              *p = p2;
                          } 
                          (**p).bal = 0; 
                          h = false; 
                          break; 
            }
    }
    if (x > (**p).Key) 
    {    
        Search (x, &((**p).Right)); 
        if (h == true)
            switch ((**p).bal) 
            { 
                case -1: (**p).bal = 0; h = false; break; 
                case  0: (**p).bal = 1; break;
                case  1:
                          p1 = (**p).Right; 
                          if ((*p1).bal == 1) 
                          {
                              (**p).Right = (*p1).Left; 
                              (*p1).Left = *p; 
                              (**p).bal = 0; 
                              *p = p1; 
                          } 
                          else
                          {
                               p2 = (*p1).Left; 
                               (*p1).Left = (*p2).Right; 
                               (*p2).Right = p1; 
                               (**p).Right = (*p2).Left; 
                               (*p2).Left = *p; 
                               if ((*p2).bal == 1) 
                                   (**p).bal = -1; 
                               else 
                                   (**p).bal = 0; 
                               if ((*p2).bal == -1) 
                                   (*p1).bal = 1; 
                               else 
                                   (*p1).bal = 0; 
                               *p = p2; 
                          } 
                          (**p).bal = 0; 
                          h = false; 
                          break;
             }
    }
}
 
void TREE::Print (node **w, int lvl)
//Èçîáðàæåíèå äåðåâà w íà ýêðàíå äèñïëåÿ
//         (ðåêóðñèâíûé àëãîðèòì).
//*w - óêàçàòåëü íà êîðåíü äåðåâà.
{
    if  (*w != NULL)
    {
        Print (&((**w).Right), lvl + 1);
        for (int i = 0; i < lvl; i++) 
            cout<< "   ";
        cout<< (**w).Key<< endl;
        Print (&((**w).Left), lvl + 1);
    }
}
 
void TREE::Traversal (node **w)
//*w - óêàçàòåëü íà êîðåíü äåðåâà.
{
    ofstream o("bin.txt");
    if  (*w != NULL)
    {
        Traversal (&((**w).Right));
        o<< (**w).Key<< " ";
        Traversal (&((**w).Left));              
    }
    o.close();
}
Добавлено через 16 часов 49 минут
Цитата Сообщение от MrGluck Посмотреть сообщение
Необходимо обойти бинарное дерево и сохранить последовательность прохождения вершин в файл. У меня записывает только корень дерева.
ап...
0
Эксперт С++
5017 / 2596 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
26.10.2011, 12:40 4
Цитата Сообщение от MrGluck Посмотреть сообщение
бинарное дерево создавалось с как можно меньшим количеством ярусов?
Использовать алгоритмы балансировки деревьев: AVL, red-black.
Цитата Сообщение от MrGluck Посмотреть сообщение
Хотелось бы создать функцию печати, чтобы видно было саму структуру дерева, но никаких идей на уме.
Обычный обход делайте, этого будет достаточно.
1
Форумчанин
Эксперт CЭксперт С++
8159 / 5007 / 1436
Регистрация: 29.11.2010
Сообщений: 13,458
26.10.2011, 13:00  [ТС] 5
Цитата Сообщение от fasked Посмотреть сообщение
Использовать алгоритмы балансировки деревьев: AVL, red-black.

Обычный обход делайте, этого будет достаточно.
Да, я решил использовать АВЛ деревья.

При обходе, если делать вывод на экран, то выводит все вершины, если сделать вывод в файл, выводит только одну, а конкретно корень дерева. (пост 3)
0
Эксперт С++
5017 / 2596 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
26.10.2011, 14:08 6
Цитата Сообщение от MrGluck Посмотреть сообщение
При обходе, если делать вывод на экран, то выводит все вершины, если сделать вывод в файл, выводит только одну, а конкретно корень дерева. (пост 3)
C++
1
2
3
4
5
6
7
8
9
10
11
12
void TREE::Traversal (node **w)
//*w - указатель на корень дерева.
{
    ofstream o("bin.txt");
    if  (*w != NULL)
    {
        Traversal (&((**w).Right));
        o<< (**w).Key<< " ";
        Traversal (&((**w).Left));
    }
    o.close();
}
В данном коде объект ofstream создается каждый раз. Следовательно, он переписывает файл при каждом вызове метода Traversal. В итоге в файле - значение первой вызванной (последней закрытой) функции. Вообще странно, что код отрабатывает. Потому что несколько объектов ofstream обращается к незакрытому файлу.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.10.2011, 14:08

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Бинарные деревья
Вот задачка: Для заданного бинарного дерева поиска проверить условие: • для каждой вершины...

Бинарные деревья
Здравствуйте господа. Очень нуждаюсь в вашей помощи по бинарным деревьям. Собственно, имеется...

бинарные деревья
Вершина двоичного дерева содержит указатель на строку и указатели на правое и левое поддеревья....

Бинарные деревья
Очень нужна помощь, вообще деревья не понимаю!!!:( Вершина дерева содержит указатель на строку и N...

Бинарные деревья
1)Написать программу подсчета числа вершин в бинарном дереве 2)Написать программу копирования...

Бинарные деревья
Подсчитать количество элементов на n-уровне бинарного дерева. Подскажите как можно решить...


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

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

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