[C++]Visita di un albero binario

[TheBestNapoli]

Salve a tutti, mi sto avventurando nel modo delle strutture dati un po' più complicate e devo sviluppare un programma che permette una visita per livelli di un albero binario... ho gia un programma che effettua le visite in preordine, postordine e simmetrica e devo aggiungere la visita per livelli (o in ampiezza). Il programma che già ho è formato dai file:
TreeNode.h
Tree.h
main.cpp
per implementare la visita per livelli ho bisogno della classe Coda e quindi devo aggiungere anche i file:
ListNode.h
List.h
Queue.h
Di seguito vi mostro tutti i file:
ListNode.h

#ifndef LISTNODE_H_
#define LISTNODE_H_

template< class NODETYPE > class List;
template< class NODETYPE >
class ListNode{
		friend class List< NODETYPE >;
	public:
		ListNode(const NODETYPE &);
		NODETYPE getData()const;
	private:
		NODETYPE data;
		ListNode< NODETYPE > *nextPtr;
};

template< class NODETYPE >
ListNode< NODETYPE >::ListNode(const NODETYPE &info) : data(info), nextPtr(0){}

template< class NODETYPE >
NODETYPE ListNode< NODETYPE>::getData()const
{
	return data;
}

#endif /* LISTNODE_H_ */

List.h

#ifndef LIST_H_
#define LIST_H_
#include <iostream>
#include <assert.h>
#include "ListNode.h"

using namespace std;

template< class NODETYPE >
class List{
	public:
		List();
		~List();
		void insertAtFront(const NODETYPE &);
		void insertAtBack(const NODETYPE &);
		bool removeFromFront(NODETYPE &);
		bool removeFromBack(NODETYPE &);
		bool isEmpty()const;
		void print()const;
	private:
		ListNode< NODETYPE > *firstPtr;
		ListNode< NODETYPE > *lastPtr;
		ListNode< NODETYPE > *getNewNode(const NODETYPE &);
};

template< class NODETYPE >
List< NODETYPE >::List() : firstPtr(0), lastPtr(0){}

template< class NODETYPE >
List< NODETYPE >::~List()
{
	if(!isEmpty())
	{
		cout<<"Distruzione nodi...\n";
		ListNode< NODETYPE> *currentPtr = firstPtr, *tempPtr;
		while(currentPtr != 0)
		{
			tempPtr = currentPtr;
			cout<<tempPtr -> data<<endl;
			currentPtr = currentPtr -> nextPtr;
			delete tempPtr;

		}
	}
	cout<<"Tutti i nodi sono stati distrutti\n\n";
}

template< class NODETYPE >
void List< NODETYPE >::insertAtFront(const NODETYPE &value)
{
	ListNode< NODETYPE > *newPtr = getNewNode(value);
	if(isEmpty())
	{
		firstPtr = lastPtr = newPtr;
	}
	else
	{
		newPtr -> nextPtr = firstPtr;
		firstPtr = newPtr;
	}
}

template< class NODETYPE >
void List< NODETYPE >::insertAtBack(const NODETYPE &value)
{
	ListNode< NODETYPE > *newPtr = getNewNode(value);
	if(isEmpty())
	{
		firstPtr = lastPtr = newPtr;
	}
	else
	{
		lastPtr -> nextPtr = newPtr;
		lastPtr = newPtr;
	}
}

template< class NODETYPE >
bool List< NODETYPE >::removeFromFront(NODETYPE &value)
{
	if(isEmpty())
	{
		return false;
	}
	else
	{
		ListNode< NODETYPE > *tempPtr = firstPtr;
		if(firstPtr == lastPtr)
		{
			firstPtr = lastPtr = 0;
		}
		else
		{
			firstPtr = firstPtr -> nextPtr;
		}
		value = tempPtr -> data;
		delete tempPtr;
		return true;
	}
}

template< class NODETYPE >
bool List< NODETYPE >::removeFromBack(NODETYPE &value)
{
	if(isEmpty())
	{
		return false;
	}
	else
	{
		ListNode< NODETYPE > *tempPtr = lastPtr;
		if(firstPtr == lastPtr)
		{
			firstPtr = lastPtr = 0;
		}
		else
		{
			ListNode< NODETYPE > *currentPtr = firstPtr;
			while(currentPtr -> nextPtr != lastPtr)
			{
				currentPtr = currentPtr -> nextPtr;
			}
			lastPtr = currentPtr;
			currentPtr -> nextPtr = 0;
		}
		value = tempPtr -> data;
		delete tempPtr;
		return true;
	}
}

template< class NODETYPE >
bool List< NODETYPE >::isEmpty()const
{
	return firstPtr == 0;
}

template< class NODETYPE >
ListNode< NODETYPE > *List< NODETYPE >::getNewNode(const NODETYPE &value)
{
	ListNode< NODETYPE > *ptr = new ListNode< NODETYPE >(value);
	assert(ptr != 0);
	return ptr;
}

