C++ Tree

[didijc]

Hey C++ guru's...

I would really appreciate some help...

I'm building a general tree (a tree with one root and N children), I've written the code and compiled it quote/un-quote successfully... ...however, I can't seem to get my delete function working properly -- what I want to do is pass in a transactionID per "that" and delete "it" and all of "its" children...

///////////////////////// GENERALTREE.h /////////////////////////
#ifndef GENERALTREE_h
#define GENERALTREE_h

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

class GenTreeNode{
	public:
		int transactionID, totalNumChildren;
		GenTreeNode *childrenPtr;

		std::string toString(){
			std::ostringstream oss;
			oss<<transactionID<<' '<<frequency;

			return oss.str();
		}

		void print(){
			cout<<toString()<<endl;
		}

		void printNode() {
			print();
			for(int i=0; i<totalNumChildren; i++){
				childrenPtr[i].printNode();
			}
		}

		GenTreeNode(): transactionID(0),totalNumChildren(0){
			childrenPtr = NULL;
		}

		GenTreeNode(int id, int cNo){
			transactionID = id;
			totalNumChildren = cNo;
			childrenPtr = new GenTreeNode[totalNumChildren];
		}

		void setTreeNode(int id, int cNo){
			transactionID = id;
			totalNumChildren = cNo;
			childrenPtr = new GenTreeNode[totalNumChildren];
		}

		~GenTreeNode(){
			if(childrenPtr != NULL){
				delete[] childrenPtr;
			}
		}

		void setChildren(int *tranID, int *cNos){
			for(int i=0; i<totalNumChildren; i++){
				childrenPtr[i].setTreeNode(tranID[i], cNos[i]);
			}
		}

		void delChildren(GenTreeNode *ChildPtr){
			if(totalNumChildren){
				delete[] childrenPtr;
			}
		}
};

class GeneralTree{
	public:
		//initialize root
		GenTreeNode root;

		GeneralTree(){}

		virtual ~GeneralTree(){}

		void setTreeChildren(int *tranIDs, int *cNos){
			root.setTreeNode(*tranIDs, *cNos);
			root.setChildren(tranIDs, cNos);
		}

		void printTree() {
			root.printNode();
		}
};
#endif

///////////////////////// MAIN.cpp /////////////////////////
#include <iostream>
#include <fstream>
#include "GeneralTree.h"

using namespace std;

int main(){
	GeneralTree cTree;

	int tIDs[] = { 100,200,300,400,500,600,700,800,900 };
	int numOfChilds[] = { 9,4,2,2,4,6,8,6,4 };

	cTree.setTreeChildren(tIDs, numOfChilds);
	cTree.printTree();

	return 0;
}

************************************

Here's the find function that I was working on...

GenTreeNode findNode(int tranId){
	// check if transactionID equals to the tranId - if yes return this node
	if(transactionID == tranId){
		return node;
	}
			
	if (childrenPtr != NULL){
		// get node from recursive calling find 
		node = findNode(tranId); 
			
		// if the node was found we are thru
		if(node != NULL) 
			return node;
	}
}

[wildgoose]

Please excuse my ignorance but something here doesn't seem right!

First of all this isn't a tree. It is a list!!!!

A tree would have atleast two branches.

GenTreeNode *childA;
GenTreeNode *childB;

I've picked on one of your functions that stood out the most with apparent problems.

GenTreeNode findNode(int tranId)
{   // check if transactionID equals to the tranId - if yes return this node
    GenTreeNode *node = NULL;

   if(transactionID == tranId)
   {
// What node??? do you mean to return 'THIS' node, thus
//  you need to return the 'this' pointer!
//        return node;
          return this;
   }

      // Is there a child link?

   if (childrenPtr != NULL)
   {		// get node from recursive calling find 	   
// ??? BOOM???? We are recursively calling this function passing
// the same Id that was passed in so we will blow the stack!
//         node = findNode(tranId); 
// OR DID YOU MEAN TO DO THIS
            node = childrenPtr->findNode( tranId );
    }

//????? WHERE IS THE RETURN!!!!!
   return node;
}

You don't need recursion to follow a list in a find operation. Just a loop. But for deletion, then you traverse the list recursively, and delete the linked objects on the way back!

void GenTreeNode::RemoveChildren( void )
{      // recursion upwards
     if (NULL != childrenPtr)   // If a child exists...
     {                  // Recursively call it to remove its children
        childrenPtr->RemoveChildren();     
        delete childrenPtr;      // remove children on way back
        childrenPtr = NULL;
     }
}

Also you can't just delete one object connected by a link! You need to traverse the chain and delete all the nodes connected to that link.