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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ While (нечетные целые числа из диапазона) http://www.cyberforum.ru/cpp-beginners/thread778329.html
1.Напишите программу, которая бы выводила на экран только нечетные целые числа из диапазона от 0 до, указанного пользователем, числа.
C++ Move to front, алгоритм на C++, error C4996: 'fopen': Об'ясните ошибку: 1>c:\users\admin\documents\visual studio 2012\projects\consoleapplication2\consoleapplication2\consoleapplication2.cpp(79): error C4996: 'fopen': This function or variable may be... http://www.cyberforum.ru/cpp-beginners/thread778326.html
C++ Do while поиск суммы положительных чисел
Написать программу поиска суммы последовательности положительных чисел, вводимых с клавиатуры. Завершением ввода считать введенный ноль. Контрольный пример: 1 2 3 -4 5 -2 0 Результат: 11
Среднее арифметическое элементов одномерного массива C++
Задание написать программу с помощью функции , найти среднее арифметическое элементов одномерного массива . без функции я нашел, но если кого нибудь не затруднит помогите найти программу с функцией...
C++ Цикл do while. Написать программу, которая определяет максимальное число из введенной с клавиатуры последовательности http://www.cyberforum.ru/cpp-beginners/thread778285.html
Как написать программу, которая определяет максимальное число из введенной с клавиатуры последовательности положительных чисел (длина последовательности неограниченна). Ниже приведен...
C++ Память распределить динамически Задали такую задачу :память матрицы распределить динамически .Найти среднее арифметическое области заштрихованной области 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 ( 1 заштрихованная... подробнее

Показать сообщение отдельно
maxii
1 / 1 / 0
Регистрация: 28.12.2011
Сообщений: 226

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

04.02.2013, 17:21. Просмотров 750. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru