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

@Элвиc · Регистрация: 26.04.2011

Author24 — интернет-сервис помощи студентам

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

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

C++

#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);
 
}

@fasked · 06.12.2011, 18:16

Сообщение от Элвиc

находит максимальное или минимальное значение записей вершин непустого дерева;

Максимальное значение всегда будет листом правого поддерева. Минимальное - левого. Ну или наоборот, в зависимости от конфигурации дерева.

@Thinker · 06.12.2011, 18:28

fasked, в дереве поиска да, но в произвольном дереве - нет.

Добавлено через 6 минут
Элвиc. могу дать дельный совет: для поиска максимального элемента используйте указатель на максимальный элемент, который сам определяется в функции, которая вызывает функцию поиска, тогда без проблем найдете. За начальное значение можно взять значение корня дерева.

@fasked · 06.12.2011, 18:48

Сообщение от Thinker

но в произвольном дереве - нет.

Прошу прощения, накосячил

C

#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 · 06.12.2011, 19:09 **[ТС]**

если не трудно можете мне написать рабочую структуру(она у меня называется "searchMax") которая будет искать отдельно максимальный и отдельно минимальный элемент именно в дереве. с помощью моей структуры он ищет максимальный но только в левой части дерева, а мне то нужно во всем...

@fasked · 06.12.2011, 19:12

Сообщение от Элвиc

рабочую структуру(она у меня называется "searchMax")

Не вижу такой структуры, есть функция.

Сообщение от Элвиc

если не трудно можете мне написать

Я Вам дал пример. Рассмотрите функции find_min и find_min_traveler и сделайте аналоги.

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	06.12.2011, 18:16	2
	Сообщение от Элвиc находит максимальное или минимальное значение записей вершин непустого дерева; Максимальное значение всегда будет листом правого поддерева. Минимальное - левого. Ну или наоборот, в зависимости от конфигурации дерева. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	06.12.2011, 18:28	3
	fasked, в дереве поиска да, но в произвольном дереве - нет. Добавлено через 6 минут Элвиc. могу дать дельный совет: для поиска максимального элемента используйте указатель на максимальный элемент, который сам определяется в функции, которая вызывает функцию поиска, тогда без проблем найдете. За начальное значение можно взять значение корня дерева. 1

@Элвиc 5 / 0 / 0 Регистрация: 26.04.2011 Сообщений: 18
	06.12.2011, 19:09 [ТС]	5
	если не трудно можете мне написать рабочую структуру(она у меня называется "searchMax") которая будет искать отдельно максимальный и отдельно минимальный элемент именно в дереве. с помощью моей структуры он ищет максимальный но только в левой части дерева, а мне то нужно во всем... 0

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	06.12.2011, 19:12	6
	Сообщение от Элвиc рабочую структуру(она у меня называется "searchMax") Не вижу такой структуры, есть функция. Сообщение от Элвиc если не трудно можете мне написать Я Вам дал пример. Рассмотрите функции find_min и find_min_traveler и сделайте аналоги. 0