Операции над элементами бинарного дерева(заменить корневой и максимальный)

[Bombucho]

Всем привет, пробовал гуглить, но ничего внятного для себя не нашел...

#include <iostream>
#include <cstdlib>
using namespace std;
//Наша структура
struct node
{
    int info; 
    node *l, *r;//Левая и Правая часть дерева
};
 
node * tree=NULL; //Объявляем переменную, типа структура дерево
 
//запись элемента в дерево
void push(int a,node **t)
{
    if ((*t)==NULL) //Если дерева не существует
    {
        (*t)=new node; 
        (*t)->info=a; 
        (*t)->l=(*t)->r=NULL; 
        return ;
    }
       //если дерево существует
        if (a>(*t)->info) push(a,&(*t)->r); //Если аргумент а больше, кладем его вправо
        else push(a,&(*t)->l); //Если меньше,то влево
}
 
//вывод дерева
void print (node *t,int u) 
{
    if (t==NULL) return; 
    else //Иначе
    {
    print(t->l,++u);
    for (int i=0;i<u;++i) cout<<"|";
    cout<<t->info<<endl; т
    u--;
    }
    print(t->r,++u); 
}
 
 //подсчет максимального элемента
 node*  maximum(node *t,int)
 {
   
   while(t->r)
   {
   t=t->r;
   }
   return t;
 }
 

 
 
int main ()
{   
    int n; //Количество элементов
    int s; //элемент(число) дерева
    cout<<"Введите количество элементов  ";
    cin>>n;
 
    for (int i=0;i<n;++i)
    {
    cout<<"ведите число  ";
    cin>>s;
    push(s,&tree); 
    }
    cout<<"Бинарное дерево"<<endl;
    print(tree,0);
}

[New man]

 //подсчет максимального элемента
 node*  maximum(node *t,int)
 {
   
   while(t->r)
   {
   t=t->r;
   }
   return t;
 }

По-моему, это не то. Ты идёшь только по правым ветвям.

Тут, скорее,

node*  maximum(node *t,int)
{
   node* result = t;
   if(t->r){
     node* tmp = maximum (t->r);
     if(tmp->info > result->info)
          result = tmp;
   }
    if(t->l)
   {
      node* tmp = maximum(t->l);
      if(tmp ->info > result->info)
          result = tmp ;
   }
   if(t->info > result->info)
        result = t;
   return result;
}

И да, зачем push принимает на вход указатель на указатель?

[Bombucho]

Сообщение от New man

И да, зачем push принимает на вход указатель на указатель?

Но ведь нужно поменять местами максимальное, а максимальное это последнее число по правым ветвям,верно же?

[Bombucho]

Сообщение от New man

И да, зачем push принимает на вход указатель на указатель?

Банально выбивало ошибку...

[New man]

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

Но ведь нужно поменять местами максимальное, а максимальное это последнее число по правым ветвям,верно же?

Это неверно для дерева в общем случае.

Нигде в условии не сказано, что дерево имеет какую-то особую структуру.

[Bombucho]

А вот насчет замены корневого и максимального, нужно создавать новую функцию по замене или можно прямо в функции поиска максимального элемента?

[Bombucho]

Сообщение от New man

Это неверно для дерева в общем случае.
Нигде в условии не сказано, что дерево имеет какую-то особую структуру.

Ну ведь это обычное бинарное дерево и наверное логичнее будет пользоваться таким

node* maximum(node *t,int) 
{ 
while(t->r!=NULL) 
{ 
t=t->r; 
} 
return t; 
}

Но вопрос остается открыт , как поменять местами максимальный и корневой элемент.

[New man]

Что ты имеешь в виду под "обычным"?

Как минимум, то, что ты говоришь, не верно, так как у тебя максимум будет в корне. А значит, само дерево не обязательно отсортированное.

[pu4koff]

Так у вас бинарное дерево - это двоичное дерево поиска, у которого все элементы левого поддерева меньше корня, а правого - больше?
Если так, то максимум - действительно самый правый элемент и поиск максимума выглядит правильным.
По поводу замены - тут два варианта:
1) Самый правый элемент является листом, т.е. у него нет и левого поддерева.
Тогда просто в левое поддерево ему суём текущий корень и назначаем максимум корнем (не забываем удалить максимум из правого поддерева его корня)
2) У максимума есть левое поддерево. Тут вот всё сложно может быть, как бы дерево перестраивать не пришлось.

[Bombucho]

Сообщение от New man

Что ты имеешь в виду под "обычным"?

Товарищ pu4koff более ясно выразил мою мысль(самый последний элемент правой части = максимальный).