|
| 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
|
|