skull87
17-06-2008, 12:06
Ciao a tutti, vi allego un esercizio, penso che dal punto di vista dell'algoritmo che lavora sull'albero non ci siano problemi, ma non sono riuscito a far andare in controllo di quante cifre di un numero sono presenti in un altro, ho cercato di fare qualcosa ma con scarsissimi risultati, vi allego la traccia ed il mio codice.
Il file albero.txt di parteza può essere 312 124 458 114 320 123 586 4178
La funzione interessata è int somma(PAnodo);
/*
Note : Dato un albero binario le cui chiavi sono interi,
determinare la somma delle chiavi dei nodi che hanno
almeno due cifre in comune con almeno uno dei due figli.
*/
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
#define TIPO_DATO int
#define OFFSET_SPACE 5
struct node {
int key;
struct node* left;
struct node* right;
};
struct node1{
TIPO_DATO *info; //Puntatore all'informazione tenuta dal nodo
struct node1 *left; //Puntatore sinistro
struct node1 *right; //Puntatore destro
};
struct elemCoda{
struct node1 *elem;
struct elemCoda *next;
};
struct Anodo{
int key;
Anodo *left,*right;
};
typedef Anodo *PAnodo;
using namespace std;
void StampaBST(PAnodo ,int );
void CreaAlberoDaFile(PAnodo &);
PAnodo AlberoCasualebst(int ); //Generazione Alberi Casuali Ord
void InsertSort2( PAnodo &,int , bool &);
void DammiChiave(PAnodo ,int &);
void writeLevelTree(struct node1 *root); //Per Stampa Grafica
struct node1 *buildTree(); //Per Stampa Grafica
struct node1 *insertInOrder(struct node1 *root, TIPO_DATO info); //Per Stampa Grafica
void pfileorder(PAnodo );
int Altezza(PAnodo );
int somma(PAnodo);
int main(){
PAnodo A,B;
struct node1 *root = NULL;
CreaAlberoDaFile(A);
//StampaBST(A,0);
//system("pause");
//Crea albero
printf("\n\t\t .: 1 :. Costruzione albero...\n");
root = buildTree();
if (root==NULL) return 1;
//Stampa albero per livelli
system("cls");
writeLevelTree (root);
printf("\n\n\n");
system("pause");
cout<<"Somma: "<<somma(A)<<endl;
system("pause");
return 0;
}
int somma(PAnodo A){
if(A->left!=NULL || A->right!=NULL){
int i=0,conta=0;
char* temp=(char*)A->key;
cout<<temp<<endl;
int n=0;
while(temp[n]!='\0') n++;
system("pause");
if(A->left!=NULL){ string temp1=(char*)A->left->key;
for(i=0;i<n-1;i++){
if(temp1.find(temp[i])) conta++;
}}
if(conta<2 && A->right!=NULL){
string temp1=(char*)A->right->key;
for(i=0;i<n-1;i++){
if(temp1.find(temp[i])) conta++;
}
}
if(conta>=2) return somma(A->left)+somma(A->right)+A->key;
else return somma(A->left)+somma(A->right);
}}
int Altezza(PAnodo A)
{ // CALCOLA L’ALTEZZA DELL’ALBERO A
int Hs, Hd;
if (A==NULL)
return -1;
else {
Hs=Altezza(A->left); Hd=Altezza(A->right);
if (Hs > Hd)
return ++Hs;
else
return ++Hd;
}
}
void visita(PAnodo a, int livello, int i, ofstream &outlista) {
// Check Livello
if (i == livello) {
outlista<<a->key<<"\t";
return;
}
// Incrementa contatore livello
i++;
// Visita Nodo Sinistro
if (a->left != NULL)
visita(a->left, livello, i,outlista);
// Visita Nodo Destro
if (a->right != NULL)
visita(a->right, livello, i,outlista);
}
void pfileorder(PAnodo Tree){
int num;
//cout<<"Salva Albero su FILE:"<<endl;
string NomeLn,NomeOut;
ifstream filista;
ofstream outlista;
NomeOut="albero.txt";
outlista.open(NomeOut.c_str());
if(!outlista){
cerr<<"Non si puo' aprire il file!"<<endl;
system("pause");
}
for(int k=0;k<=Altezza(Tree);k++)
visita(Tree,k,0,outlista);
outlista.close();
}
void DammiChiave(PAnodo TNode, int &TheKey)
{ //ritorna il key field del nodo puntato da Tnode, se Tnode è
// NULL allora ritorna il valore di -100
if (TNode != NULL )
TheKey= TNode ->key;
else
TheKey= -100;
}
void StampaBST(PAnodo Tree,int i){
if(Tree!=NULL){
StampaBST(Tree->right,i+1);
for(int j=1;j<=i;j++)
cout<<" ";
cout<<Tree->key;
cout<<endl;
StampaBST(Tree->left,i+1);
}
}
void CreaAlberoDaFile(PAnodo &Tree){
int num;
cout<<"Crea Albero da FILE:"<<endl;
Tree=NULL;
string NomeLn,NomeOut;
ifstream filista;
ofstream outlista;
NomeLn="albero.txt";
filista.open(NomeLn.c_str());
if(!filista){
cerr<<"Non si puo' aprire il file!"<<endl;
system("pause");
}
filista>>num;
while (!filista.eof()) {
bool temp=false;
InsertSort2( Tree, num, temp);
if (temp==false) cout<<"Numero preesistente ="<<num<<endl;
else cout<<" Inserito numero= "<<num<<endl;
filista>>num;;
}
system("pause");
filista.close();
}
void InsertSort2( PAnodo &A,int m, bool &inserito) { //OK
if(A==NULL) {
A=new Anodo;
A->key = m;
A->left=NULL;
A->right=NULL;
inserito=true;
}
else if(A->key<m) InsertSort2(A->right,m,inserito);
else if(A->key>m) InsertSort2(A->left,m,inserito);
else inserito=false;
}
/*
Helper function that allocates a new node
with the given data and NULL left and right
pointers.
*/
struct node* NewNode(int data) {
struct node* node = new(struct node); // "new" is like "malloc"
node->key = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/*
Give a binary search tree and a number, inserts a new node
with the given number in the correct place in the tree.
Returns the new root pointer which the caller should
then use (the standard trick to avoid using reference
parameters).
*/
struct node* insert(struct node* node, int data) {
// 1. If the tree is empty, return a new, single node
if (node == NULL) {
return(NewNode(data));
}
else {
// 2. Otherwise, recur down the tree
if (data <= node->key) node->left = insert(node->left, data);
else node->right = insert(node->right, data);
return(node); // return the (unchanged) node pointer
}
}
struct node1 *buildTree(){
/* int info;
struct node1 *root = NULL;
for(;info!=0;){
printf("\n\tInserire elementi (0 per terminare): ");
scanf("%d",&info);
if (info!=0){
printf("\tInserisco elemento %d nell'albero\n",info);
root = insertInOrder(root,info);
}
}
return root;*/
int num;
cout<<"Crea Albero da FILE:"<<endl;
struct node1 *root=NULL;
string NomeLn,NomeOut;
ifstream filista;
ofstream outlista;
NomeLn="albero.txt";
filista.open(NomeLn.c_str());
if(!filista){
cerr<<"Non si puo' aprire il file!"<<endl;
system("pause");
}
filista>>num;
while(!filista.eof()){
root = insertInOrder(root,num);
filista>>num;
}
filista.close();
return root;
}
/* 2 */
/* 2.1 */
struct node1 *newNode(TIPO_DATO x){
struct node1 *elem = (struct node1 *)malloc (sizeof(struct node1));
TIPO_DATO *info = (TIPO_DATO *)malloc (sizeof(TIPO_DATO));
if ((elem==NULL)||(info==NULL)) return NULL;
*info = x;
elem->info = info;
elem->left = NULL;
elem->right = NULL;
return elem;
}
struct node1 *insertInOrder(struct node1 *root, TIPO_DATO info){
//Caso base
if (root == NULL) return (newNode(info));
//Ricorsione
if (info > *(root->info))
root->right = insertInOrder(root->right, info);
else
root->left = insertInOrder(root->left, info);
return root;
}
/* 5 */
/* 5.1 */
/* Restituisce il numero di livelli dell'albero */
/* (Necessario per una corretta spaziatura) */
int contaLivelli(struct node1 *root, int nLeft, int nRight){
int x,y;
if (root==NULL) return 0;
x = contaLivelli(root->left, nLeft+1, nRight);
y = contaLivelli(root->right, nLeft, nRight+1);
if (x>y) return (x+1);
return (y+1);
}
/* 5.2 */
/* Inserisce in coda alla lista puntata da "coda" il nodo x */
struct elemCoda *insertInTail(struct elemCoda *coda,struct node1 *x){
struct elemCoda *tmp = (struct elemCoda *) malloc (sizeof(struct elemCoda));
struct elemCoda *conta;
if (tmp==NULL) return NULL;
if (x==NULL){
tmp->elem = NULL;
tmp->next = NULL;
} else{
tmp->elem = x;
tmp->next = NULL;
}
if (coda==NULL) return tmp;
for(conta=coda;conta->next!=NULL;conta=conta->next);
conta->next = tmp;
return coda;
}
void writeLevelTree (struct node1 *root){
struct elemCoda *coda=NULL,
*tmp=NULL;
/* Per una "corretta" spaziatura */
int nLevel, //#livelli
nNodesCurrentLevel, //#nodi del livello correntemente elaborato
currentLevel=0, //#livello correntemente elaborato
conta, //var. per ciclo spaziatura
nCurrentNode=0; //#nodo correntemente in esame
//Calcolo numero livelli dell'albero
nLevel = contaLivelli(root,1,1); /* 5.1 */
//Inserimento radice albero in coda alla lista
coda = insertInTail(coda,root); /* 5.2 */
//Fin quando la coda dei nodi è piena...
for(;coda!=NULL;){
nNodesCurrentLevel=(int)pow (2, currentLevel); //#nodi del corrente livello (per spaziatura)
++nCurrentNode; //#nodo corrente rispetto al livello (per spaziatura)
//Spaziatura prima del valore del nodo
for (conta=0; conta<(OFFSET_SPACE*nLevel/nNodesCurrentLevel); ++conta)
printf(" ");
//Valore del nodo (se il nodo non esiste, NULL, due spazi)
if (coda->elem!=NULL)
printf("%d",*(coda->elem->info));
else printf(" ");
//Spaziatura dopo il valore del nodo
for (conta=0; conta<(OFFSET_SPACE*nLevel/nNodesCurrentLevel); ++conta)
printf(" ");
//Se sono stati stampati tutti i nodi di questo livello
// vai a capo, azzera il #nodo corrente e incrementa
// il valore del livello corrente
if (nCurrentNode == nNodesCurrentLevel){
currentLevel++;
nCurrentNode=0;
//cout<<"\n L "<<currentLevel<<" \n";
printf("\n\n\n");
}
//Inserisci in coda i due figli (destro e sinistro) del nodo corrente.
tmp = coda;
coda = coda->next;
if (tmp->elem!=NULL){
coda = insertInTail(coda,tmp->elem->left);
coda = insertInTail(coda,tmp->elem->right);
} else
//Se il nodo corrente è NULL e questo in corso di elaborazione
// non è l'ultimo livello, inserisci in coda due figli NULL
// (destro e sinistro del nodo NULL) in coda (per una
// "corretta" spaziatura)
if (currentLevel<nLevel-1){
coda = insertInTail(coda,NULL);
coda = insertInTail(coda,NULL);
}
}
}
Graze 1000 a tutti
Il file albero.txt di parteza può essere 312 124 458 114 320 123 586 4178
La funzione interessata è int somma(PAnodo);
/*
Note : Dato un albero binario le cui chiavi sono interi,
determinare la somma delle chiavi dei nodi che hanno
almeno due cifre in comune con almeno uno dei due figli.
*/
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
#define TIPO_DATO int
#define OFFSET_SPACE 5
struct node {
int key;
struct node* left;
struct node* right;
};
struct node1{
TIPO_DATO *info; //Puntatore all'informazione tenuta dal nodo
struct node1 *left; //Puntatore sinistro
struct node1 *right; //Puntatore destro
};
struct elemCoda{
struct node1 *elem;
struct elemCoda *next;
};
struct Anodo{
int key;
Anodo *left,*right;
};
typedef Anodo *PAnodo;
using namespace std;
void StampaBST(PAnodo ,int );
void CreaAlberoDaFile(PAnodo &);
PAnodo AlberoCasualebst(int ); //Generazione Alberi Casuali Ord
void InsertSort2( PAnodo &,int , bool &);
void DammiChiave(PAnodo ,int &);
void writeLevelTree(struct node1 *root); //Per Stampa Grafica
struct node1 *buildTree(); //Per Stampa Grafica
struct node1 *insertInOrder(struct node1 *root, TIPO_DATO info); //Per Stampa Grafica
void pfileorder(PAnodo );
int Altezza(PAnodo );
int somma(PAnodo);
int main(){
PAnodo A,B;
struct node1 *root = NULL;
CreaAlberoDaFile(A);
//StampaBST(A,0);
//system("pause");
//Crea albero
printf("\n\t\t .: 1 :. Costruzione albero...\n");
root = buildTree();
if (root==NULL) return 1;
//Stampa albero per livelli
system("cls");
writeLevelTree (root);
printf("\n\n\n");
system("pause");
cout<<"Somma: "<<somma(A)<<endl;
system("pause");
return 0;
}
int somma(PAnodo A){
if(A->left!=NULL || A->right!=NULL){
int i=0,conta=0;
char* temp=(char*)A->key;
cout<<temp<<endl;
int n=0;
while(temp[n]!='\0') n++;
system("pause");
if(A->left!=NULL){ string temp1=(char*)A->left->key;
for(i=0;i<n-1;i++){
if(temp1.find(temp[i])) conta++;
}}
if(conta<2 && A->right!=NULL){
string temp1=(char*)A->right->key;
for(i=0;i<n-1;i++){
if(temp1.find(temp[i])) conta++;
}
}
if(conta>=2) return somma(A->left)+somma(A->right)+A->key;
else return somma(A->left)+somma(A->right);
}}
int Altezza(PAnodo A)
{ // CALCOLA L’ALTEZZA DELL’ALBERO A
int Hs, Hd;
if (A==NULL)
return -1;
else {
Hs=Altezza(A->left); Hd=Altezza(A->right);
if (Hs > Hd)
return ++Hs;
else
return ++Hd;
}
}
void visita(PAnodo a, int livello, int i, ofstream &outlista) {
// Check Livello
if (i == livello) {
outlista<<a->key<<"\t";
return;
}
// Incrementa contatore livello
i++;
// Visita Nodo Sinistro
if (a->left != NULL)
visita(a->left, livello, i,outlista);
// Visita Nodo Destro
if (a->right != NULL)
visita(a->right, livello, i,outlista);
}
void pfileorder(PAnodo Tree){
int num;
//cout<<"Salva Albero su FILE:"<<endl;
string NomeLn,NomeOut;
ifstream filista;
ofstream outlista;
NomeOut="albero.txt";
outlista.open(NomeOut.c_str());
if(!outlista){
cerr<<"Non si puo' aprire il file!"<<endl;
system("pause");
}
for(int k=0;k<=Altezza(Tree);k++)
visita(Tree,k,0,outlista);
outlista.close();
}
void DammiChiave(PAnodo TNode, int &TheKey)
{ //ritorna il key field del nodo puntato da Tnode, se Tnode è
// NULL allora ritorna il valore di -100
if (TNode != NULL )
TheKey= TNode ->key;
else
TheKey= -100;
}
void StampaBST(PAnodo Tree,int i){
if(Tree!=NULL){
StampaBST(Tree->right,i+1);
for(int j=1;j<=i;j++)
cout<<" ";
cout<<Tree->key;
cout<<endl;
StampaBST(Tree->left,i+1);
}
}
void CreaAlberoDaFile(PAnodo &Tree){
int num;
cout<<"Crea Albero da FILE:"<<endl;
Tree=NULL;
string NomeLn,NomeOut;
ifstream filista;
ofstream outlista;
NomeLn="albero.txt";
filista.open(NomeLn.c_str());
if(!filista){
cerr<<"Non si puo' aprire il file!"<<endl;
system("pause");
}
filista>>num;
while (!filista.eof()) {
bool temp=false;
InsertSort2( Tree, num, temp);
if (temp==false) cout<<"Numero preesistente ="<<num<<endl;
else cout<<" Inserito numero= "<<num<<endl;
filista>>num;;
}
system("pause");
filista.close();
}
void InsertSort2( PAnodo &A,int m, bool &inserito) { //OK
if(A==NULL) {
A=new Anodo;
A->key = m;
A->left=NULL;
A->right=NULL;
inserito=true;
}
else if(A->key<m) InsertSort2(A->right,m,inserito);
else if(A->key>m) InsertSort2(A->left,m,inserito);
else inserito=false;
}
/*
Helper function that allocates a new node
with the given data and NULL left and right
pointers.
*/
struct node* NewNode(int data) {
struct node* node = new(struct node); // "new" is like "malloc"
node->key = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/*
Give a binary search tree and a number, inserts a new node
with the given number in the correct place in the tree.
Returns the new root pointer which the caller should
then use (the standard trick to avoid using reference
parameters).
*/
struct node* insert(struct node* node, int data) {
// 1. If the tree is empty, return a new, single node
if (node == NULL) {
return(NewNode(data));
}
else {
// 2. Otherwise, recur down the tree
if (data <= node->key) node->left = insert(node->left, data);
else node->right = insert(node->right, data);
return(node); // return the (unchanged) node pointer
}
}
struct node1 *buildTree(){
/* int info;
struct node1 *root = NULL;
for(;info!=0;){
printf("\n\tInserire elementi (0 per terminare): ");
scanf("%d",&info);
if (info!=0){
printf("\tInserisco elemento %d nell'albero\n",info);
root = insertInOrder(root,info);
}
}
return root;*/
int num;
cout<<"Crea Albero da FILE:"<<endl;
struct node1 *root=NULL;
string NomeLn,NomeOut;
ifstream filista;
ofstream outlista;
NomeLn="albero.txt";
filista.open(NomeLn.c_str());
if(!filista){
cerr<<"Non si puo' aprire il file!"<<endl;
system("pause");
}
filista>>num;
while(!filista.eof()){
root = insertInOrder(root,num);
filista>>num;
}
filista.close();
return root;
}
/* 2 */
/* 2.1 */
struct node1 *newNode(TIPO_DATO x){
struct node1 *elem = (struct node1 *)malloc (sizeof(struct node1));
TIPO_DATO *info = (TIPO_DATO *)malloc (sizeof(TIPO_DATO));
if ((elem==NULL)||(info==NULL)) return NULL;
*info = x;
elem->info = info;
elem->left = NULL;
elem->right = NULL;
return elem;
}
struct node1 *insertInOrder(struct node1 *root, TIPO_DATO info){
//Caso base
if (root == NULL) return (newNode(info));
//Ricorsione
if (info > *(root->info))
root->right = insertInOrder(root->right, info);
else
root->left = insertInOrder(root->left, info);
return root;
}
/* 5 */
/* 5.1 */
/* Restituisce il numero di livelli dell'albero */
/* (Necessario per una corretta spaziatura) */
int contaLivelli(struct node1 *root, int nLeft, int nRight){
int x,y;
if (root==NULL) return 0;
x = contaLivelli(root->left, nLeft+1, nRight);
y = contaLivelli(root->right, nLeft, nRight+1);
if (x>y) return (x+1);
return (y+1);
}
/* 5.2 */
/* Inserisce in coda alla lista puntata da "coda" il nodo x */
struct elemCoda *insertInTail(struct elemCoda *coda,struct node1 *x){
struct elemCoda *tmp = (struct elemCoda *) malloc (sizeof(struct elemCoda));
struct elemCoda *conta;
if (tmp==NULL) return NULL;
if (x==NULL){
tmp->elem = NULL;
tmp->next = NULL;
} else{
tmp->elem = x;
tmp->next = NULL;
}
if (coda==NULL) return tmp;
for(conta=coda;conta->next!=NULL;conta=conta->next);
conta->next = tmp;
return coda;
}
void writeLevelTree (struct node1 *root){
struct elemCoda *coda=NULL,
*tmp=NULL;
/* Per una "corretta" spaziatura */
int nLevel, //#livelli
nNodesCurrentLevel, //#nodi del livello correntemente elaborato
currentLevel=0, //#livello correntemente elaborato
conta, //var. per ciclo spaziatura
nCurrentNode=0; //#nodo correntemente in esame
//Calcolo numero livelli dell'albero
nLevel = contaLivelli(root,1,1); /* 5.1 */
//Inserimento radice albero in coda alla lista
coda = insertInTail(coda,root); /* 5.2 */
//Fin quando la coda dei nodi è piena...
for(;coda!=NULL;){
nNodesCurrentLevel=(int)pow (2, currentLevel); //#nodi del corrente livello (per spaziatura)
++nCurrentNode; //#nodo corrente rispetto al livello (per spaziatura)
//Spaziatura prima del valore del nodo
for (conta=0; conta<(OFFSET_SPACE*nLevel/nNodesCurrentLevel); ++conta)
printf(" ");
//Valore del nodo (se il nodo non esiste, NULL, due spazi)
if (coda->elem!=NULL)
printf("%d",*(coda->elem->info));
else printf(" ");
//Spaziatura dopo il valore del nodo
for (conta=0; conta<(OFFSET_SPACE*nLevel/nNodesCurrentLevel); ++conta)
printf(" ");
//Se sono stati stampati tutti i nodi di questo livello
// vai a capo, azzera il #nodo corrente e incrementa
// il valore del livello corrente
if (nCurrentNode == nNodesCurrentLevel){
currentLevel++;
nCurrentNode=0;
//cout<<"\n L "<<currentLevel<<" \n";
printf("\n\n\n");
}
//Inserisci in coda i due figli (destro e sinistro) del nodo corrente.
tmp = coda;
coda = coda->next;
if (tmp->elem!=NULL){
coda = insertInTail(coda,tmp->elem->left);
coda = insertInTail(coda,tmp->elem->right);
} else
//Se il nodo corrente è NULL e questo in corso di elaborazione
// non è l'ultimo livello, inserisci in coda due figli NULL
// (destro e sinistro del nodo NULL) in coda (per una
// "corretta" spaziatura)
if (currentLevel<nLevel-1){
coda = insertInTail(coda,NULL);
coda = insertInTail(coda,NULL);
}
}
}
Graze 1000 a tutti