template< class NODETYPE >
void List< NODETYPE >::print()const
{
	if(isEmpty())
	{
		cout<<"La lista e' vuota\n\n";
		return;
	}
	ListNode< NODETYPE > *currentPtr = firstPtr;
	cout<<"La lista e': ";
	while(currentPtr != 0)
	{
		cout<<currentPtr -> data<<" ";
		currentPtr = currentPtr -> nextPtr;
	}
	cout<<endl<<endl;
}

#endif /* LIST_H_ */

Queue.h

#ifndef QUEUE_H_
#define QUEUE_H_
#include "List.h"

template< class QUEUETYPE >
class Queue : private List< QUEUETYPE >{
	public:
		void enqueue(const QUEUETYPE &d) {insertAtBack(d);}
		bool dequeue(QUEUETYPE &d) {return removeFromFront(d);}
		bool isQueueEmpty()const {return isEmpty();}
		void printQueue()const {print();}
};

#endif /* QUEUE_H_ */

TreeNode.h

#ifndef TREENODE_H_
#define TREENODE_H_

template< class NODETYPE > class Tree;
template< class NODETYPE >
class TreeNode{
		friend class Tree< NODETYPE >;
	public:
		TreeNode(const NODETYPE &d) : leftPtr(0), data(d), rightPtr(0){}
		NODETYPE getData()const {return data;}
	private:
		TreeNode< NODETYPE > *leftPtr;
		NODETYPE data;
		TreeNode< NODETYPE > *rightPtr;
};

#endif /* TREENODE_H_ */

Tree.h

#ifndef TREE_H_
#define TREE_H_
#include <iostream>
#include <assert.h>
#include "TreeNode.h"
#include "Queue.h"

using namespace std;

template< class NODETYPE >
class Tree{
	public:
		Tree();
		void insertNode(const NODETYPE &);
		void preOrderTraversal()const;
		void inOrderTraversal()const;
		void postOrderTraversal()const;
	private:
		TreeNode <NODETYPE> *rootPtr;
		void insertNodeHelper(TreeNode< NODETYPE > **, const NODETYPE &);
		void preOrderHelper(TreeNode< NODETYPE > *)const;
		void inOrderHelper(TreeNode< NODETYPE > *)const;
		void postOrderHelper(TreeNode< NODETYPE > *)const;
};

template< class NODETYPE >
Tree< NODETYPE >::Tree()
{
	rootPtr = 0;
}

template< class NODETYPE >
void Tree< NODETYPE >::insertNode(const NODETYPE &value)
{
	insertNodeHelper(&rootPtr,value);
}

template< class NODETYPE >
void Tree< NODETYPE >::insertNodeHelper(TreeNode< NODETYPE > **ptr, const NODETYPE &value)
{
	if(*ptr == 0)
	{
		*ptr = new TreeNode< NODETYPE >(value);
		assert(*ptr != 0);
	}
	else
	{
		if(value < (*ptr) -> data)
		{
			insertNodeHelper(&((*ptr) -> leftPtr), value);
		}
		else
		{
			if(value > (*ptr) -> data)
			{
				insertNodeHelper(&((*ptr) -> rightPtr), value);
			}
			else
			{
				cout<<value<<" dup"<<endl;
			}
		}
	}
}

template< class NODETYPE >
void Tree< NODETYPE >::preOrderTraversal()const
{
	preOrderHelper(rootPtr);
}

template< class NODETYPE >
void Tree< NODETYPE >::preOrderHelper(TreeNode< NODETYPE > *ptr)const
{
	if(ptr != 0)
	{
		cout<<ptr -> data<<" ";
		preOrderHelper(ptr -> leftPtr);
		preOrderHelper(ptr -> rightPtr);
	}
}

template< class NODETYPE >
void Tree< NODETYPE >::inOrderTraversal()const
{
	inOrderHelper(rootPtr);
}

template< class NODETYPE >
void Tree< NODETYPE >::inOrderHelper(TreeNode< NODETYPE > *ptr)const
{
	if(ptr != 0)
	{
		inOrderHelper(ptr -> leftPtr);
		cout<<ptr -> data<<" ";
		inOrderHelper(ptr -> rightPtr);
	}
}

template< class NODETYPE >
void Tree< NODETYPE >::postOrderTraversal()const
{
	postOrderHelper(rootPtr);
}

template< class NODETYPE >
void Tree< NODETYPE >::postOrderHelper(TreeNode< NODETYPE > *ptr)const
{
	if(ptr != 0)
	{
		postOrderHelper(ptr -> leftPtr);
		postOrderHelper(ptr -> rightPtr);
		cout<<ptr -> data<<" ";
	}
}

#endif /* TREE_H_ */

main.cpp

#include "Tree.h"

