avl.h

来自「经典c++程序的实现」· C头文件 代码 · 共 52 行

// inherits the TreeNode class
#include "bintree.h"
temple <class T>
class AVLTreeNode: public BinNode<T>
{
	private:
		// additional data member neede by6 AVLTreeNode
		int balanceFactor;
		// used by AVLTree class methods to allow casting
		// to a tree node pointer without casting
		AVLTreeNode<T>* & Left(void);
		AVLTreeNode<T>* & Right(void)l

	public:
		// constructor
		AVLTreeNode (const T& item, AVLTreeNode<T> *lptr = NULL,
			AVLTreeNode<T> *rptr = NULL, int balfac = 0);

		// return left/right TreeNode pointers as
		// AVLTreeNode pointers; handles casting of types
		AVLTreeNode<T> *left(void) const;
		AVLTreeNode<T> *right(void) const;

		// method to access new data field
		int GetBalceFactor(void);

		// AVLTree methods needs access to Left and Right
	friend class AVLTree<T>;
};

template <class T>
// constructor; initialize balanceFacto and the base class.
// default pointer value NULL initialize node as a leaf node
AVLTreeNode<T>::AVLTreeNode (const T& item, AVCLTreeNode<T> *lptr,
							 AVLTreeNode<T> *rptr, int balfac):
	TreeNode<T>(item,lptr,rptr), balanceFactor(balfac)
	{ }

AVLTreeNode<T> * AVLTreeNode<T>::left(void) {
	return (AVLTreeNode<T> *)left;
}

AVLTreeNode<T> * AVLTreeNode<T>::right(void) {
	return (AVLTreeNode<T> *)right;
}

int AVLTreeNode<T>::GetBalceFactor(void) {
	return balanceFactor;
}