Sorry it took a while, well i'm ready to release version 0.1 but before i do, as this is originally from the GCC implementation of a red-black tree (but major modifification) should i copy and paste the GNU licensing comments to the top of the code?

Quote:Original post by Etnu
I have a custom linked list that I use which has a "GetFirst()" and "GetLast()" member function. Depending on which one you call, the "GetNext()" function will either return the previous, or the next element. The list contains pointers to both head & tail, and each node contains a previous and next pointer.

I think something like that is probably the way to go if you have multiple transversal methods.

Its okay i've already sorted the iterators out a while ago, there is two iterators constant and non constant iterator types which are parameterized by traversal scheme and you can copy/construct any iterators with any iterators with other types of traversal scheme.

I'm thinking about later on to have tree_traits type so people can add new traversal schemes and drop them into the iterators

I was wondering whether you are familiar with the boost.graph library.

It uses STL like generic design principles. There is a lot of rationale so you might find inspiration there

Out of curiosity, what don't you like about the tree container in GPG4? I thought the concept of no recursion to follow a pre-order traversal was a nice touch.

Quote:Original post by aboeing
I've always wondered why there wasnt a generalised tree in the STL. Seems like a fairly common data structure to me.

Generally because the idea of a tree is on a different level to the other STL containers. If you just wanted a balanced tree for some sort of lookup speed, then that is what std::set and std::map is for, and the tree implementation is irrelevant. And if you absolutely require a hierarchical structure, then most of the time I would expect you'd want to create custom node types that contain links to their children, and whether you used deque, list, or vector in that implementation would depend on your needs. Personally I can't ever see a time where a STL tree class wouldn't either be too low-level or too abstract for a task.

Quote:Original post by DrNecessiter
Out of curiosity, what don't you like about the tree container in GPG4? I thought the concept of no recursion to follow a pre-order traversal was a nice touch.

Hello all of the traversal schemes i've written don't use recursion. The reason why i didn't like there version was the way they handled the concept of it, viewing a tree as a linear sequence of trees. The way i see it the iterators allow the algorithms to view as it as linear container.

Some of the operations in there are a little strange like what does it mean to get/push/pop the front & back of a tree?

The implementation wasn't very good & the way it handles allocators seemed a little abit hacky.

I've believe mine is much better than that one & the one thats on the net as it was based off GCC implementation of red-black tree its very robust & efficent. Yes i'm ready to release it for people to critique & improve, it compiles & runs on VS.NET 2003 & GCC 3.4.

I may add a tree_traits type later on so people can add there own traversal scheme implementations and use the same 2 iterators types provided.

As it is a modified source of GCC i wasn't sure about the rules of releasing it so i've copied the license comments at the top

here is the source:
tree.hpp

// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.//// This file is part of the GNU ISO C++ Library.  This library is free// software; you can redistribute it and/or modify it under the// terms of the GNU General Public License as published by the// Free Software Foundation; either version 2, or (at your option)// any later version.// This library is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the// GNU General Public License for more details.// You should have received a copy of the GNU General Public License along// with this library; see the file COPYING.  If not, write to the Free// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,// USA.// As a special exception, you may use this file as part of a free software// library without restriction.  Specifically, if other files instantiate// templates or use macros or inline functions from this file, or you compile// this file and link it with other files to produce an executable, this// file does not by itself cause the resulting executable to be covered by// the GNU General Public License.  This exception does not however// invalidate any other reasons why the executable file might be covered by// the GNU General Public License./* * * Copyright (c) 1996,1997 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation.  Silicon Graphics makes no * representations about the suitability of this software for any * purpose.  It is provided "as is" without express or implied warranty. * * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation.  Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose.  It is provided "as is" without express or implied warranty. * * */// tree type v0.1// author: Korcan Hussein# ifndef _KTREE_#	define _KTREE_#	ifndef _GNUC_#		ifndef __EXCEPTIONS//		Iff -fno-exceptions, transform error handling code to work without it.#			define try      if (true)#			define catch(X) if (false)#			define __throw_exception_again#		else//		Else proceed normally.#			define __throw_exception_again throw#		endif#	endif#	include <cstddef>#	include <utility>#	include <algorithm>#	include <iterator>#	include <queue>namespace std {	struct tree_node_base {		typedef tree_node_base*	base_ptr;		typedef const tree_node_base* const_base_ptr;		tree_node_base*		_parent;		tree_node_base*		_first_child;		tree_node_base*		_last_child;		tree_node_base*		_pred;		tree_node_base*		_succ;		static		inline base_ptr most_bottom_first_child(base_ptr __x) {			while(__x->_first_child != 0) __x = __x->_first_child;			return __x;		}		static		inline const_base_ptr most_bottom_first_child(const_base_ptr __x) {			while(__x->_first_child != 0) __x = __x->_first_child;			return __x;		}		static		inline base_ptr most_bottom_last_child(base_ptr __x) {			while(__x->_last_child != 0) __x = __x->_last_child;			return __x;		}		static		inline const_base_ptr most_bottom_last_child(const_base_ptr __x) {			while(__x->_last_child != 0) __x = __x->_last_child;			return __x;		}	};	template< typename T > struct tree_node : public tree_node_base {		typedef tree_node_base*			link_type;		typedef const tree_node_base*	const_link_type;		typedef	T						value_type;		value_type	_elem;	};	/*template< typename T, typename node_t = tree_node<T> >	struct tree_traits {		typedef	typename node_t::value_type			value_type;		typedef const typename node_t::value_type	const_value_type;		typedef value_type&							reference;		typedef	const value_type&					const_reference;		typedef value_type*							pointer;		typedef const pointer						const_pointer;		typedef ptrdiff_t							difference_type;		typedef size_t								size_type;		typedef typename node_t::link_type			link_type;		typedef typename node_t::const_link_type	const_link_type;		typedef node_t*								node_type;		typedef const node_t*						const_node_type;		static node_type _M_cast_node(link_type __x) {			return static_cast<node_type>(__x);		}		static const_node_type _M_cast_node(const_link_type __x) {			return static_cast<const_node_type>(__x);		}	};*/	struct traversal_base {		typedef tree_node_base::base_ptr		_base_ptr;		typedef tree_node_base::const_base_ptr	_const_base_ptr;	};    	struct pre_order : public traversal_base {		pre_order(): traversal_base() {}		static 		inline _base_ptr tree_increment(_base_ptr __x) {			if((__x->_first_child == 0) && (__x->_succ == 0)) {                while(__x->_parent->_succ == 0) __x = __x->_parent;				return __x->_parent->_succ;			} else				return ((__x->_first_child != 0) ? __x->_first_child : __x->_succ);		}		static 		inline _const_base_ptr tree_increment(_const_base_ptr __x) {			if((__x->_first_child == 0) && (__x->_succ == 0)) {                while(__x->_parent->_succ == 0) __x = __x->_parent;                return __x->_parent->_succ;			} else				return ((__x->_first_child != 0) ? __x->_first_child : __x->_succ);		}		static 		inline _base_ptr tree_decrement(_base_ptr __x) {			if((__x->_pred != 0) && (__x->_pred->_last_child != 0)) {				__x = __x->_pred;				while(__x->_last_child != 0) __x = __x->_last_child;								return __x;			} else if((__x->_pred != 0)) {				return __x->_pred;			} else {				return __x->_parent;			}		}		static 		inline _const_base_ptr tree_decrement(_const_base_ptr __x) {			if((__x->_pred != 0) && (__x->_pred->_last_child != 0)) {				__x = __x->_pred;				while(__x->_last_child != 0) __x = __x->_last_child;								return __x;			} else if((__x->_pred != 0)) {				return __x->_pred;			} else {				return __x->_parent;			}		}	};	struct post_order : public traversal_base {		post_order(): traversal_base() {};		static 		inline _base_ptr tree_increment(_base_ptr __x) {			if((__x->_succ != 0) && (__x->_succ->_first_child != 0)) {				__x = __x->_succ;				if(__x->_parent != 0) {                    while(__x->_first_child != 0) __x = __x->_first_child;				                    return __x;				} else					return __x;			} else if((__x->_succ != 0)) {				return __x->_succ;			} else {				return __x->_parent;			}		}		static 		inline _const_base_ptr tree_increment(_const_base_ptr __x) {			if((__x->_succ != 0) && (__x->_succ->_first_child != 0)) {				__x = __x->_succ;				if(__x->_parent != 0) {                    while(__x->_first_child != 0) __x = __x->_first_child;				                    return __x;				} else					return __x;			} else if((__x->_succ != 0)) {				return __x->_succ;			} else {				return __x->_parent;			}		}		static 		inline _base_ptr tree_decrement(_base_ptr __x) {			if((__x->_last_child == 0) && (__x->_pred == 0)) {                while(__x->_parent->_pred == 0) __x = __x->_parent;				return __x->_parent->_pred;			} else				return ((__x->_last_child != 0) ? __x->_last_child : __x->_pred);		}		static		inline _const_base_ptr tree_decrement(_const_base_ptr __x) {			if((__x->_last_child == 0) && (__x->_pred == 0)) {                while(__x->_parent->_pred == 0) __x = __x->_parent;				return __x->_parent->_pred;			} else				return ((__x->_last_child != 0) ? __x->_last_child : __x->_pred);		}	};	struct breadth_first : public traversal_base {		breadth_first(): traversal_base(), _q_of_first() {}		inline _base_ptr tree_increment(_base_ptr __x) {			if(__x->_first_child != 0) {				_q_of_first.push(__x->_first_child);			}			if(__x->_succ != 0 && __x->_parent != 0)				return __x->_succ;			else if(!_q_of_first.empty()) {                _base_ptr& __y = _q_of_first.front();                _q_of_first.pop();                return __y;			} else {				return 0;			}		}		inline _const_base_ptr tree_increment(_const_base_ptr __x) {			if(__x->_first_child != 0) {				_q_of_first.push(__x->_first_child);			}			if(__x->_succ != 0 && __x->_parent != 0)				return __x->_succ;			else if(!_q_of_first.empty()) {                _base_ptr& __y = _q_of_first.front();                _q_of_first.pop();                return __y;			} else {				return 0;			}		}		inline _base_ptr tree_decrement(_base_ptr __x) {			if(__x->_pred != 0)				return __x->_pred;			else if(__x->_parent != 0 && __x->_parent->_pred != 0) {				__x = __x->_parent->_pred;				while(__x->_pred != 0 && __x->_pred->_last_child == 0) { __x = __x->_pred; }				if(__x->_pred != 0)					return __x->_pred->_last_child;				else					return __x->_parent->_last_child;			}  else if(__x->_parent == 0)				return __x->_succ;			else				return __x->_parent;		}		inline _const_base_ptr tree_decrement(_const_base_ptr __x) {			if(__x->_pred != 0)				return __x->_pred;			else if(__x->_parent != 0 && __x->_parent->_pred != 0) {				__x = __x->_parent;				while(__x->_pred != 0 && __x->_pred->_last_child == 0) { __x = __x->_pred; }				if(__x->_pred->_last_child != 0)					return __x->_pred->_last_child;				else					return __x->_parent->_last_child;			}  else				return __x->_succ;		}	private:		std::queue< _base_ptr >	_q_of_first;	};	template< typename item_type, typename traversal_scheme = pre_order >	class tree_iterator {			typedef tree_iterator<item_type, traversal_scheme>	_self;		        typedef const tree_node<item_type>*					_const_link_type;		typedef tree_node<item_type>*						_link_type;		typedef tree_node_base::base_ptr					_base_ptr;		typedef traversal_scheme							_traversal_policy;	public:		typedef std::bidirectional_iterator_tag				iterator_category;		typedef ::ptrdiff_t									difference_type;		typedef item_type									value_type;		typedef item_type&									reference;		typedef item_type*									pointer;	//private:		_traversal_policy	_trav_policy;		_base_ptr			_M_node;	public:		tree_iterator(): _trav_policy(), _M_node(0) {}				tree_iterator(_link_type __x, const _traversal_policy& __t = _traversal_policy())		: _M_node(__x), _trav_policy(__t) { }		template< typename trav_type >		tree_iterator(const tree_iterator< item_type, trav_type >& __i)		:	_M_node(__i._M_node),			_trav_policy() {}		tree_iterator(const _self& __i)		:	_M_node(__i._M_node),			_trav_policy(__i._trav_policy) {}		template< typename trav_type >		_self& operator=(const tree_iterator< item_type, trav_type >& __it) {			if(this != &__it) {                _M_node			=	__it._M_node;				_trav_policy	=	_traversal_policy();			}			return *this;		}		_self& operator=(const _self& __it) {			if(this != &__it) {                _M_node			=	__it._M_node;				_trav_policy	=	__it._trav_policy;			}			return *this;		}        reference operator*() const {			return static_cast<_link_type>(_M_node)->_elem;		}        pointer operator->() const {			return &static_cast<_link_type>(_M_node)->_elem;		}				_self& operator++() {            _M_node = _trav_policy.tree_increment(_M_node);            return *this;		}        _self operator++(int) {            _self __tmp = *this;            _M_node = _trav_policy.tree_increment(_M_node);            return __tmp;		}        _self& operator--() {            _M_node = _trav_policy.tree_decrement(_M_node);            return *this;		}        _self operator--(int) {            _self __tmp = *this;			_M_node = _trav_policy.tree_decrement(_M_node);            return __tmp;		}		template<typename trav_type>		bool operator==(const tree_iterator< item_type, trav_type >& __x) const {			return _M_node == __x._M_node;		}		template< typename trav_type >		bool operator!=(const tree_iterator< item_type, trav_type >& __x) const {			return _M_node != __x._M_node;		}        bool operator==(const _self& __x) const {			return _M_node == __x._M_node;		}        bool operator!=(const _self& __x) const {			return _M_node != __x._M_node;		}	};	template<typename item_type, class traversal_scheme = pre_order >	class const_tree_iterator {			typedef const_tree_iterator<item_type>		_self;        typedef tree_node_base::const_base_ptr		_base_ptr;        typedef const tree_node<item_type>*			_link_type;		typedef traversal_scheme					_traversal_policy;	public:				typedef std::bidirectional_iterator_tag		iterator_category;		typedef tree_iterator<item_type>			iterator;		typedef	const item_type&					reference;		typedef const item_type*					pointer;		typedef ptrdiff_t							difference_type;		typedef item_type							value_type;        	//private:		_traversal_policy	_trav_policy;		_base_ptr			_M_node;	public:		const_tree_iterator()		:	_trav_policy(),			_M_node(0) {}        		const_tree_iterator(_link_type __x, const _traversal_policy& __t = _traversal_policy())		:	_M_node(__x),			_trav_policy(__t) {}				template< typename trav_type >		const_tree_iterator(const tree_iterator< item_type, trav_type >& __it)		:	_M_node(__it._M_node),			_trav_policy() {}		const_tree_iterator(const iterator& __it)		:	_M_node(__it._M_node),			_trav_policy(__it._trav_policy) {}		template< typename trav_type >		_self& operator=(const tree_iterator< item_type, trav_type>& __it) {			if(this != &__it) {                _M_node			=	__it._M_node;				_trav_policy	=	_traversal_policy();			}			return *this;		}		_self& operator=(const iterator& __it) {			if(this != &__it) {				_M_node			=	__it._M_node;                _trav_policy	=	__it._trav_policy;			}			return *this;		}        reference operator*() const {			return static_cast<_link_type>(_M_node)->_elem;		}        pointer operator->() const {			return &static_cast<_link_type>(_M_node)->_elem;		}        _self& operator++() {            _M_node = _trav_policy.tree_increment(_M_node);            return *this;		}        _self operator++(int) {            _self __tmp = *this;            _M_node = _trav_policy.tree_increment(_M_node);            return __tmp;		}				_self& operator--() {            _M_node = _trav_policy.tree_decrement(_M_node);            return *this;		}				_self operator--(int) {            _self __tmp = *this;            _M_node	=	_trav_policy.tree_decrement(_M_node);            return __tmp;		}		template<typename trav_type>		bool operator==(const const_tree_iterator< item_type, trav_type >& __x) const {			return _M_node == __x._M_node;		}		template<typename trav_type>		bool operator!=(const const_tree_iterator< item_type, trav_type >& __x) const {			return _M_node != __x._M_node;		}        bool operator==(const _self& __x) const {			return _M_node == __x._M_node;		}		bool operator!=(const _self& __x) const {			return _M_node != __x._M_node;		}	};	template<typename _Val, typename trav1, typename trav2>	inline bool operator==(	const tree_iterator<_Val, trav1 >& __x,							const const_tree_iterator<_Val, trav2 >& __y) {		return __x._M_node == __y._M_node;	}								template<typename _Val, typename trav1, typename trav2>	inline bool operator!=(	const tree_iterator< _Val, trav1 >& __x,							const const_tree_iterator< _Val, trav2 >& __y) {		return __x._M_node != __y._M_node;	}	template<typename _Val>	inline bool operator==(	const tree_iterator<_Val>& __x,							const const_tree_iterator<_Val>& __y) {		return __x._M_node == __y._M_node;	}								template< typename _Val>	inline bool operator!=(	const tree_iterator<_Val>& __x,							const const_tree_iterator<_Val>& __y) {		return __x._M_node != __y._M_node;	}	template< typename item_type, typename _Alloc = std::allocator< item_type > >	class tree_base {	protected:				typedef typename _Alloc::template rebind< tree_node< item_type > >::other _node_allocator;		typedef tree_node_base*			_base_ptr;		typedef const tree_node_base*	_const_base_ptr;        typedef tree_node< item_type >	_tree_node;		typedef _tree_node*				_link_type;		typedef const _tree_node*		_const_link_type;	public:		typedef item_type				value_type;		typedef _Alloc					allocator_type;		typedef ::size_t				size_type;	protected:		struct tree_impl : public _node_allocator {            tree_node_base	_M_header;            size_type 		_M_node_count; // Keeps track of size of tree.            tree_impl(const _node_allocator& __a = _node_allocator())			:	_node_allocator(__a),				_M_node_count(0),				_M_header()			{				this->_M_header._parent			=	0;				this->_M_header._first_child	=	&this->_M_header;						this->_M_header._last_child		=	&this->_M_header;				this->_M_header._pred			=	&this->_M_header;				this->_M_header._succ			=	0;			}		};	private:        tree_impl _M_impl;	protected:		//conversion utils		static _link_type _M_parent(_base_ptr __x) {			return static_cast<_link_type>(__x->_parent);		}		static _const_link_type _M_parent(_const_base_ptr __x) {			return static_cast<_const_link_type>(__x);		}		static _link_type _M_first(_base_ptr __x) {			return static_cast<_link_type>(__x->_first_child);		}		static _const_link_type _M_first(_const_base_ptr __x) {			return static_cast<_const_link_type>(__x->_first_child);		}		static _link_type _M_last(_base_ptr __x) {			return static_cast<_link_type>(__x->_last_child);		}		static _const_link_type _M_last(_const_base_ptr __x) {			return static_cast<_const_link_type>(__x->_last_child);		}		static _link_type _M_succ(_base_ptr __x){ 			return static_cast<_link_type>(__x->_succ);		}		static _const_link_type _M_succ(_const_base_ptr __x) {			return static_cast<_const_link_type>(__x->_succ);		}		static _link_type _M_pred(_base_ptr __x) {			return static_cast<_link_type>(__x->_pred);		}		static _const_link_type _M_pred(_const_base_ptr __x) {			return static_cast<_const_link_type>(__x->_pred);		}		static _link_type _M_cast_node(_base_ptr __x) {			return static_cast<_link_type>(__x);		}		static _const_link_type _M_cast_node(_const_base_ptr __x) {			return static_cast<_const_link_type>(__x);		}		_base_ptr& _M_bottom_first() { return _M_impl._M_header._first_child; }				_const_base_ptr _M_bottom_first() const { return _M_impl._M_header._first_child; }		_base_ptr& _M_bottom_last() { return _M_impl._M_header._last_child; }				_const_base_ptr _M_bottom_last() const { return _M_impl._M_header._last_child; }		_base_ptr& _M_root() { return this->_M_impl._M_header._pred; }		_const_base_ptr _M_root() const { return this->_M_impl._M_header._pred; }		/////////////////////////////////////////////////////////////////////////////////		_link_type _M_pre_begin() { return static_cast<_link_type>(this->_M_impl._M_header._pred); }		_const_link_type _M_pre_begin() const { return static_cast<_const_link_type>(this->_M_impl._M_header._pred); }				_link_type _M_pre_end() { return static_cast<_link_type>(&this->_M_impl._M_header); }				_const_link_type _M_pre_end() const { return static_cast<_const_link_type>(&this->_M_impl._M_header); }		////////////////////////////////////////////////////////////////////////////////		_link_type _M_post_begin() { return static_cast<_link_type>(this->_M_impl._M_header._first_child); }				_const_link_type _M_post_begin() const { return static_cast<_const_link_type>(this->_M_impl._M_header._first_child); }		_link_type _M_post_end() { return static_cast<_link_type>(&this->_M_impl._M_header); }				_const_link_type _M_post_end() const { return static_cast<_const_link_type>(&this->_M_impl._M_header); }		/////////////////////////////////////////////////////////////////////////////////        _link_type _M_begin() { return static_cast<_link_type>(this->_M_impl._M_header._pred); }       _const_link_type _M_begin() const { return static_cast<_const_link_type>(this->_M_impl._M_header._pred); }       _link_type _M_end() { return static_cast<_link_type>(&this->_M_impl._M_header); }       	   _const_link_type _M_end() const { return static_cast<_const_link_type>(&this->_M_impl._M_header); }		_tree_node* _M_get_node() {			return _M_impl._node_allocator::allocate(1);		}				void _M_put_node(_tree_node* __p) {			_M_impl._node_allocator::deallocate(__p, 1);		}				_link_type _M_create_node(const item_type& __x) {            _link_type __tmp = _M_get_node();            			try { 				std::_Construct(&__tmp->_elem, __x);			} catch(...) {                _M_put_node(__tmp);                __throw_exception_again;            }            return __tmp;		}         _link_type _M_clone_node(_const_link_type __x) {            _link_type __tmp = _M_create_node(__x->_elem);			__tmp->_parent		=	0;            __tmp->_pred		=	0;            __tmp->_succ		=	0;			__tmp->_first_child	=	0;			__tmp->_last_child	=	0;            return __tmp;		}		void _M_init() {			_M_impl._M_header._parent		=	0;			_M_impl._M_header._first_child	=	&_M_impl._M_header;					_M_impl._M_header._last_child	=	&_M_impl._M_header;			_M_impl._M_header._pred			=	&_M_impl._M_header;			_M_impl._M_header._succ			=	0;			_M_impl._M_node_count			=	0;		}		_link_type		_M_copy(_const_link_type __x, _link_type __p);				size_type _M_count_nodes(_const_base_ptr) const;		void _M_swap(_base_ptr __x) {			//swap headers			_base_ptr tmp_link				=	_M_impl._M_header._last_child;			_M_impl._M_header._last_child	=	__x->_last_child;			__x->_last_child				=	tmp_link;			tmp_link						=	_M_impl._M_header._first_child;			_M_impl._M_header._first_child	=	__x->_first_child;			__x->_first_child				=	tmp_link;			tmp_link						=	_M_impl._M_header._pred->_succ;			_M_impl._M_header._pred->_succ	=	__x->_pred->_succ;			__x->_pred->_succ				=	tmp_link;			tmp_link						=	_M_impl._M_header._pred;			_M_impl._M_header._pred			=	__x->_pred;			__x->_pred						=	tmp_link;		}		void _M_detach_node(_base_ptr __x) {			if(	(__x == __x->_parent->_first_child) &&				(__x == __x->_parent->_last_child)) {		// most special case 0 pos is only child				__x->_parent->_first_child	=	0;				__x->_parent->_last_child	=	0;			} else if(__x == __x->_parent->_first_child) {// special case 1 pos is at first child				__x->_parent->_first_child	=	__x->_succ;				__x->_succ->_pred			=	0;				__x->_succ					=	0;			} else if(__x == __x->_parent->_last_child) {// special case 2 pos is at last				__x->_parent->_last_child	=	__x->_pred;				__x->_pred->_succ			=	0;				__x->_succ					=	0;			} else {// general case				__x->_pred->_succ	=	__x->_succ;                __x->_succ->_pred	=	__x->_pred;				__x->_pred			=	0;				__x->_succ			=	0;			}		}		//destructive erase	   void _M_erase(_link_type __x);	   //non-destructive single erase	   void _M_erase_leaf(_link_type __pos) {		   if(__pos->_parent != 0) {			if(	(__pos == __pos->_parent->_first_child) &&				(__pos == __pos->_parent->_last_child)) {			  					__pos->_parent->_first_child	=	0;					__pos->_parent->_last_child		=	0;			} else if(__pos == __pos->_parent->_first_child) {				__pos->_parent->_first_child	=	__pos->_succ;				__pos->_succ->_pred			=	0;			} else if(__pos == __pos->_parent->_last_child) {					__pos->_parent->_last_child	=	__pos->_pred;				__pos->_pred->_succ			=	0;			} else {					__pos->_succ->_pred	=	__pos->_pred;				__pos->_pred->_succ	=	__pos->_succ;				}		  }		  destroy_node(__pos);	   }	   // non-destructive erase-all	   void _M_erase_all(_link_type __pos);       void destroy_node(_link_type __p) {		   std::_Destroy(&__p->_elem);            _M_put_node(__p);		}	   const size_type& _M_size() const {			return _M_impl._M_node_count;		}		size_type& _M_size() {			return _M_impl._M_node_count;		}		template<typename trav_type>		_link_type _M_insert(tree_iterator< item_type, trav_type >& itr, const item_type& __v) {			_link_type __z = _M_create_node(__v);					__z->_first_child	=	0;			__z->_last_child	=	0;			__z->_parent		=	0;			__z->_succ			=	0;			if(_M_root() == _M_end()) {				__z->_succ			=	&_M_impl._M_header;				_M_root()			=	__z; //root of the tree								_M_impl._M_header._first_child	=	__z;				_M_impl._M_header._last_child	=	__z;			} else if(itr._M_node == _M_root()) {                				return static_cast<_link_type>(itr._M_node);				} else {									if(itr._M_node == itr._M_node->_parent->_first_child) {				//insert front					__z->_parent							=	itr._M_node->_parent;					__z->_succ								=	itr._M_node;					itr._M_node->_pred						=	__z;					itr._M_node->_parent->_first_child		=	__z;				} else {					//insert back					__z->_parent				=	itr._M_node->_parent;					__z->_succ					=	itr._M_node;					__z->_pred					=	itr._M_node->_pred;					itr._M_node->_pred->_succ	=	__z;					itr._M_node->_pred			=	__z;					}								_M_bottom_first()	=	_tree_node::most_bottom_first_child(_M_root());				_M_bottom_last()	=	_tree_node::most_bottom_last_child(_M_root());			}			++_M_size();			return __z;		}		template<typename trav_type>		_link_type _M_insert_child(tree_iterator< item_type, trav_type >& itr, const item_type& __v) {			 _link_type __z = _M_create_node(__v);					__z->_first_child	=	0;			__z->_last_child	=	0;			__z->_parent		=	0;			__z->_pred			=	0;			__z->_succ			=	0;			if(_M_root() == _M_end()) {								__z->_succ			=	&_M_impl._M_header;				_M_root()			=	__z; //root of the tree				_M_impl._M_header._first_child	=	__z;				_M_impl._M_header._last_child	=	__z;			} else {				if(itr._M_node->_first_child == 0) {                    // append front                    __z->_parent				=	itr._M_node;                    itr._M_node->_first_child	=	__z;                    itr._M_node->_last_child	=	__z;				} else {					//append back					__z->_parent				=	itr._M_node;					__z->_pred					=	itr._M_node->_last_child;					itr._M_node->_last_child->_succ		=	__z;					itr._M_node->_last_child			=	__z;				}				_M_bottom_first()	=	_tree_node::most_bottom_first_child(_M_root());				_M_bottom_last()	=	_tree_node::most_bottom_last_child(_M_root());			}			++_M_size();			return __z;		}		_link_type _M_insert_child(_link_type& pos, _link_type& __z) {			if(pos->_first_child == 0) {                    // append front				__z->_parent		=	pos;				pos->_first_child	=	__z;                pos->_last_child	=	__z;			} else {				//append back				__z->_parent				=	pos;				__z->_pred					=	pos->_last_child;				pos->_last_child->_succ		=	__z;				pos->_last_child			=	__z;			}			return __z;		}		public:		// allocation/deallocation		tree_base(const allocator_type& __a)		:	_M_impl(__a) {}        ~tree_base() {			if(_M_begin() != _M_end())                _M_erase(_M_begin());		}		allocator_type get_allocator() const {			return *static_cast<const _node_allocator*>(&this->_M_impl);		}	};	// destructive erase, for clear and deconstructor only	template<typename item_type, typename _Alloc >	void tree_base< item_type, _Alloc >::_M_erase(typename tree_base< item_type, _Alloc >::_link_type __x) {			//recursively destroy			_base_ptr _curr	=	__x->_first_child;			_base_ptr _tmp		=	0;			while(_curr != 0) {				_tmp		=	_curr->_succ;				_M_erase(_M_cast_node(_curr));				_curr	=	_tmp;			}			destroy_node(__x);	}	// non destructive erase	template<typename item_type, typename _Alloc >	void tree_base< item_type, _Alloc >::_M_erase_all(typename tree_base< item_type, _Alloc >::_link_type __pos) {        _base_ptr _curr		=	__pos->_first_child;		_base_ptr _tmp		=	0;		while(_curr != 0) {			_tmp		=	_curr->_succ;			_M_erase_all(_M_cast_node(_curr));			_curr	=	_tmp;		}		_M_erase_leaf(__pos);	}	template<typename item_type, typename _Alloc >	typename tree_base< item_type, _Alloc >::_link_type	tree_base< item_type, _Alloc >::_M_copy(typename tree_base< item_type, _Alloc >::_const_link_type __x,											typename tree_base< item_type, _Alloc >::_link_type __p) {      // Structural copy      _link_type __top		=	_M_clone_node(__x);	  if(__p == _M_end()) {		  //special case making connection with the root & header		  __top->_succ		=	__p;		  __p->_pred		=	__top;	  } else {          __top->_parent	=	__p;	  }	  try {			_const_base_ptr _curr = __x->_first_child;			while(_curr != 0) {				_link_type new_kid = _M_copy(_M_cast_node(_curr), __top);				_M_insert_child(__top, new_kid);				_curr = _curr->_succ;			}	  } catch(...) {          _M_erase(__top);          __throw_exception_again;	  }      return __top;	}	template<typename item_type, typename _Alloc >	typename tree_base< item_type, _Alloc >::size_type	tree_base< item_type, _Alloc >::	_M_count_nodes(typename tree_base< item_type, _Alloc >::_const_base_ptr __x) const {		size_type size = 0;		_const_base_ptr _curr = __x->_first_child;		if(_curr != _M_end()) {            while(_curr != 0) {				size += _M_count_nodes(_curr);				_curr = _curr->_succ;			}			++size;		}		return size;	}	template< typename item_type, typename _Alloc = std::allocator< item_type > >	class tree : protected tree_base< item_type, _Alloc > {		 		typedef tree_base< item_type, _Alloc >							_base;		typedef typename _base::_link_type								_link_type;        typedef typename _base::_const_link_type						_const_link_type;		typedef typename _base::_base_ptr								_base_ptr;		typedef typename _base::_const_base_ptr							_const_base_ptr;		using _base::_M_swap;		using _base::_M_copy;		using _base::_M_insert_child;		using _base::_M_get_node;		using _base::_M_cast_node;		using _base::_M_count_nodes;		using _base::_M_put_node;		using _base::_M_root;		using _base::_M_end;		using _base::_M_begin;		using _base::_M_pre_begin;		using _base::_M_post_begin;		using _base::_M_post_end;		using _base::_M_pre_end;		using _base::_M_size;		using _base::_M_bottom_first;		using _base::_M_bottom_last;		using _base::_M_parent;		using _base::_M_init;		using _base::_M_detach_node;	public:		using _base::get_allocator;		typedef item_type												value_type;		typedef value_type*												pointer;		typedef const value_type*										const_pointer;		typedef value_type&												reference;		typedef const value_type&										const_reference;		typedef ::ptrdiff_t												difference_type;		typedef typename _base::size_type								size_type;		typedef typename _base::allocator_type							allocator_type;		typedef tree_iterator<value_type>								iterator;		typedef const_tree_iterator<value_type>							const_iterator;		typedef tree_iterator< value_type, pre_order >					pre_order_itr;		typedef const_tree_iterator<value_type, pre_order >				const_pre_order_itr;		typedef tree_iterator< value_type, post_order >					post_order_itr;		typedef const_tree_iterator< value_type, post_order >			const_post_order_itr;		typedef tree_iterator< value_type, breadth_first >				breadth_first_itr;		typedef const_tree_iterator< value_type, breadth_first >		const_breadth_first_itr;		typedef std::reverse_iterator< iterator >						reverse_iterator;		typedef std::reverse_iterator< const_iterator >					const_reverse_iterator;		typedef std::reverse_iterator< pre_order_itr >					reverse_pre_itr;		typedef std::reverse_iterator< const_pre_order_itr >			const_reverse_pre_itr;		typedef std::reverse_iterator< post_order_itr >					reverse_post_itr;		typedef std::reverse_iterator< const_post_order_itr >			const_reverse_post_itr;	private:		//special constructor for substree operation		tree(_base_ptr __x, const allocator_type& __a = allocator_type())		: _base(__a) {			_M_root()			=	__x;			__x->_succ			=	_M_end();			_M_bottom_first()	=	tree_node_base::most_bottom_first_child(_M_root());			_M_bottom_last()	=	tree_node_base::most_bottom_last_child(_M_root());			_M_size()			=	_M_count_nodes(_M_begin());		}	public:		explicit tree(const allocator_type& __a = allocator_type())		: _base(__a) {}		tree(const tree< item_type, _Alloc >& t): _base(t.get_allocator()) {			if(t._M_root() != 0 && t._M_root() != t._M_end()) {                _M_root()			=	_M_copy(t._M_begin(), _M_end());				_M_bottom_first()	=	tree_node_base::most_bottom_first_child(_M_root());				_M_bottom_last()	=	tree_node_base::most_bottom_last_child(_M_root());				_M_size()			=	t._M_size();			}		}		template< typename trav_type >		tree(	tree_iterator< item_type, trav_type >& __top,				const allocator_type& __a = allocator_type())		: _base(__a) {			_M_root()			=	_M_copy(_M_cast_node(__top._M_node), _M_end());			_M_bottom_first()	=	tree_node_base::most_bottom_first_child(_M_root());			_M_bottom_last()	=	tree_node_base::most_bottom_last_child(_M_root());			_M_size()			=	_M_count_nodes(_M_begin());		}		tree<item_type, _Alloc>& operator=(const tree<item_type, _Alloc>&);		iterator begin() { return _M_begin(); }		const_iterator begin() const { return _M_begin(); }		reverse_iterator rbegin() { return reverse_iterator(end()); }		const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }		iterator end() { return _M_end(); }		const_iterator end() const { return _M_end(); }		reverse_iterator rend() { return reverse_iterator(begin()); }		const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }       	pre_order_itr pre_begin() { return _M_pre_begin(); }		const_pre_order_itr pre_begin() const { return _M_pre_begin(); }		pre_order_itr pre_end() { return _M_pre_end(); }		const_pre_order_itr pre_end() const { return _M_pre_end(); }		post_order_itr post_begin() { return _M_post_begin(); }		const_post_order_itr post_begin() const { return _M_post_begin(); }		post_order_itr post_end() { return _M_post_end(); }		const_post_order_itr post_end() const { return _M_post_end(); }		breadth_first_itr breadth_begin() { return _M_begin(); }		const_breadth_first_itr breadth_begin() const { return _M_begin(); }		breadth_first_itr breadth_end() { return 0; }//_M_end(); }		const_breadth_first_itr breadth_end() const { return 0; }//_M_end(); }		reverse_pre_itr pre_rbegin() { return reverse_pre_itr(pre_end()); }        const_reverse_pre_itr pre_rbegin() const { return const_reverse_pre_itr(pre_end()); }		reverse_pre_itr pre_rend() { return reverse_pre_itr(pre_begin()); }        const_reverse_pre_itr pre_rend() const { return const_reverse_pre_itr(pre_begin()); }		reverse_post_itr post_rbegin() { return reverse_post_itr(_M_begin()); }        const_reverse_post_itr post_rbegin() const { return const_reverse_post_itr(_M_begin()); }		reverse_post_itr post_rend() { return reverse_post_itr(post_begin()); }        const_reverse_post_itr post_rend() const { return const_reverse_post_itr(post_begin()); }		template<class trav_type>		tree_iterator< item_type, trav_type > root() { return (_M_begin()); }		template<class trav_type>		const_tree_iterator< item_type, trav_type > root() const { return(_M_begin()); }		template<class trav_type>		std::reverse_iterator< tree_iterator< item_type, trav_type > >		rroot() {			return std::reverse_iterator< tree_iterator< item_type, trav_type > >(_M_begin());		}		template< typename trav_type >		std::reverse_iterator< const_tree_iterator< item_type, trav_type > >		rroot() const {			return std::reverse_iterator< const_tree_iterator< item_type, trav_type > >(_M_begin());		}        bool empty() const { return _M_size() == 0; }        size_type size() const { return _M_size(); }		size_type max_size() const { return size_type(-1); }		//returns number of children		template< typename trav_type >		size_type child_size(const_tree_iterator< item_type, trav_type >) const;		//returns number of children		template< typename trav_type >		size_type child_size(tree_iterator< item_type, trav_type >) const;		template< typename trav_type >		size_type depth(const_tree_iterator< item_type, trav_type >) const;		template< typename trav_type >		size_type depth(tree_iterator< item_type, trav_type >) const;       	//insert sibiling        template< typename trav_type1, typename trav_type2 >		tree_iterator< item_type, trav_type2 >		insert(tree_iterator< item_type, trav_type1 >, const item_type&);		template< typename trav_type >		tree_iterator< item_type, trav_type>		insert(tree_iterator< item_type, trav_type>, const item_type&);		template< typename InputIter, typename trav_type >		void insert(tree_iterator< item_type, trav_type>, InputIter, InputIter);		template< typename trav_type1, typename trav_type2 >		tree_iterator< item_type, trav_type2 >		add_child(tree_iterator< item_type, trav_type1 >, const value_type&);		template< typename trav_type >		tree_iterator< item_type, trav_type >		add_child(tree_iterator< item_type, trav_type >, const value_type&);		template< typename InputIter, typename trav_type >		void		add_child(tree_iterator< item_type, trav_type>, InputIter, InputIter);		//destructive erase, deletes any children aswell		template< typename trav_type >		void erase(tree_iterator< item_type, trav_type >);				template< typename trav_type >		void erase(tree_iterator< item_type, trav_type >, tree_iterator< item_type, trav_type >);		//non destructive erase, inflates the child into the previous location of the deleted node		template< typename trav_type >		void erase_child(tree_iterator< item_type, trav_type >);				template< typename trav_type >		void erase_child(tree_iterator< item_type, trav_type >, tree_iterator< item_type, trav_type >);        		void swap(tree< item_type, _Alloc >&);		template< typename trav_type >		tree_iterator< item_type, trav_type > find(const value_type& __x);		template< typename trav_type >		const_tree_iterator< item_type, trav_type > find(const value_type& __x) const;		iterator find(const value_type& __x);		const_iterator find(const value_type& __x) const;		template< typename trav_type, typename trav_type2 >		tree_iterator< item_type, trav_type2 >		child(tree_iterator< item_type, trav_type >, size_type);		template< typename trav_type >		tree_iterator< item_type, trav_type >		child(tree_iterator< item_type, trav_type >, size_type);		template< typename trav_type, typename trav_type2 >		const_tree_iterator< item_type, trav_type2 >		child(const_tree_iterator< item_type, trav_type >, size_type) const;		template< typename trav_type >		const_tree_iterator< item_type, trav_type >		child(const_tree_iterator< item_type, trav_type >, size_type) const;		template< typename trav_type, typename trav_type2 >		std::pair<	tree_iterator< item_type, trav_type2 >, 					tree_iterator< item_type, trav_type2 > >		children(tree_iterator< item_type, trav_type > pos) {						return std::make_pair(	_M_cast_node(pos._M_node->_parent->_first_child),									_M_cast_node(pos._M_node->_parent->_last_child));		}		template< typename trav_type, typename trav_type2 >		std::pair<	const_tree_iterator< item_type, trav_type2 >, 					const_tree_iterator< item_type, trav_type2 > >		children(const_tree_iterator< item_type, trav_type > pos) const {			return std::make_pair(	_M_cast_node(pos._M_node->_parent->_first_child),									_M_cast_node(pos._M_node->_parent->_last_child));		}		template< typename trav_type >		std::pair<	tree_iterator< item_type, trav_type >, 					tree_iterator< item_type, trav_type > >		children(tree_iterator< item_type, trav_type > pos) {			return std::make_pair(	_M_cast_node(pos._M_node->_parent->_first_child),									_M_cast_node(pos._M_node->_parent->_last_child));		}		template< typename trav_type >		std::pair<	const_tree_iterator< item_type, trav_type >, 					const_tree_iterator< item_type, trav_type > >		children(const_tree_iterator< item_type, trav_type > pos)  const {			return std::make_pair(	_M_cast_node(pos._M_node->_parent->_first_child),									_M_cast_node(pos._M_node->_parent->_last_child));		}		template< typename trav_type, typename trav_type2 >		tree_iterator< item_type, trav_type2 >		parent(tree_iterator< item_type, trav_type > pos) {			return _M_parent(pos._M_node);		}		template< typename trav_type, typename trav_type2 >		const_tree_iterator< item_type, trav_type2 >		parent(const_tree_iterator< item_type, trav_type > pos) const {			return _M_parent(pos._M_node);		}		template< typename trav_type >		tree_iterator< item_type, trav_type >		parent(tree_iterator< item_type, trav_type > pos) {			return _M_parent(pos._M_node);		}		template< typename trav_type >		const_tree_iterator< item_type, trav_type >		parent(const_tree_iterator< item_type, trav_type > pos) const {			return _M_parent(pos._M_node);		}		template< typename trav_type >		tree< item_type, _Alloc > subtree(tree_iterator< item_type, trav_type >);		template< typename trav_type >		bool is_root(tree_iterator< item_type, trav_type >) const;		template< typename trav_type >		bool is_root(const_tree_iterator< item_type, trav_type >) const;		template< typename trav_type >		bool is_parent(tree_iterator< item_type, trav_type >) const;		template< typename trav_type >		bool is_parent(const_tree_iterator< item_type, trav_type >) const;		template < typename trav_type >		bool is_child_of(tree_iterator< item_type, trav_type >, tree_iterator< item_type, trav_type >) const;		template< typename trav_type >		bool is_child_of(const_tree_iterator< item_type, trav_type >, const_tree_iterator< item_type, trav_type >) const;		template< typename trav_type >		bool is_leaf(tree_iterator< item_type, trav_type >) const;		template< typename trav_type >		bool is_leaf(const_tree_iterator< item_type, trav_type >) const;		void clear(){            _M_erase(_M_begin());			_M_init();		}	};	template< typename item_type, typename _Alloc >	inline bool operator==(	const tree< item_type, _Alloc >& __x,							const tree< item_type, _Alloc >& __y) {		return ((__x.size() == __y.size()) && std::equal(__x.begin(), __x.end(),														 __y.begin()));	}	template< typename item_type, typename _alloc >	inline bool operator!=(	const tree< item_type, _alloc >& __x,							const tree< item_type, _alloc >& __y) {		return !(__x == __y);	}	template< typename item_type, typename _Alloc >	tree< item_type, _Alloc >&	tree< item_type, _Alloc >::operator=(const tree< item_type, _Alloc >& __x) {		if (this != &__x) {            if (__x._M_root() != 0 && __x._M_root() != __x._M_end()) {				clear();                _M_root()			=	_M_copy(__x._M_begin(), _M_end());				_M_bottom_first()	=	tree_node_base::most_bottom_first_child(_M_root());				_M_bottom_last()	=	tree_node_base::most_bottom_last_child(_M_root());                _M_size()			=	__x._M_size();			}		}        return *this;	}	template<typename item_type, typename _Alloc >	template< typename trav_type1, typename trav_type2 >	inline tree_iterator< item_type, trav_type2 >	tree< item_type, _Alloc >::insert(	tree_iterator< item_type, trav_type1 > itr,										const item_type& __v) {		return _M_insert(itr, __v);	}	template<typename item_type, typename _Alloc >	template<typename trav_type>	inline tree_iterator< item_type, trav_type>	tree< item_type, _Alloc >::insert(	tree_iterator< item_type, trav_type > itr,										const item_type& __v) {		return _M_insert(itr, __v);	}	template<typename item_type, typename _Alloc >	template<typename InputIter, typename trav_type>	inline void	tree< item_type, _Alloc >::insert(	tree_iterator< item_type, trav_type > pos,										InputIter first, InputIter last) {			for(; first != last; ++first) {				_M_insert(pos, *first);			}	}	template<typename item_type, typename _Alloc >	template<typename trav_type>	inline void tree<item_type, _Alloc >::erase(tree_iterator< item_type, trav_type> pos) {		bool needs_init = false;		if(pos._M_node == _M_root()) {			needs_init = true;		}		_M_erase_all(_M_cast_node(pos._M_node));		if(needs_init) {			_M_init();           		} else {			_M_bottom_first()	=	tree_node_base::most_bottom_first_child(_M_root());            _M_bottom_last()	=	tree_node_base::most_bottom_last_child(_M_root());		}	}		template<typename item_type, typename _Alloc >	template<typename trav_type>	inline void tree<item_type, _Alloc >::erase(tree_iterator< item_type, trav_type> __first,												tree_iterator< item_type, trav_type> __last) {		if(	(__first._M_node != _M_root()) &&			(__first._M_node->_parent == __last._M_node->_parent)) {			_base_ptr __tmp		=	0;			_base_ptr __curr	=	__first._M_node;			while(__curr != 0 && __curr != __last._M_node) {				__tmp	=	__curr->_succ;                _M_erase_all(_M_cast_node(__curr));				__curr	=	__tmp;			}			_M_bottom_first()	=	tree_node_base::most_bottom_first_child(_M_root());			_M_bottom_last()	=	tree_node_base::most_bottom_last_child(_M_root());		}	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline void tree< item_type, _Alloc >::erase_child(tree_iterator< item_type, trav_type> pos) {		if(	pos._M_node->_parent != 0) {						if(	(pos._M_node->_first_child != 0) && 				(pos._M_node->_last_child != 0)) {								//for each child in pos				_base_ptr _curr = pos._M_node->_first_child;				while(_curr != 0) {					_curr->_parent	=	pos._M_node->_parent;					_curr = _curr->_succ;				}				if(	(pos._M_node == pos._M_node->_parent->_first_child) &&					(pos._M_node == pos._M_node->_parent->_last_child)) {		// most special case 0 pos is only child					pos._M_node->_parent->_first_child	=	pos._M_node->_first_child;					pos._M_node->_parent->_last_child	=	pos._M_node->_last_child;				} else if(pos._M_node == pos._M_node->_parent->_first_child) {// special case 1 pos is at first child					pos._M_node->_last_child->_succ		=	pos._M_node->_succ;					pos._M_node->_succ->_pred			=	pos._M_node->_last_child;					pos._M_node->_parent->_first_child	=	pos._M_node->_first_child;				} else if(pos._M_node == pos._M_node->_parent->_last_child) {// special case 2 pos is at last					pos._M_node->_first_child->_pred	=	pos._M_node->_pred;					pos._M_node->_pred->_succ			=	pos._M_node->_first_child;					pos._M_node->_parent->_last_child	=	pos._M_node->_last_child;				} else {// general case					pos._M_node->_first_child->_pred	=	pos._M_node->_pred;					pos._M_node->_last_child->_succ		=	pos._M_node->_succ;					pos._M_node->_pred->_succ			=	pos._M_node->_first_child;					pos._M_node->_succ->_pred			=	pos._M_node->_last_child;				}								destroy_node(_M_cast_node(pos._M_node));				_M_bottom_first()	=	tree_node_base::most_bottom_first_child(_M_root());				_M_bottom_last()	=	tree_node_base::most_bottom_last_child(_M_root());			} else {//its a leaf				_M_erase_leaf(_M_cast_node(pos._M_node));			}		}	}			template< typename item_type, typename _Alloc >	template< typename trav_type >	inline void tree<item_type, _Alloc >::erase_child(	tree_iterator< item_type, trav_type > __first,														tree_iterator< item_type, trav_type > __last) {		if(	(__first._M_node != _M_root()) &&			(__first._M_node->_parent == __last._M_node->_parent)) {			_base_ptr __tmp		=	0;			_base_ptr __curr	=	__first._M_node;			while(__curr != 0 && __curr != __last._M_node) {				__tmp	=	__curr->_succ;                erase_child(iterator(_M_cast_node(__curr)));				__curr	=	__tmp;			}			_M_bottom_first()	=	tree_node_base::most_bottom_first_child(_M_root());			_M_bottom_last()	=	tree_node_base::most_bottom_last_child(_M_root());		}	}	template< typename item_type, typename _Alloc >	inline void 	tree< item_type, _Alloc >::swap(tree< item_type, _Alloc >& tr) {		if(this != &tr) {			_M_swap(tr._M_end());			const size_type n	=	_M_size();			_M_size()			=	tr.size();			tr._M_size()		=	n;		}	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline tree_iterator< item_type, trav_type>	tree<item_type, _Alloc >::find(const item_type& __x) {		iterator curr = begin();		for(iterator _end = end();			curr != _end;			++curr){			if(__x == *curr)				break;						}		return _M_cast_node(curr._M_node);	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline const_tree_iterator< item_type, trav_type >	tree< item_type, _Alloc >::find(const item_type& __x) const {		const_iterator curr = begin();		for(const_iterator _end = end();			curr != _end;			++curr){			if(__x == *curr)				break;						}		return _M_cast_node(curr._M_node);	}	template< typename item_type, typename _Alloc >	inline typename tree< item_type, _Alloc >::iterator	tree<item_type, _Alloc >::find(const item_type& __x) {		iterator curr = begin();		for(iterator _end = end();			curr != _end;			++curr){			if(__x == *curr)				break;						}		return _M_cast_node(curr._M_node);	}	template< typename item_type, typename _Alloc >	inline typename tree< item_type, _Alloc >::const_iterator	tree< item_type, _Alloc >::find(const item_type& __x) const {		const_iterator curr = begin();		for(const_iterator _end = end();			curr != _end;			++curr){			if(__x == *curr)				break;						}		return _M_cast_node(curr._M_node);	}	template< typename item_type, typename _Alloc >    template< typename trav_type1, typename trav_type2 >    inline tree_iterator< item_type, trav_type2 >	tree< item_type, _Alloc >::add_child(tree_iterator< item_type, trav_type1 > itr, 											const typename tree< item_type, _Alloc >::value_type& __v) {		return _M_insert_child(itr, __v);	}	template< typename item_type, typename _Alloc >    template< typename trav_type >    inline tree_iterator< item_type, trav_type >	tree< item_type, _Alloc >::add_child(tree_iterator< item_type, trav_type > itr, 										const typename tree< item_type, _Alloc >::value_type& __v) {		return _M_insert_child(itr, __v);	}	template< typename item_type, typename _Alloc >	template< typename InputIter, typename trav_type >	inline void	tree< item_type, _Alloc >::add_child(tree_iterator< item_type, trav_type > pos, 											InputIter first,											InputIter last) {		for(; first != last; ++first) {			_M_insert_child(pos, *first);		}	}	template< typename item_type, typename _Alloc >	template< typename trav_type, typename trav_type2 >	inline tree_iterator< item_type, trav_type2 >	tree< item_type, _Alloc >::child(tree_iterator< item_type, trav_type > pos, size_type n) {		_base_ptr _curr = pos._M_node->_first_child;		while(_curr != 0 && n-- != 0)			_curr	=	_curr->_succ;		return _M_cast_node(_curr);	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline tree_iterator< item_type, trav_type >	tree< item_type, _Alloc >::child(tree_iterator< item_type, trav_type > pos, size_type n) {		_base_ptr _curr = pos._M_node->_first_child;		while(_curr != 0 && n-- != 0)			_curr	=	_curr->_succ;		return _M_cast_node(_curr);	}	template< typename item_type, typename _Alloc >	template< typename trav_type, typename trav_type2 >	inline const_tree_iterator< item_type, trav_type2 >	tree< item_type, _Alloc >::child(const_tree_iterator< item_type, trav_type > pos, size_type n) const {		_const_base_ptr _curr = pos._M_node->_first_child;		while(_curr != 0 && n-- != 0)			_curr	=	_curr->_succ;		return _M_cast_node(_curr);	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline const_tree_iterator< item_type, trav_type >	tree< item_type, _Alloc >::child(const_tree_iterator< item_type, trav_type > pos, size_type n) const {		_const_base_ptr _curr = pos._M_node->_first_child;		while(_curr != 0 && n-- != 0)			_curr	=	_curr->_succ;		return _M_cast_node(_curr);	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline tree< item_type, _Alloc > 	tree< item_type, _Alloc >::subtree(tree_iterator< item_type, trav_type > __pos) {		if(__pos._M_node->_parent != 0) {			_M_detach_node(__pos._M_node);			__pos._M_node->_parent = 0;		}		_M_bottom_first()	=	tree_node_base::most_bottom_first_child(_M_root());		_M_bottom_last()	=	tree_node_base::most_bottom_last_child(_M_root());		return __pos._M_node;	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline bool 	tree< item_type, _Alloc >::is_root(tree_iterator< item_type, trav_type > __r) const {		return (__r._M_node == _M_root());	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline bool 	tree< item_type, _Alloc >::is_root(const_tree_iterator< item_type, trav_type > __r) const {		return (__r._M_node == _M_root());	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline bool 	tree< item_type, _Alloc >::is_parent(tree_iterator< item_type, trav_type > ___p) const {		return !is_leaf(___p);	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline bool 	tree< item_type, _Alloc >::is_parent(const_tree_iterator< item_type, trav_type > ___p) const {		return !is_leaf(___p);	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline bool 	tree< item_type, _Alloc >::is_child_of(	tree_iterator< item_type, trav_type > __c,											tree_iterator< item_type, trav_type > __p) const {		return (__c._M_node->_parent == __p._M_node);	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline bool 	tree< item_type, _Alloc >::is_child_of(	const_tree_iterator< item_type, trav_type > __c,											const_tree_iterator< item_type, trav_type > __p) const {		return (__c._M_node->_parent == __p._M_node);	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline bool	tree< item_type, _Alloc >::is_leaf(tree_iterator< item_type, trav_type > __pos) const {		return ((__pos._M_node->_first_child == 0) && (__pos._M_node->_last_child == 0));	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline bool 	tree< item_type, _Alloc >::is_leaf(const_tree_iterator< item_type, trav_type > __pos) const {		return ((__pos._M_node->_first_child == 0) && (__pos._M_node->_last_child == 0));	}	//returns number of children	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline typename tree< item_type, _Alloc >::size_type	tree< item_type, _Alloc >::child_size(const_tree_iterator< item_type, trav_type > ___p) const {		_const_base_ptr _curr = ___p._M_node->_first_child;		size_type _child_size = 0;		while(_curr	!=	0) {			++_child_size;			_curr	=	_curr->_succ;		}		return _child_size;	}	//returns number of children	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline typename tree< item_type, _Alloc >::size_type	tree< item_type, _Alloc >::child_size(tree_iterator< item_type, trav_type > ___p) const {		_const_base_ptr _curr = ___p._M_node->_first_child;		size_type _child_size = 0;		while(_curr	!=	0) {			++_child_size;			_curr	=	_curr->_succ;		}		return _child_size;	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline typename tree< item_type, _Alloc >::size_type	tree< item_type, _Alloc >::depth(const_tree_iterator< item_type, trav_type > ___p) const {		size_type _depth_size = 0;		_const_base_ptr _curr = ___p._M_node->_parent;		while(_curr != 0) {			++_depth_size;			_curr	=	_curr->_parent;		}		return _depth_size;	}	template< typename item_type, typename _Alloc >	template< typename trav_type >	inline typename tree< item_type, _Alloc >::size_type	tree< item_type, _Alloc >::depth(tree_iterator< item_type, trav_type > ___p) const {		size_type _depth_size = 0;		_const_base_ptr _curr = ___p._M_node->_parent;		while(_curr != 0) {			++_depth_size;			_curr	=	_curr->_parent;		}		return _depth_size;	}}# endif