int main()
{
	Tree< int > intTree;
	int intVal;
	cout<<"Inserisci 10 valori interi:\n";
	for(int i=0;i<7;i++)
	{
		cin>>intVal;
		intTree.insertNode(intVal);
	}
	cout<<"PreOrder Traversal\n";
	intTree.preOrderTraversal();
	cout<<"\nInOrder Traversal\n";
	intTree.inOrderTraversal();
	cout<<"\nPostOrder Traversal\n";
	intTree.postOrderTraversal();
	return 0;
}

Per quanto riguarda la funzione della visita per livelli ho capito il procedimento che bisogna seguire: in pratica si utilizza un oggetto coda, si inserisce nella coda il nodo radice, poi finchè la coda non è vuota viene estratto il nodo che è in testa alla coda e viene visualizzato, se il puntatore del figlio di sinitra è diverso da NULL si inserisce nela coda il nodo di sinistra e analogo procedimento con il figlio di destra:
in Tree.h includo il file Queue.h e inserisco le funzioni membro levelOrderTraversal() e levelOrderHelper() all'interno della classe; l'implementazione che ho fatto però mi dà alcuni errori:

template< class NODETYPE >
void Tree< NODETYPE >::levelOrderTraversal()const
{
	levelOrderHelper(rootPtr);
}

template< class NODETYPE >
void Tree< NODETYPE >::levelOrderHelper(TreeNode< NODETYPE > *rootNode)const
{
	Queue< TreeNode < NODETYPE >* > queue;
	TreeNode< NODETYPE > *traverse;
	queue.enqueue(rootNode);
	while(!queue.isQueueEmpty())
	{
		traverse = queue.dequeue();
		queue.printQueue();
		if(traverse -> leftPtr != NULL)
		{
			queue.enqueue(traverse -> leftPtr);
		}
		if(traverse -> rightPtr != NULL)
		{
			queue.enqueue(traverse -> rightPtr);
		}
	}
}

gli errori sono nel file Queue.h

there are no arguments to 'isEmpty' that depend on a template parameter, so a declaration of 'isEmpty' must be available
there are no arguments to 'print' that depend on a template parameter, so a declaration of 'print' must be available

e nel file Tree.h

no matching function for call to 'Queue<TreeNode<int>*>::dequeue()'

in realtà credo che non sia solo l'algoritmo ad essere sbagliato, ma anche l'intera strutturazione del programma... oltre all'algoritmo in sè qualcuno mi darebbe una mano a capire in queste situazioni qual è la giusta sintassi delle inclusioni e delle implementazioni dei template? Grazie mille a tutti.

[TheBestNapoli]

nessuno può aiutarmi?

[hamming_burst]

Ad occhio, direi che manca in:

Tree.h:

#include "Queue.h"

visto che chiami le funzioni nella visita per livelli.
L'algoritmo mi pare sia corretto, ma al primo colpo mi sembrava ci fosse qualcosa che non andava, controllando meglio direi che è corretto.

[TheBestNapoli]

Scusa ham_burst, grazie mille per aver risposto, in realtà è stato un mio errore nel trascrivere il programma, infatti l'avevo già incluso "Queue.h" ma involontariamente l'ho cancellato quando ho trascritto il tutto qui... (ora ho corretto il post)... il problema quindi mi rimane e mi scuso ancora...
Gli argomenti come il template e gli algoritmi del programma bene o male li ho capiti, ma ora mi ritrovo per la prima volta ad includere tutti questi file e quindi ad unire tutte questi template di classi... in pratica mi ritrovo ad usare tutte queste strutture dati insieme e ho difficoltà nell'implementazione... grazie ancora, spero in un aiutino

[hamming_burst]

Ma allora quali sono gli errori che ti derivano dalla compilazione?
Se hai copi-incollato sbagliato, tipo l'ultimo errore non dovrebbe esserci se avevi già insertio l'header corretto...

[TheBestNapoli]

Gli errori sono erano sempre quelli, comunque stamattina ho concentrato la mia attenzione esclusivamente nel comprendere questo esercizio e sono arrivato alla conclusione... in pratica i primi due errori erano dovuti al fatto che non avevo un implementazione delle funzioni della classe Coda, mentre il secondo errore era dovuto al fatto che la funzione dequeue(), così come l'ho definita nella classe Coda è di tipo bool e inoltre ha un parametro nel prototipo e quindi era completamente sbagliata l'istruzione

traverse = queue.dequeue();

Per quanto riguarda il primo errore ho eliminato il file List.h e ho modificato i file ListNode.h e Queue.h, ridefinendo al meglio le funzioni che mi servivano; poi per il secondo errore ho aggiustato l'algoritmo della visita per livelli sulla base delle funzioni che avevo definito.
Comunque sia ora funziona tutto alla perfezione, grazie mille ham_burst per le risposte (mi hanno incoraggiato perchè pensavo di aver sbagliato tutto )
Questo forum è fantastico... alla prossima! Ciaooo!