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

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

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

Создание бинарного дерева и сортировка в нем масива - C++

04.02.2013, 17:21. Просмотров 770. Ответов 0
Метки нет (Все метки)

Здесь я привел прогу для того чтобы создавать деревья и с их помощью сортировать масив. Но я не знаю как отсортированый список вернуть назад с деревьев в масив.
Что здесь надо сделать подскажите.
Кроме того по заданию мне надо создать бинарные деревья. То есть их надо как то обозначить. А уже потом включать туда масив. Прога с нета. Подскажите что надо сделать. То есть первое задание у меня создать прогу с деревьями даных, а потом уже закидывать туда масив, сортировать и еще надо возвратить назад. Может програма то и правильная, но как ее пристроить к моему заданию. (только без обектно ориентрованых элементов)
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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct tree
{
int a; // дані
struct tree *left; // левый сын
struct tree *right; // правий сын
} TREE;
 
TREE *add_to_tree(TREE *root, int new_value)
{
if (root==NULL) // создаем новый элемент{
root = (TREE*)malloc(sizeof(TREE));
root->a = new_value;
root->left = root->right = 0;
return root;
}
if (root->a < new_value) // добавляем ветвь
root->right = add_to_tree(root->right, new_value);
else
root->left = add_to_tree(root->left, new_value);
return root;
}
void tree_to_array(TREE *root, int a[]) // заполнение масива
{
static max2=0; // счетчик
if (root==NULL) return; // нету сынов
tree_to_array(root->left, a); // обход левого дерева
a[max2++] = root->a;
tree_to_array(root->right, a); // обход правого дерева
free(root);
}
 
void sort_tree(int a[], int elem_total) // сортировка
{
TREE *root;
int i;
 
root = NULL;
for (i=0; i<elem_total; i++) // прохождение через масив и заполнение дерева
root = add_to_tree(root, a[i]);
tree_to_array(root, a); // заполнение масива
}
void main() {
int i;
int a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };
 
sort_tree(a, 14);
 
printf("sorted array:\n");
for (i=0;i<14;i++) printf("%d ",a[i]); 
}
Добавлено через 19 часов 41 минуту
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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
 
using namespace std;
 
struct node // структура для представления узлов дерева
{
   int key;
   unsigned char height;
   node *left;
   node *right;
   node(int k)
   {
      key = k;
      left = right = 0;
      height = 1;
   }
};
 
 
void print_tree_infix(node *p)
{
   if(!p) return;
   else
   {
      print_tree_infix(p->left);
      printf("key=%d\n", p->key);
      print_tree_infix(p->right);
   }
}
 
void tree_to_array(node *p, int *A)
{
   static int i = 0;
   // обнуление статической постоянной
   if(!A)
   {
      i = 0;
      return;
   }
   // проход дерева
   if(!p) return;
   else
   {
      tree_to_array(p->left, A);
      A[i++] = p->key;
      tree_to_array(p->right, A);
   }
}
 
void print_array(int *A, int n)
{
   for(int i = 0; i < n; i++)
      printf("%d ", A[i]);
   printf("\n");
}
////////////////////////////////////////////////////////////////////////////////
 
unsigned char height(node *p)
{
   return p ? p->height : 0;
}
 
int bfactor(node *p)
{
   return height(p->right) - height(p->left);
}
 
void fixheight(node *p)
{
   unsigned char hl = height(p->left);
   unsigned char hr = height(p->right);
   p->height = (hl > hr ? hl : hr) + 1;
}
 
node *rotateright(node *p) // правый поворот вокруг p
{
   node *q = p->left;
   p->left = q->right;
   q->right = p;
   fixheight(p);
   fixheight(q);
   return q;
}
 
node *rotateleft(node *q) // левый поворот вокруг q
{
   node *p = q->right;
   q->right = p->left;
   p->left = q;
   fixheight(q);
   fixheight(p);
   return p;
}
 
