## tree & node templates

#ifndef __TREE_H__
#define __TREE_H__

template <class T> class TreeNode {
private:
	T *item;
	TreeNode<T> *parent_ptr, *left_ptr, *right_ptr;
public:
	TreeNode() { parent_ptr = left_ptr = right_ptr = 0; };
	TreeNode(const T & it) { item = new T(it); parent_ptr = left_ptr = right_ptr = 0; };
	~TreeNode() { delete item; };

	void set_parent(TreeNode<T> *parent) { parent_ptr = parent; };
	void set_left(TreeNode<T> *left) { left_ptr = left; };
	void set_right(TreeNode<T> *right) { right_ptr = right; };
	T & value() { return *item; };

	TreeNode<T> * parent() { return parent_ptr; };
	TreeNode<T> * left() { return left_ptr; };
	TreeNode<T> * right() { return right_ptr; };
};

template <class T> class Tree {
protected:
	TreeNode<T> *root_ptr;
    typedef enum { null, to_the_left, to_the_right } direction;

public:
	Tree() {
    	root_ptr = 0;
    };

	Tree(const T & item) {
        insert(item);
    };

	Tree(const T items[], int num_items) {
    	root_ptr = 0;

    	for (int i = 0; i < num_items; i++) {
    		insert(items[i]);
    	}
    };

	TreeNode<T> * root() const {
    	return root_ptr;
    };

	TreeNode<T> * operator<<(const T & item) {
        return insert(item);
	}

	TreeNode<T> * insert(const T & item) {
    	TreeNode<T> *prev, *search = root_ptr;
        direction taken = null;

    	while (search) {
            prev = search;

            if (item > search->value()) {
                search = search->right();
                taken = to_the_right;
            } else {
                search = search->left();
                taken = to_the_left;
            }
    	}

    	TreeNode<T> *new_leaf = new TreeNode<T>(item);

    	if (taken == null) {
            root_ptr = new_leaf;
    	} else if (taken == to_the_right) {
            prev->set_right(new_leaf);
            new_leaf->set_parent(prev);
    	} else {
            prev->set_left(new_leaf);
            new_leaf->set_parent(prev);
    	}

    	return new_leaf;
    };

    // return a pointer to the TreeNode containing an item that compares as equal with the argument item
	TreeNode<T> * find(T & item) const {
    	TreeNode<T> * search = root_ptr;

    	while (search && search->value() != item) {
    		if(item > search->value()) {
                search = search -> right();
    		} else {
                search = search -> left();
    		}
    	}

    	return search;
    };

	typedef void (*node_visitor_function)(TreeNode<T> *);

    void visit_in_order(node_visitor_function visitor)
    {
        perform_visit_in_order(visitor, root_ptr);
    }

    void perform_visit_in_order(node_visitor_function visitor, TreeNode<T> * node)
    {
        if (node) {
            visit_in_order(visitor, node->left());
            visitor(node);
            visit_in_order(visitor, node->right());
        }
    }
};

#endif

## simple test code

#include "../tree.h"
#include "../string.h"
#include "../deck.h"
#include "../card.h"
#include "test_macros.h"

#include <iostream>
using std::cout;
using std::endl;

String convenient;

void test_with_ints();
void int_tree_visitor(TreeNode<int> *node);

typedef Tree<int> IntTree;
typedef TreeNode<int> IntNode;

int main(void)
{
    test_with_ints();
}

void test_with_ints()
{
    IntTree int_tree;

    int_tree << 3;
    int_tree << -2;
    int_tree << 5;

    assert_equal(int_tree.root()->value(), 3, "Test root value");
    assert_equal(int_tree.root()->left()->value(), -2, "Test left value");
    assert_equal(int_tree.root()->right()->value(), 5, "Test right value");

    convenient = "";
    int_tree.visit_in_order(&int_tree_visitor);
    assert_equal("3 -2 5", convenient, "Test in-order-visit");
}

void int_tree_visitor(IntNode *node)
{
    convenient += " " + node->value();
}

## compiler output [plain_text]

make tree-test
make: Circular list.h <- list.h dependency dropped.
make: Circular list.h <- tree.h dependency dropped.
make: Circular tree.h <- tree.h dependency dropped.
g++ -Wall -g test/test_tree.cpp card.cpp deck.cpp string.cpp hand.cpp hand_collection.cpp game.cpp list.h tree.h player.cpp round.cpp && ./a.out
In file included from test/test_tree.cpp:15:
test/test_macros.h:12:1: warning: "assert" redefined
In file included from /usr/include/c++/4.0.0/cassert:48,
                 from /usr/include/c++/4.0.0/debug/debug.h:272,
                 from /usr/include/c++/4.0.0/bits/stl_algobase.h:76,
                 from /usr/include/c++/4.0.0/bits/char_traits.h:46,
                 from /usr/include/c++/4.0.0/ios:45,
                 from /usr/include/c++/4.0.0/ostream:44,
                 from /usr/include/c++/4.0.0/iostream:44,
                 from test/../string.h:13,
                 from test/test_tree.cpp:12:
/usr/include/assert.h:84:1: warning: this is the location of the previous definition
tree.h: In member function ‘void Tree<T>::perform_visit_in_order(void (*)(TreeNode<T>*), TreeNode<T>*) [with T = int]’:
tree.h:112:   instantiated from ‘void Tree<T>::visit_in_order(void (*)(TreeNode<T>*)) [with T = int]’
test/test_tree.cpp:47:   instantiated from here
tree.h:118: error: no matching function for call to ‘Tree<int>::visit_in_order(void (*)(TreeNode<int>*), TreeNode<int>*)’
tree.h:110: note: candidates are: void Tree<T>::visit_in_order(void (*)(TreeNode<T>*)) [with T = int]
tree.h:120: error: no matching function for call to ‘Tree<int>::visit_in_order(void (*)(TreeNode<int>*), TreeNode<int>*)’
tree.h:110: note: candidates are: void Tree<T>::visit_in_order(void (*)(TreeNode<T>*)) [with T = int]
make: *** [tree-test] Error 1