Help with Insertion into a Quadtree

Hello,

I was hoping someone could help me with inerting into a quadtree that
I am coding.  This is the first time I am attempting to write an
algorithm for image compression.  I believe that for the most part my
simple data structure is sound except for the inserting, and hope that
someone can point me the the right direction for this.

I use to insert functions, one is public and the other is private.
The public function simply calls the private function that does all
the work.  The reason I am concerned with this is because when I
traverse the tree with both in-order and pre-order the result is the
same and it should not be.  If anyone is familiar with quadtree
compression for images and can help me out I would be greatfull.

Below, I have pasted the contents of both my .h and .cpp files.

Thank you for your help.


//  .cpp file begins here.  //

#include "Qtree.h"

namespace QNT
{



/*
* insert():
* Preconditions:  This insert function is called by the public
insert.
* Postconditions: Inserts the data items into a new node in the
tree.
*/
void Qtree::insert(int R, int G, int B, Qnode*& subTreeRoot)
{

if (subTreeRoot == NULL)
{
subTreeRoot = new Qnode(R, G, B, NULL, NULL, NULL, NULL);
}
else if (subTreeRoot->nwLink != NULL)
{
insert(R, G, B, subTreeRoot->nwLink);
}
else if (subTreeRoot->neLink != NULL)
{
insert(R, G, B, subTreeRoot->neLink);
}
else if (subTreeRoot->swLink != NULL)
{
insert(R, G, B, subTreeRoot->swLink);
}
else //subTreeRoot->seLink != NULL
{
insert(R, G, B, subTreeRoot->seLink);
}

}



/*
* insert():
* Preconditions:  An instance of Qtree must exist.  Insert takes 3
*                 integer paramaters.
* Postconditions: A new node is created in the tree with the 3 data
*                 items that were passed in.
*/
void Qtree::insert(int R, int G, int B)
{
insert(R, G, B, root);
}



/*
* inOrderShow():
* Preconditions:  Private helper function that is called by the
public
*                 inOrderShow function.
* Postconditions: Traverses the tree in order and prints the
results.
*/
void Qtree::inOrderShow(Qnode* subTreeRoot) const
{
if (subTreeRoot != NULL)
{
inOrderShow(subTreeRoot->nwLink);
inOrderShow(subTreeRoot->neLink);
std::cout << subTreeRoot->red << ", ";
std::cout << subTreeRoot->green << ", ";
std::cout << subTreeRoot->blue << std::endl;
inOrderShow(subTreeRoot->swLink);
inOrderShow(subTreeRoot->seLink);
}
}



/*
* inOrderShow():
* Preconditions:  An instance of Qtree must exist.
* Postconditions: Traverse the tree in order, returning the results
*                 contained at each node of the tree.
*/
void Qtree::inOrderShow( ) const
{
inOrderShow(root);
}



/*
* preOrderShow():
* Preconditions:  Private helper function that is called by the
public
*                 preOrderShow function.
* Postconditions: Traverses the tree in pre-Order and prints the
results.
*/
void Qtree::preOrderShow(Qnode* subTreeRoot) const
{
if(subTreeRoot != NULL)
{
std::cout << subTreeRoot->red << ", ";
std::cout << subTreeRoot->green << ", ";
std::cout << subTreeRoot->blue << std::endl;
preOrderShow(subTreeRoot->nwLink);
preOrderShow(subTreeRoot->neLink);
preOrderShow(subTreeRoot->swLink);
preOrderShow(subTreeRoot->seLink);
}
}



/*
* preOrderShow():
* Preconditions:  An instance of Qtree must exist.
* Postconditions: Traverse the tree in pre-order, returning the
results
*                 contained at each node of the tree.
*/
void Qtree::preOrderShow( ) const
{
preOrderShow(root);
}



/*
* deleteSubtree():
* Preconditions:   This function is called by the default
constructor.
* Postconditions:  Recursively deletes nodes in each subtree of the
*                  quadtree until all nodes including the root have
been
*                  destroyed.
*/
void Qtree::deleteSubtree(Qnode*& subTreeRoot)
{
if (subTreeRoot != NULL)
{
deleteSubtree(subTreeRoot->nwLink);
deleteSubtree(subTreeRoot->neLink);
deleteSubtree(subTreeRoot->swLink);
deleteSubtree(subTreeRoot->seLink);

//subTreeRoot now points to a one node tree.
delete subTreeRoot;
subTreeRoot = NULL;
}
}


/*
* ~Qtree():
* Preconditions:  Default Destructor, an instance of Qtree must
exist
*                 prior to calling.
* Postconditions: Destroys tree by recusively destroying subtrees
one
*                 node at a time, until no nodes are left.
*/
Qtree::~Qtree( )
{
deleteSubtree(root);
}

}


