This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

| Templated Binary Tree Submitted by

This submission is a templated binary tree class. The implementation is fairly self-explanatory. The use of templates makes the binary tree extremely flexible and useful. The best way to illustrate this is with an example:

    // Andrew C. White, acwhite@charter.net
    // 19 April 2002
    // Templated Binary Tree

    // THIS CODE MAY BE USED BY ANYONE FOR ANY PURPOSE. BY USING THIS CODE YOU
    // AGREE TO TAKE FULL RESPNSIBILITY FOR ANY HARMFUL OR UNINTENDED CONSEQUENCES
    // THAT IT MAY CAUSE.

    #include <iostream
    #include "TBT.h"

    bool test(int a, int b)
    {
    	if(a  b)
    		return true;

    	return false;
    }

    void output(int a)
    {
    	std::cout << ' ' << a << ' ';
    }

    void main()
    {
    	BinTree<int tree;
    	tree.SetIsGreater(test);
    	tree.SetInOrder(output);

    	tree.Add(10);
    	tree.Add(5);
    	tree.Add(15);

    	tree.InOrder();
    }

The console display would read: "5 10 15" Any suggestions/comments would be greatly appreciated. - Andrew C. White

Currently browsing [TemplatedBinaryTree.zip] (1,801 bytes) - [TBT.h] - (4,363 bytes)

    // Andrew C. White, acwhite@charter.net
    // 19 April 2002
    // Templated Binary Tree

    // THIS CODE MAY BE USED BY ANYONE FOR ANY PURPOSE. BY USING THIS CODE YOU
    // AGREE TO TAKE FULL RESPNSIBILITY FOR ANY HARMFUL OR UNINTENDED CONSEQUENCES
    // THAT IT MAY CAUSE.

    // NOTE: This code was created for maximum readability, and therefore is probably
    // not very efficient.

    // NOTE: The use of templates allows for extreme flexibility. Currently, only
    // in-order traversal is implemented, however adding more traversal types would
    // be simple to do.

    // NOTE: Before you can add data to a new tree, you must first call the SetIsGreater
    // function. This must only be done once for the tree. The function you pass in must
    // return a pointer to a BinTreeNode and take two parameters of the data type.
    // See the included example if this is unclear.

    // NOTE: Before you can use the in-order transversal, you must first call the
    // SetInOrder function. This must only be done once for the tree. The function
    // you pass in must take a single parameter of the data type. See the included
    // example if this is unclear.

    #ifndef _TBT_H_
    #define _TBT_H_

    ///////////////////////////////////////////////////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////////
    // TEMPLATED BINARY TREE NODE CLASS

    template <class type> class BinTreeNode
    {
    public:
    	BinTreeNode();
    	~BinTreeNode();

    	BinTreeNode<type>* Add(type newData, bool (*isGreater) (type data1, type data2));
    	void InOrder(void (*inOrder) (type data));

    private:
    	BinTreeNode<type>* right;
    	BinTreeNode<type>* left;
    	type data;
    	bool full;
    };

    // CONSTRUCTOR
    template <class type> BinTreeNode<type>::BinTreeNode()
    {
    	right = 0;
    	left = 0;
    	full = false;
    }

    // DECONSTRUCTOR
    template <class type> BinTreeNode<type>::~BinTreeNode()
    {
    	if(left)
    	{
    		delete left;
    		left = 0;
    	}

    	if(right)
    	{
    		delete right;
    		right = 0;
    	}
    }

    // ADD
    template <class type> BinTreeNode<type>* BinTreeNode<type>::Add(type newData, bool (*isGreater)(type data1, type data2))
    {
    	if(full)
    	{
    		if(isGreater(newData, data))
    		{
    			if(!right)
    				right = new BinTreeNode<type>;

    			return right->Add(newData, isGreater);
    		}
    		else
    		{
    			if(!left)
    				left = new BinTreeNode<type>;

    			return left->Add(newData, isGreater);
    		}
    	}
    	else
    	{
    		data = newData;
    		full = true;
    		return this;
    	}
    }

    // IN-ORDER TRAVERSAL
    template <class type> void BinTreeNode<type>::InOrder(void (*inOrder) (type data))
    {
    	if(left)
    		left->InOrder(inOrder);

    	inOrder(this->data);

    	if(right)
    		right->InOrder(inOrder);
    }

    ///////////////////////////////////////////////////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////////
    // TEMPLATED BINARY TREE CLASS

    template <class type> class BinTree
    {
    public:
    	BinTree();
    	~BinTree();

    	BinTreeNode<type>* Add(type newData);
    	void SetIsGreater(bool (*isGreater)(type data1, type data2));
    	void InOrder();
    	void SetInOrder(void (*inOrder) (type data));

    private:
    	BinTreeNode<type>* root;
    	bool (*isGreater) (type data1, type data2);
    	void (*inOrder) (type data);
    };

    // CONSTRUCTOR
    template <class type> BinTree<type>::BinTree()
    {
    	root = 0;
    	isGreater = 0;
    }

    // DECONSTRUCTOR
    template <class type> BinTree<type>::~BinTree()
    {
    	if(root)
    	{
    		delete root;
    		root = 0;
    	}

    	isGreater = 0;
    	inOrder = 0;
    }

    // ADD
    template <class type> BinTreeNode<type>* BinTree<type>::Add(type newData)
    {
    	if(!isGreater)
    		return 0;

    	if(!root)
    		root = new BinTreeNode<type>;

        return root->Add(newData, isGreater);
    }

    // SET THE COMPARE FUNCTION
    template <class type> void BinTree<type>::SetIsGreater(bool (*isGreater) (type data1, type data2))
    {
    	this->isGreater = isGreater;
    }

    // IN-ORDER TRAVERSAL
    template <class type> void BinTree<type>::InOrder()
    {
    	if(root && inOrder)
    		root->InOrder(inOrder);
    }

    // SET THE IN-ORDER TRAVERSAL FUNCTION
    template <class type> void BinTree<type>::SetInOrder(void (*inOrder) (type data))
    {
    	this->inOrder = inOrder;
    }

    #endif

Currently browsing [TemplatedBinaryTree.zip] (1,801 bytes) - [example.cpp] - (613 bytes)

    // Andrew C. White, acwhite@charter.net
    // 19 April 2002
    // Templated Binary Tree

    // THIS CODE MAY BE USED BY ANYONE FOR ANY PURPOSE. BY USING THIS CODE YOU
    // AGREE TO TAKE FULL RESPNSIBILITY FOR ANY HARMFUL OR UNINTENDED CONSEQUENCES
    // THAT IT MAY CAUSE.

    #include <iostream>
    #include "TBT.h"

    bool test(int a, int b)
    {
    	if(a > b)
    		return true;

    	return false;
    }

    void output(int a)
    {
    	std::cout << ' ' << a << ' ';
    }

    void main()
    {
    	BinTree<int> tree;
    	tree.SetIsGreater(test);
    	tree.SetInOrder(output);

    	tree.Add(10);
    	tree.Add(5);
    	tree.Add(15);

    	tree.InOrder();
    }

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.