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

Задача про Бинарные деревья! - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Элвиc
5 / 0 / 0
Регистрация: 26.04.2011
Сообщений: 18
06.12.2011, 17:59     Задача про Бинарные деревья! #1
здрасти! помогите плиз с задачей! я вот начал писать и столкнулся с проблемами...
вот задание:

Записи вершин дерева - вещественные числа. Описать процедуру или функцию, которая:
находит максимальное или минимальное значение записей вершин непустого дерева;

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
#include <iostream>
 
using namespace std;
 
struct tree 
{
  int info;
  tree *left;
  tree *right;
};
 
struct tree *root1; 
 
struct tree *stree(struct tree *root, struct tree *r, int info)
{
 
  if(!r) 
  {
    r = (struct tree *) malloc(sizeof(struct tree));
    r->left = NULL;
    r->right = NULL;
    r->info = info;
    if(!root) return r; /* первый вход */
    if(info < root->info) root->left = r;
    else root->right = r;
    return r;
  }
 
  if(info < r->info)
    stree(r, r->left, info);
  else
    stree(r, r->right, info);
 
  return root;
}
 
void print_tree(struct tree *r, int l)
{
  int i;
 
  if(!r) return;
 
  print_tree(r->right, l+1);
  for(i=0; i<l; ++i) cout<<"   ";
  cout<<r->info;
  cout<<endl;
  print_tree(r->left, l+1);
}
void searchMax(struct tree *r, int l,int m)
{
cout<<m<<endl;
if(!r) return;
 
 
  if(m<r->info) 
 m=r->info;
 searchMax(r->right, l+1,m);
  
 if(m<r->info) 
 m=r->info;
 
 searchMax(r->left, l+1,m);
 if(m<r->info) 
 m=r->info;
 cout<<m<<endl;
}
void main()
{
  //int s;
  int n=8;
  int a[8];
  cout<<"enter";
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  }
  root1 = NULL; 
  for (int i=0; i<n; i++)
  {
     root1 = stree(root1, root1, a[i]);
  }
  cout<<endl<<"print tree"<<endl;
  print_tree(root1, 0);
 
  int max=a[0];
searchMax(root1,0,max);
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.12.2011, 17:59     Задача про Бинарные деревья!
Посмотрите здесь:

C++ бинарные деревья
Бинарные деревья C++
Бинарные деревья C++
C++ Бинарные деревья
C++ бинарные деревья
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
06.12.2011, 18:16     Задача про Бинарные деревья! #2
Цитата Сообщение от Элвиc Посмотреть сообщение
находит максимальное или минимальное значение записей вершин непустого дерева;
Максимальное значение всегда будет листом правого поддерева. Минимальное - левого. Ну или наоборот, в зависимости от конфигурации дерева.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
06.12.2011, 18:28     Задача про Бинарные деревья! #3
fasked, в дереве поиска да, но в произвольном дереве - нет.

Добавлено через 6 минут
Элвиc. могу дать дельный совет: для поиска максимального элемента используйте указатель на максимальный элемент, который сам определяется в функции, которая вызывает функцию поиска, тогда без проблем найдете. За начальное значение можно взять значение корня дерева.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
06.12.2011, 18:48     Задача про Бинарные деревья! #4
Цитата Сообщение от Thinker Посмотреть сообщение
но в произвольном дереве - нет.
Прошу прощения, накосячил

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
#include <stdio.h>
 
struct btree_node {
   double data;
   struct btree_node *left;
   struct btree_node *right;
};
 
void find_min_traveler(struct btree_node *node, double *min) {
   if (node) {
      if (*min > node->data)
         *min = node->data;
         
      find_min_traveler(node->left, min);
      find_min_traveler(node->right, min);
   }
}
 
double find_min(struct btree_node *node) {
   double min = node->data;
   find_min_traveler(node, &min);
   
   return min;
}
 
void NODE_INIT(struct btree_node *node, double data, struct btree_node *left, struct btree_node *right) {
   (node)->data  = data, (node)->left  = left, (node)->right = right;
}
 
int main() {
   /* Tree init */
   struct btree_node nodes[6] = { { 0 } };
   struct btree_node *root = nodes;
 
   NODE_INIT(nodes + 3, 3.0, NULL, NULL);
   NODE_INIT(nodes + 4, 0.1, NULL, NULL);
   NODE_INIT(nodes + 5, 0.2, NULL, NULL);
   NODE_INIT(nodes + 1, 2.5, nodes + 3, NULL);
   NODE_INIT(nodes + 0, 1.5, nodes + 1, nodes + 2);
   NODE_INIT(nodes + 2, 1.0, nodes + 4, nodes + 5);
 
   /* Find min */
   printf("min = %lf\n", find_min(root));
   return 0;
}
На скорую руку. Но а вообще лучше возвращать указатель на узел с минимальным элементом.
Элвиc
5 / 0 / 0
Регистрация: 26.04.2011
Сообщений: 18
06.12.2011, 19:09  [ТС]     Задача про Бинарные деревья! #5
если не трудно можете мне написать рабочую структуру(она у меня называется "searchMax") которая будет искать отдельно максимальный и отдельно минимальный элемент именно в дереве. с помощью моей структуры он ищет максимальный но только в левой части дерева, а мне то нужно во всем...
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
06.12.2011, 19:12     Задача про Бинарные деревья! #6
Цитата Сообщение от Элвиc Посмотреть сообщение
рабочую структуру(она у меня называется "searchMax")
Не вижу такой структуры, есть функция.
Цитата Сообщение от Элвиc Посмотреть сообщение
если не трудно можете мне написать
Я Вам дал пример. Рассмотрите функции find_min и find_min_traveler и сделайте аналоги.
Yandex
Объявления
06.12.2011, 19:12     Задача про Бинарные деревья!
Ответ Создать тему
Опции темы

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