Sto cercando di risolvere alberi solo che la soluzione che stavo scrivendo mi da problemi, precisamente va fuori memoria, penso di aver anche individuato il punto che causa l’errore (ho messo un commento) mi potreste aiutare a capire il perché.
Questo è il codice grazie in anticipo!
EDIT: Risolto il fuori memoria ma ora è sbagliato il modo in cui inserisci i nodi e questo dipende dal fatto che, non so il perché, quasi tutti i nodi hanno come padre la radice, mi potreste aiutare a trovare l’errore ho messo il codice aggiornato
#include <bits/stdc++.h>
#define MAXN 1000010
using namespace std;
struct nodo{
int info;
nodo* parent;
nodo* sx;
nodo* dx;
};
int N;
int pre[MAXN];
int post[MAXN];
int sim[MAXN];
void pre_order(nodo* p){
if(p!=NULL){
cout<<p->info<<" ";
pre_order(p->sx);
pre_order(p->dx);
}
}
void insert_tree(int pos ,nodo* &padre ,nodo* &p ,int POS[] , int N){
/*cout<<p->info<<" ";
if(p->parent!=NULL){
cout<<p->parent->info;
}
cout<<endl;*///questa parte commentata è solo per controllare in che nodo si trovi e qual è il suo padre
if(p==NULL){
p=new nodo;
p->info=pos;
p->parent=padre;
p->sx=NULL;
p->dx=NULL;
}
else{
int* it=find(POS,POS+N,pos);
int* itn=find(POS,POS+N,p->info);
if(it-POS<itn-POS){
if(p->sx==NULL){
p->sx=new nodo;
p->sx->info=pos;
p->sx->parent=padre;
p->sx->sx=NULL;
p->sx->dx=NULL;
}
insert_tree(pos,p,p->sx,POS,N);//il fuori memoria è qui
}
else{
if(it-POS>itn-POS){
if(p->parent->dx==NULL){
p->parent->dx=new nodo;
p->parent->dx->info=pos;
p->parent->dx->parent=padre;
p->parent->dx->sx=NULL;
p->parent->dx->dx=NULL;
}
insert_tree(pos,p->parent,p->parent->dx,POS,N);//il fuori memoria è qui
}
}
}
}
void visita(int N, int *PRE, int *POST, int *SIMM){
nodo* root=NULL;
root=new nodo;
root->info=PRE[0];
root->parent=NULL;
//root->parent->info=0;
root->sx=new nodo;
root->sx->parent=root;
root->sx->info=PRE[1];
root->sx->sx=NULL;
root->sx->dx=NULL;
root->dx=new nodo;
root->dx->parent=root;
root->dx->info=POST[N-2];
root->dx->sx=NULL;
root->dx->dx=NULL;
for(int i=2;i<N;i++){
//stampo la visita solo per vedere in che situazione si trova l'albero
pre_order(root);
cout<<endl;
insert_tree(PRE[i],root->parent,root,POST,N);
}
//stampo questa visita solo per controllare che l'albero sia stato costruito bene
pre_order(root);
}
int main(){
cin>>N;
for(int i=0;i<N;i++){
cin>>pre[i];
}
for(int i=0;i<N;i++){
cin>>post[i];
}
visita(N,pre,post,sim);
}