avlnode.h

本人自己的作品

#pragma once
///自由内存AVL树节点
///注：T在比较大小时，只用了小于作为基础
template<class T> class CAVLNode
{
protected:
	///节点数据
	T _data;
	///左子树高度
	long _left_hei;
	///右子树高度
	long _right_hei;
	///左子树所在的指针
	CAVLNode* _left;
	///左子树所在的指针
	CAVLNode* _right;
public:
	///构造
	CAVLNode(T data = T());
	///复制构造
	CAVLNode(const CAVLNode& node);
	///析构
	~CAVLNode(void);
	///取得左子树所在的指针
	CAVLNode* Left() const;
	///设置左子树所在的指针
	void Left(CAVLNode* left);
	///取得右子树所在的指针
	CAVLNode* Right() const;
	///设置右子树所在的指针
	void Right(CAVLNode* right);
	///设置左子树高度
	void LeftHei(long hei);
	///取得左子树高度
	long& LeftHei();
	///设置右子树高度
	void RightHei(long hei);
	///取得右子树高度
	long& RightHei();
	///平衡因子
	long balance() const;
	///树高度
	long Height() const;///高度
	///取得数据--只读
	const T& Data() const;
	///设置数据
	void Data(T data);
	///得到数据--可更改
	T& GetData();
	///数据复制
	CAVLNode<T>& operator =(const CAVLNode<T>& node);
public:
	///重载!= 与CAVLNode对象比较
	bool operator !=(const CAVLNode& node) const;
	///重载> 与CAVLNode对象比较
	bool operator > (const CAVLNode& node) const;
	///重载>= 与CAVLNode对象比较
	bool operator >=(const CAVLNode& node) const;
	///重载< 与CAVLNode对象比较
	bool operator < (const CAVLNode& node) const;
	///重载<= 与CAVLNode对象比较
	bool operator <=(const CAVLNode& node) const;
	///重载== 与CAVLNode对象比较
	bool operator ==(const CAVLNode& node) const;
	
	///重载!= 与T对象比较
	bool operator !=(const T& data) const;
	///重载> 与T对象比较
	bool operator > (const T& data) const;
	///重载>= 与T对象比较
	bool operator >=(const T& data) const;
	///重载< 与T对象比较
	bool operator < (const T& data) const;
	///重载<= 与T对象比较
	bool operator <=(const T& data) const;
	///重载== 与T对象比较
	bool operator ==(const T& data) const;
};

///构造与析构
template<class T> inline
CAVLNode<T>::CAVLNode(T data)
: _data(data)
, _left(NULL)
, _right(NULL)
, _left_hei(0)
, _right_hei(0)
{
}
template<class T> inline
CAVLNode<T>::CAVLNode(const CAVLNode<T>& node)
: _data(node._data)
, _left(node._left)
, _right(node._right)
, _left_hei(node._left_hei)
, _right_hei(node._right_hei)
{
}

template<class T> inline
CAVLNode<T>& CAVLNode<T>::operator =(const CAVLNode<T>& node)
{
	_data     = node._data;
	_left     = node._left;
	_right    = node._right;
	_left_hei = node._left_hei;
	_right_hei= node._right_hei;
	return *this;
}
template<class T> inline
CAVLNode<T>::~CAVLNode(void)
{
}

///链接
template<class T> inline
CAVLNode<T>* CAVLNode<T>::Left() const
{
	return _left;
}

template<class T> inline
void CAVLNode<T>::Left(CAVLNode<T>* left)
{
	_left = left;
}

template<class T> inline
CAVLNode<T>* CAVLNode<T>::Right() const
{
	return _right;
}

template<class T> inline
void CAVLNode<T>::Right(CAVLNode<T>* right)
{
	_right = right;
}
///高度
template<class T> inline
void CAVLNode<T>::LeftHei(long hei)
{
	_left_hei = hei;
}
template<class T> inline
long& CAVLNode<T>::LeftHei()
{
	return _left_hei;
}
template<class T> inline
void CAVLNode<T>::RightHei(long hei)
{
	_right_hei= hei;
}
template<class T> inline
long& CAVLNode<T>::RightHei()
{
	return _right_hei;
}
///平衡因子
template<class T> inline
long CAVLNode<T>::balance() const
{
	return _left_hei - _right_hei;
}
///高度
template<class T> inline
long CAVLNode<T>::Height() const
{
	return _left_hei > _right_hei ?
		_left_hei + 1 : _right_hei + 1;///还有自己的高度
}
///数据
template<class T> inline
const T& CAVLNode<T>::Data() const
{
	return _data;
}
///数据
template<class T> inline
T& CAVLNode<T>::GetData()
{
	return _data;
}

template<class T> inline
void CAVLNode<T>::Data(T data)
{
	_data = data;
}
///比较
template<class T> inline
bool CAVLNode<T>::operator !=(const CAVLNode<T>& node) const
{
	return node._data < _data || _data < node._data;
}
template<class T> inline
bool CAVLNode<T>::operator >(const CAVLNode<T>& node) const
{
	return node._data < _data;
}
template<class T> inline
bool CAVLNode<T>::operator >=(const CAVLNode<T>& node) const
{
	return !(_data < node._data);
}
template<class T> inline
bool CAVLNode<T>::operator <(const CAVLNode<T>& node) const
{
	return _data < node._data;
}

template<class T> inline
bool CAVLNode<T>::operator <=(const CAVLNode<T>& node) const
{
	return !(node._data < _data);
}
template<class T> inline
bool CAVLNode<T>::operator ==(const CAVLNode<T>& node) const
{
	return !(node._data < _data) && !(_data < node._data);
}

///比较
template<class T> inline
bool CAVLNode<T>::operator !=(const T& data) const
{
	return data < _data || _data < data;
}
template<class T> inline
bool CAVLNode<T>::operator >(const T& data) const
{
	return data < _data;
}
template<class T> inline
bool CAVLNode<T>::operator >=(const T& data) const
{
	return !(_data < data);
}
template<class T> inline
bool CAVLNode<T>::operator <(const T& data) const
{
	return _data < data;
}

template<class T> inline
bool CAVLNode<T>::operator <=(const T& data) const
{
	return !(data < _data);
}
template<class T> inline
bool CAVLNode<T>::operator ==(const T& data) const
{
	return !(data < _data) && !(_data < data);
}
///缺省的内存分配器--使用new 和delete
template<class T> 
class CAVLNodeAlloctor
{
public:
	///分配内存
	CAVLNode<T>* Alloc()
	{
		return new CAVLNode<T>;
	}
	///销毁内存
	void Free(CAVLNode<T>* t)
	{
		delete t;
	}
};