PCS Tree Summary

PCS Tree Summary

Preface

For the first assignment, I learn how to deal with the test. Actually I just took Data structure class last quarter, so everything here is not that unfamiliar with me. It just complex a lit bit from the stuff we learnt from data structure class. I haven’t spent much time on the assignment. But this is still a good recall of my understanding of data structure.

What is a PCS Tree?

Definition

Parent – Child –Sibling Tree

PCS Tree is a data structure used to store a hierarchical tree in form of a set of linked nodes. Each node in the tree can be a Parent, a Child or a Sibling of another node. Each parent node has one link to its first child only. The child nodes of a node are connected as a one-way linked list.

P for Parent

A pointer link to the parent

C for Child

A pointer link to the child

S for Sibling

A pointer link to siblings

Application

There are maybe various applications of PCS Tree. You may want to use it to store a directory structure inside an archive. Or it can be used to store data in a GUI control like QTreeView. In games, PCS Tree can be used to store a hierarchy of 3D objects. Each node will represent one object so that transformation applied to an object will affects all its child objects and grandchild objects.

Structures

PCSNode Graph:

1

PCSNode Method:

// constructor
PCSNode();
   
// copy constructor
PCSNode(const PCSNode &in );

// Specialize Constructor
PCSNode( PCSNode * const inParent, PCSNode * const inChild, 
         PCSNode * const inSibling, const char * const inName);
PCSNode( const char * const inName );


// destructor
~PCSNode();

// assignment operator
PCSNode &operator = (const PCSNode &in);

// accessors
void setParent( PCSNode * const in );
void setChild( PCSNode * const in );
void setSibling( PCSNode * const in );
PCSNode *getParent( void ) const;
PCSNode *getChild( void ) const;
PCSNode *getSibling( void ) const;

// name
PCSNodeReturnCode setName(const char * const inName );
PCSNodeReturnCode getName(char * const outBuffer, int sizeOutBuffer ) const;

// dump
void print() const;
void dumpChildren() const;
void dumpSiblings() const;
void dumpTree() const;

// get number of children/siblings
int getNumSiblings() const;
int getNumChildren() const;       
int getNumLevels() const;
int getNumNodes() const;
int getNumNodesRecursion() const;

// get level
int getLevel() const;

// remove
void removeAllNodes();
void removeAllNodesRecursion();

PCSTree Graph:

PCSTree

PCSTree Method:

// constructor
PCSTree();

// destructor
~PCSTree();

// get Root
PCSNode *getRoot( void ) const;

// insert
void insert(PCSNode * const inNode, PCSNode * const parent);

// remove
void remove(PCSNode * const inNode);

// get info
void getInfo( PCSTreeInfo &infoContainer );
void dumpTree( ) const;

 

Features

Every node has hierarchy.

Adding node is very fast.

Easy to use and implement.

Seeking and removing speed is OK.

Can get parents and children fast.

Good for storing objects.

 

Jin Han
February 16, 2013

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.