//   .h file begins here    //


#include <iostream>

using namespace std;

#ifndef QNT_H
#define QNT_H

namespace QNT
{
class Qtree; //forward declaration

class Qnode
{
public:

//   Qnode( ) : root(NULL){}

/*
* Qnode():
* Preconditions:  Must pass in parameters that correspond to the
node pointers and
*                 the RGB values of a pixel.
* Postconditions: A node is created that holds the corresponding
values that were
*                 passed in.
*/
Qnode(int Red, int Green, int Blue, Qnode* nw, Qnode* ne, Qnode*
sw, Qnode* se)
: red(Red), green(Green), blue(Blue), nwLink(nw), neLink(ne),
swLink(sw), seLink(se){}

// Qtree declared as friend to have access to Qnode private
members.
friend class Qtree;

private:

int red;        // holds the red pixel value
int green;      // holds the green pixel value
int blue;       // holds the blue pixel value

// Pointers used to create the 4-ary tree or Quadtree.
Qnode *nwLink;
Qnode *neLink;
Qnode *swLink;
Qnode *seLink;
};  // Close class Qnode



class Qtree
{
public:

/*
* Qtree():
* Preconditions:  Default Constructor, user just needs to
instantiate
/*                an instance.
* Postconditions: Creats a tree with a root node that is empty.
*/
Qtree( ) : root(NULL){}



/*
* ~Qtree():
* Preconditions:  Default Destructor, an instance of Qtree must
exist
*                 prior to calling.
* Postconditions: Destroys tree by recusively destroying
subtrees one
*                 node at a time, until no nodes are left.
*/
virtual ~Qtree( );



/*
* insert():
* Preconditions:  An instance of Qtree must exist.  Insert takes
3
*                 integer paramaters.
* Postconditions: A new node is created in the tree with the 3
data
*                 items that were passed in.
*/
void insert(int R, int G, int B);



/*
* inOrderShow():
* Preconditions:  An instance of Qtree must exist.
* Postconditions: Traverse the tree in order, returning the
results
*                 contained at each node of the tree.
*/
void inOrderShow( ) const;



/*
* preOrderShow():
* Preconditions:  An instance of Qtree must exist.
* Postconditions: Traverse the tree in pre-order, returning the
results
*                 contained at each node of the tree.
*/
void preOrderShow( ) const;


private:

/*
* insert():
* Preconditions:  This insert function is called by the public
insert.
* Postconditions: Inserts the data items into a new node in the
tree.
*/
void insert(int R, int G, int B, Qnode*& subTreeRoot);



/*
* deleteSubtree():
* Preconditions:   This function is called by the default
constructor.
* Postconditions:  Recursively deletes nodes in each subtree of
the
*                  quadtree until all nodes including the root
have been
*                  destroyed.
*/
void deleteSubtree(Qnode*& subTreeRoot);



/*
* inOrderShow():
* Preconditions:  Private helper function that is called by the
public
*                 inOrderShow function.
* Postconditions: Traverses the tree in order and prints the
results.
*/
void inOrderShow(Qnode* subTreeRoot) const;



/*
* preOrderShow():
* Preconditions:  Private helper function that is called by the
public
*                 preOrderShow function.
* Postconditions: Traverses the tree in pre-Order and prints the
results.
*/
void preOrderShow(Qnode* subTreeRoot) const;

// Private data pointer to root Qnode
Qnode *root;

};  // Close class Qtree

}  // Close namespace QNT

#endif