avltree.h

来自「这些程序是本人学习数据结构时编的」· C头文件 代码 · 共 63 行

// AVLTree.h: interface for the AVLTree class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_AVLTREE_H__FF822652_C32B_42E7_9F53_9581E0C5F76C__INCLUDED_)
#define AFX_AVLTREE_H__FF822652_C32B_42E7_9F53_9581E0C5F76C__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000


#include <iostream>
#include <iomanip>
using namespace std;

template<class Type> class AVLTree;

template<class Type>
class AVLNode
{
friend class AVLTree;
public:
	Type data;
	AVLNode<Type> * left, *right;
	int balance;
	AVLNode<Type>(): left(NULL),right(NULL),balance(0){};
	AVLNode<Type>(Type d, AVLNode<Type> *l  = NULL,AVLNode<Type> *r = NULL):data(d),left(l),right(r),balance(0){};
};

template<class Type>
class AVLTree  
{
friend class AVLNode<Type>;
public:
	int Remove(int x);
	int Find(int x);
	int Insert (Type x);
	AVLTree() :root(NULL){};
	AVLTree(Type Ref): refvalue(Ref),root(NULL){};
	virtual ~AVLTree();
	Type RefValue();
	AVLNode<Type>* & Root(){return root;};
	int Height() const;	
	void Traverse(AVLNode<Type> *ptr,ostream & out,int i);	
	friend istream& operator >> (istream & in,AVLTree<Type> & tre);
	friend ostream& operator << (ostream & out,AVLTree<Type> & tree);
protected:
	AVLNode<Type> * root;
	Type refvalue;
	int height(AVLNode<Type> * ptr) const;
	AVLNode<Type>* find(AVLNode<Type>* current,int x);
	int Insert(AVLNode<Type> * &tre,Type x,int & taller);
	void RotateLeft(AVLNode<Type> * Tree,AVLNode<Type> * & NewTree);
	void RotateRight(AVLNode<Type> * Tree, AVLNode<Type> * & NewTree);
	void LeftBalance(AVLNode<Type>* &Tree,int & taller);
	void RightBalance(AVLNode<Type> * &Tree,int & taller);
	bool balanceTree(AVLNode<Type> * ptr ,int &x);
	AVLNode<Type>* GetPre(AVLNode<Type> * ptr);
};

#endif // !defined(AFX_AVLTREE_H__FF822652_C32B_42E7_9F53_9581E0C5F76C__INCLUDED_)