node *balance(node *p) // балансировка узла p
{
   fixheight(p);
   if( bfactor(p) == 2 )
   {
      if( bfactor(p->right) < 0 )
         p->right = rotateright(p->right);
      return rotateleft(p);
   }
   if( bfactor(p) == -2 )
   {
      if( bfactor(p->left) > 0  )
         p->left = rotateleft(p->left);
      return rotateright(p);
   }
   return p; // балансировка не нужна
}
 
node *insert(node *p, int k) // вставка ключа k в дерево с корнем p
{
   if( !p ) return new node(k);
   if( k < p->key )
      p->left = insert(p->left, k);
   else
      p->right = insert(p->right, k);
   return balance(p);
}
 
node *findmin(node *p) // поиск узла с минимальным ключом в дереве p
{
   return p->left ? findmin(p->left) : p;
}
 
node *removemin(node *p) // удаление узла с минимальным ключом из дерева p
{
   if( p->left == 0 )
      return p->right;
   p->left = removemin(p->left);
   return balance(p);
}
 
node *remove(node *p, int k) // удаление ключа k из дерева p
{
   if( !p ) return 0;
   if( k < p->key )
      p->left = remove(p->left, k);
   else if( k > p->key )
      p->right = remove(p->right, k);
   else //  k == p->key
   {
      node *q = p->left;
      node *r = p->right;
      delete p;
      if( !r ) return q;
      node *min = findmin(r);
      min->right = removemin(r);
      min->left = q;
      return balance(min);
   }
   return balance(p);
}
Добавлено через 6 минут
Скажите как во втором коде или первом вставить поочередно ключи деревьев в функции main. Напрмер с помощью функции инсерт. insert (root,"a"), а как тогда вводить с помощью командной строки. Надо что сперва лиш создавать масив, а уже потом вводить значение функции?

Добавлено через 3 минуты
for(int i = 0; i < n; i++)
root = insert(root, A[i])--например масив вводится так. А с командной строки чтоли просто вписать cin>>. Нон как в даном случае отделять элементы деревьев?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.02.2013, 17:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Создание бинарного дерева и сортировка в нем масива (C++):

Создание бинарного дерева из бинарного файла - C++
struct Bin { string name; string city; int players; int score; }; void ReadFromBin(Point*&amp; Tree) { Bin q;

Создание бинарного дерева - C++
Есть задания и я знаю как их сделать, но не понимаю, как создать и вывести на экран бинарное дерево. Подскажите пожалуйста, ссылки, коды,...

Создание прошитого бинарного дерева - C++
есть файл fIn.txt A BC D_IF ___L то есть _ значает что потомка нет (например у B потомок только B, второго нет); ,...

Создание бинарного дерева поиска - C++
Людииииии помогите пож-таааа.....Нужно создать бинарное дерево поиска, считывая элементы из текст файла.. Очень нужноооо:( кто нибудь:(:(...

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

Создание бинарного дерева и ограничение на количество узлов в ней - C++
В задании по созданию бинарного дерева есть условие на то, что узлов в дереве должно быть не больше 10. Пробую поставить такое ограничение...

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

Запись бинарного дерева в файл и восстановление из него этого дерева - C++
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя - 1 указатель на структуру с данными, 2 и 3й указатель на...

Написать шаблон бинарного дерева с функцией распечатки дерева - C++
Не понимаю, что от меня хотят. Дано такое задание: Написать шаблон бинарного дерева с функцией распечатки дерева *(+(d,e),c) в виде...

Построение бинарного дерева на основе не бинарного - C++
В лабораторной работе есть такое задание: Создайте процедуру построения бинарного дерева на основе не бинарного. Объясните как вообще...

Вывод бинарного дерева на экран в виде "дерева" - C++
основная задача: подсчет количества листьев. проблема: при просмотре хочу выводить бин. дерево, в красивом виде, возможно использование...


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

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

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