here is a little sample test:
main.cpp

#include "tree.hpp"using std::tree;#include <string>#include <vector>#include <iostream>template< typename T >void print_tree(const tree<T>& );int main() {	tree<std::string> t;	tree<std::string>::pre_order_itr itr = t.pre_begin();	itr = t.add_child(itr, "university");			t.add_child(itr, "Eng");			t.add_child(itr, "Medicine");			tree<std::string>::iterator itr2 = t.add_child(itr, "Science");					t.add_child(itr2, "Chemistry");						t.add_child(itr2, "Physics");						tree<std::string>::pre_order_itr itr3 = t.add_child(itr2, "Biology");							t.add_child(itr3, "PE");							t.add_child(itr3, "RE");						t.add_child(itr2, "Mathematics");						t.add_child(itr2, "Computer Science");						t.add_child(itr, "Education");				t.add_child(itr, "Social Ed");			tree<std::string>::pre_order_itr itr4 = t.add_child(itr, "Humanties");												t.add_child(itr4, "Lanugages");					t.add_child(itr4, "History");	std::cout <<  "\nTree 1\n";		print_tree(t);	tree<std::string> t2 = t.subtree(itr3);	std::cout <<  "\nTree 2\n";		print_tree(t2);	std::cout << "\nswapping tree 1 & 2....\n";	t.swap(t2);	std::cout <<  "\nTree 1\n";		print_tree(t);	std::cout <<  "\nTree 2\n";		print_tree(t2);	std::cout << "is t1 != t2? " << std::boolalpha << (t != t2) << '\n';	std::cout << "\ncopying t2 to a vector of strings:\n";	std::vector<std::string> vstrings(t2.begin(), t2.end());	std::cout << "\nPrinting vector of strings...\n\n";	for(int i = 0, n = vstrings.size(); i < n; i++)		std::cout << vstrings</span> &lt;&lt; '\n';<br>	<span class="cpp-keyword">return</span> 0;<br>}<br><br><span class="cpp-keyword">template</span>&lt; <span class="cpp-keyword">typename</span> T &gt;<br><span class="cpp-keyword">void</span> print_tree(<span class="cpp-keyword">const</span> tree&lt; T &gt;& t) {<br>	<span class="cpp-keyword">for</span>(<span class="cpp-keyword">typename</span> tree&lt; T &gt;::const_iterator tree_itr = t.begin(),<br>		end = t.end();<br>		tree_itr != end;<br>		++tree_itr) {<br>			std::cout &lt;&lt; *tree_itr &lt;&lt; '\n';<br>	}<br>}<br></pre></font></td></tr></table><!–ENDSCRIPT–>

I thought i better mention something about it. There is only two iterators const_iterator & iterator types that are paramatized by traversal scheme preorder, postorder, breadth-first are provided, the usual STL typedefs are there aswell some extras to make it easy create an iterator with a particular type of traversal scheme, you can construct an iterator of one traversal scheme with another iterator of a different traversal scheme.