Click here to Skip to main content
Click here to Skip to main content

Tree data class for C++

, 12 Jan 2002
Rate this:
Please Sign up or sign in to vote.
Simple class to represent tree data structures in C++
<!-- Download Links --> <!-- Add the rest of your HTML here -->

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:
...// all methods and variables are private
   friend class Ref<Type>; // Ref class will manipulate us
};
template <class Type> class Ref {
    Ref(Type *p);
    Ref();
    Ref(const Ref<Type> rhs);
    //destructor
    virtual ~Ref();

//operators =
    Ref operator=(const Ref<Type> rhs);
    Ref operator=(const Type t);
    Ref operator=(Type *p); 
// operator ==
    bool operator==(const Ref<Type> rhs) 
// misc

    Ref Clone();
    void Release();
    bool IsNull();

// accessors to the actual data 
// (check if it's null first)
    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 the tree is a node without parent, and leaf is a node without children. It also has reference (Ref) to the data. It's 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.

Definitons:

  • 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:
    .... // all methods  vars are private
    friend class Tree<Type>;
}

template <class Type> class Tree {
public:
    // we'll call the tree node
    typedef Tree<Type> Node;
    
    // parent
    Node Parent();
    
    // children - Nodes
    __declspec( property( get=get_Nodes) ) Node Nodes[];
    __declspec( property( get=get_Count) ) int Count;

    Node get_Nodes(int nIndex);
    int get_Count();
    
    // data acess
    __declspec( property( get=get_Data) ) Ref<Type> Data;

    operator Type();
    Type *operator->();
    Ref<Type> get_Data();

    // node functions (isLeaf and so on
    bool IsLeaf();
    bool IsNode();
    bool IsRoot();

    // comparision
    bool operator == (const Node rhs)
          { return *(NodeBase*)this==(NodeBase )rhs;};

    // node operations
    Node AddNode(const Type t); 
    void Delete();
    void DeleteNode(int nIndex);
    void DeleteNode(Node node);

    // constructors
    Tree(const Type Data);
    Tree(Type *Data);
    
    Tree();
    Tree(const Tree<Type> rhs);
    Tree(const NodeBase rhs);
    
    // destructor
    virtual ~Tree();
}

Very simple usage example

#include <span class="code-string">"stdio.h"
</span>
#include <span class="code-string">"tree.h"
</span>
#include <span class="code-string">"string"
</span>
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[])
{
	// define the tree
	StringTree tree; 
	((string&)tree)="Root";

	//add few nodes
	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");

	// print the tree
	PrintNode(tree,0);

	// wait for enter
	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 not also not the best performer since it uses vector internally, but is flexible and easy to use. Most of available Tree structures you'll find we'll 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).

Contact me if you have comments and opinions (akovache@san.rr.com)

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

Share

About the Author

Alexander Kovachev
Web Developer
United States United States
No Biography provided

Comments and Discussions

 
GeneralOther tree data class Pinmemberjohn.double26-Dec-09 10:41 
Generalthanks a lot Pinmemberscu064311110816-Dec-08 1:40 
GeneralHello! Help me... PinmemberZoTiger28-Dec-07 19:00 
GeneralUpdating exisiting nodes Pinmemberfreddy198113-Apr-06 18:39 
I'm trying to come up with a function that will allow me to update the existing nodes in the tree.
From what I have been able to do, the compiler is asking me to add a "put" method to the property:
__declspec( property( get=get_Nodes) ) Node Nodes[];

Unfortunately I have not been able to do that.
 
The other option was to overload the = operator and use the following function:
void UpdateNode(const Type &t)
{
NodeBase::get_Data() = t;
};
 
The only problem is that by doing this update I loose all the child information.

Any help you can provide will be very much appreciated.

Thanks.

Freddy Cardenas
 
-- modified at 21:04 Friday 14th April, 2006
GeneralThe demo software doesnt work PinmemberAnonymous4-Jul-02 8:33 
GeneralUsing STL for imlementing trees PinmemberMartin Holzherr14-Jan-02 2:21 
GeneralRe: Using STL for imlementing trees PinmemberMihail23-Oct-03 3:07 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140827.1 | Last Updated 13 Jan 2002
Article Copyright 2002 by Alexander Kovachev
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid