Introduction
Not so long ago in one of my recent projects, I needed a tree class for representing data structures. I looked all over the web and didn't find any acceptable solution. A tree is a structure which is not as simple as an array or list, so unfortunately STL comes without it and I had to write one myself.
I divided the implementation on two main parts: Data
and Node
. Data
object is responsible for holding the data, and the Node (Tree)
for the tree structure.
Data Objects
The purpose of the Data
class is to keep the actual data. It keeps the data until all actual references to it are dead. This is done with reference counting (COM like). I know somebody may find this worthless and useless, but it makes the data more capsulated and secure. The implementation is divided in two classes, Data
and Ref
(reference). All the data is stored in the Data
class. All the job is done by Ref
class, which manipulates the data class:
template <class Type> class Data {
private:
...
friend class Ref<Type>;
};
template <class Type> class Ref {
Ref(Type *p);
Ref();
Ref(const Ref<Type> rhs);
virtual ~Ref();
Ref operator=(const Ref<Type> rhs);
Ref operator=(const Type t);
Ref operator=(Type *p);
bool operator==(const Ref<Type> rhs)
Ref Clone();
void Release();
bool IsNull();
Type *operator->();
Type get_Data();
operator Type();
}
Tree(Node) Object
Tree
class represents a node in the tree, so it has parent and it has children. in this way, I use a single class for representing a node and a tree, so the tree is a node without parent, and leaf is a node without children. It also has reference (Ref
) to the data. Its implementation is divided between two classes, NodeData
and Tree
. NodeData
objects holds the actual data for the parent and the children, but Tree
object manipulates this data and gives access to them. Actually, you'll always use only Tree
class directly.
Definitions:
Node
- a node or leaf in the tree (can be root node as well) Leaf
- a node without children nodes Root
- a node without parent node (we'll reference it as a Tree
as well) Null
- null
node
template <class Type> class NodeData {
private:
....
friend class Tree<Type>;
}
template <class Type> class Tree {
public:
typedef Tree<Type> Node;
Node Parent();
__declspec( property( get=get_Nodes) ) Node Nodes[];
__declspec( property( get=get_Count) ) int Count;
Node get_Nodes(int nIndex);
int get_Count();
__declspec( property( get=get_Data) ) Ref<Type> Data;
operator Type();
Type *operator->();
Ref<Type> get_Data();
bool IsLeaf();
bool IsNode();
bool IsRoot();
bool operator == (const Node rhs)
{ return *(NodeBase*)this==(NodeBase )rhs;};
Node AddNode(const Type t);
void Delete();
void DeleteNode(int nIndex);
void DeleteNode(Node node);
Tree(const Type Data);
Tree(Type *Data);
Tree();
Tree(const Tree<Type> rhs);
Tree(const NodeBase rhs);
virtual ~Tree();
}
Very Simple Usage Example
#include "stdio.h"
#include "tree.h"
#include "string"
using namespace std;
typedef Tree<string> StringTree;
typedef
StringTree::Node StringNode;
recursive function for prionitng nodes void
PrintNode(StringNode node,int nLevel) {
print new line fputs("\n",stdout);
print spaces for indent (2 for every level) string
s; s.resize(nLevel*2,'
'); fputs(s.c_str(),stdout);
print the value fputs(node.get_Data()->c_str(),stdout);
iterate through children nLevel++;
for(int
n= 0;n<&;node.Count;n++) {
PrintNode(node.Nodes[n],nLevel);
}
}
int main(int argc, char* argv[])
{
StringTree tree;
((string&)tree)="Root";
StringNode node=tree;
node.AddNode("1").AddNode("11");
StringNode node2=node.AddNode("2");
node2.AddNode("21").AddNode("211");
node2.AddNode("22");
node2.AddNode("23");
node.AddNode("3");
PrintNode(tree,0);
char buf[3];
fputs("\nPress ENTER :",stdout);
fgets(buf,3,stdin);
return 0;
}
Conclusion
The presented Tree
class is not the best solution, and is also not the best performer since it uses vector
internally, but is flexible and easy to use. In most of the available Tree
structures, you'll find that we require direct work with pointers, and a lot of code to be filled and indexed. This one is very easy to use (with the price for this of course).
Please let me a note below if you have comments and opinions.
License
This article has no explicit license attached to it, but may contain usage terms in the article text or the download files themselves. If in doubt, please contact the author via the discussion board below.
A list of licenses authors might use can be found here.