avlindex.h

avl平衡二叉树和索引树的结合体!做成了一个头文件形式.用的时候要自己写个主函数调用

//AVL树的思路:
//结点类:  需要定义一个双亲结点,以便之后的程序向上查找双亲结点的方便
//当插入一个数据的时候,按往常的插入方式放到树中,当插入的当前结点current的平衡因子为0时,则所有的树的高度都没有变化,
//当插入的当前结点的平衡因子不为0时,所有的双亲结点的平衡因子要做相应的变化
//当离插入结点最近的结点的平衡因子|m|〉1时，必须发生旋转变化使得该树继续保持平衡
//插入结点的双亲结点不为零后，则其祖先结点（向上寻找3个结点） 的平衡因子会发生改变
//注意:重新整理思路!!!!!!!
//attention:在设置孩子结点的双亲结点时，必须考虑这个双亲结点是不是为空
//Coded by HuangXiaojun
//Hunan university


#ifndef HEADER_POINTER_AVL
#define HEADER_POINTER_AVL
#include<iostream>
#include<string>
#include"stdafx.h"
using namespace std;
//定义树的结点--------------------------------
class TreeNode{
	TreeNode* parent;
	TreeNode* N_left;
	int I_element;
	TreeNode* N_right;
public:
	int balance;//平衡因子，记录的是左子树高度-右子树的高度
	TreeNode(const int temp){
		parent=N_left=N_right=NULL;
		I_element=temp;
		balance=0;
	}
	TreeNode(){
		parent=N_left=N_right=NULL;
	}
	TreeNode(TreeNode*leftval,const int temp,TreeNode*rightval){
		N_left=leftval;I_element=temp;N_right=rightval;parent=NULL;
	}
	~TreeNode(){}
	void setRightChild(TreeNode* temp){N_right=temp;}
	void setLeftChild(TreeNode* temp){N_left=temp;}
	void setparent(TreeNode* temp){parent=temp;}
	TreeNode* rightChild(){return N_right;}
	TreeNode* leftChild(){return N_left;}
	TreeNode* parentNode(){return parent;}
	void setValue(const int temp){I_element=temp;}
	int getValue(){return I_element;}
	bool IsLeaf(){
		return (N_right==NULL)&&(N_left==NULL);
	}


};
//定义二叉查找树的类
class AVL{
	TreeNode* N_root;//根结点
	int NodeCount;//该树的结点总数
	//采用中序输出-----------------------------------------------------------
	void InOrder(string Sbegin,string Send,Link* listArray,TreeNode* current,int pos,Tableheader header){
		if(current!=NULL){
			InOrder(Sbegin,Send,listArray,current->leftChild(),pos,header);//打印左子树
			int number2,i;
			string* SubString2=stringCut(listArray[current->getValue()].data,number2);
			if(Send!="#" && SubString2[pos]>=Send) return;
			Node* Fence=header.setStart();//将表头数据传出
			if(Sbegin!="#" && SubString2[pos]>=Sbegin)
			{
					for(i=0; i<number2; ++i){
						cout<<SubString2[i];
						int a=Fence->next->element.colDataLength();
						int b=SubString2[i].length();//通过以上两个整型变量计算需要输出多少个空格
						for(int j=0;j<(a-b);++j)
							cout<<' ';
						Fence=Fence->next;//下列的数据宽度
					}
				cout<<endl;
			}
			else if( SubString2[pos]>=Sbegin)
			{		
					for(i=0; i<number2; ++i){
						cout<<SubString2[i];
						int a=Fence->next->element.colDataLength();
						int b=SubString2[i].length();//通过以上两个整型变量计算需要输出多少个空格
						for(int j=0;j<(a-b);++j)
							cout<<' ';
						Fence=Fence->next;//下列的数据宽度
					}
				cout<<endl;
			}
			InOrder(Sbegin,Send,listArray,current->rightChild(),pos,header);//打印右子树
		}
	}
	//清楚以某个结点为根的树
	void clearHlp(TreeNode* current){
		if(current==NULL) return;
		clearHlp(current->leftChild());
		clearHlp(current->rightChild());
		delete current;
	}
	//插入以某个结点为根的树的结点，一旦设置了当前结点的孩子，则马上设置孩子的双亲结点
	TreeNode* insertHlp(Link*listArray,TreeNode* current,int temp,TreeNode* & insertNode,int pos)const{//current:当前要插入的树的根节点, temp:数组的下表,insertNode用于指向生成的新结点,listArray数据存储数组的首地址,pos主键的位置

		if(current==NULL){//当结点为空的时候，创建结点插入上一结点的子孩子上
			TreeNode* p=new TreeNode(temp);
			insertNode=p;
			return p;
		}
		int number1,number2;
		string* SubString1=stringCut(listArray[temp].data,number1);
		string* SubString2=stringCut(listArray[current->getValue()].data,number2);
		if(SubString1[pos]<SubString2[pos]){//当插入值小于当前结点的值时
			current->setLeftChild( insertHlp(listArray,current->leftChild(),temp,insertNode,pos) );
			if(current->leftChild()!=NULL)
				current->leftChild()->setparent(current);//设置左孩子的父亲结点
		}
		else if(SubString1[pos]>SubString2[pos]){//大于当前结点的值时
			current->setRightChild( insertHlp(listArray,current->rightChild(),temp,insertNode,pos) );
			if(current->rightChild()!=NULL)
				current->rightChild()->setparent(current);//设置右孩子的父亲结点
		}
		else{
			insertNode=NULL;
		}
		return current;//若current的孩子结点不为空，那么把孩子结点返回给insertHlp，为空的时候，创建结点插入上一结点的子孩子上

	}
	//删除该树中的最小值结点
	TreeNode* deletemin(TreeNode* current,TreeNode*& min)const{//current：当前要删除的树的根结点，min：接受删除的最小的结点
		if(current==NULL)return NULL;
		if(current->leftChild()==NULL) {//若左孩子为空，则该结点就是最小值结点，将它传出，将右孩子的结点赋予deletemin，以便后面将转给根结点current
			min=current;
			return current->rightChild();
		}
		else {
			current->setLeftChild( deletemin(current->leftChild(),min) );
			return current;
		}

	}
	//删除该树中的最大值结点
	TreeNode* deletemax(TreeNode* current,TreeNode*& max)const{//current如上，max：接受删除的最大结点
		if(current==NULL)return NULL;
		if(current->rightChild()==NULL){
			max=current;
			return current->leftChild();
		}
		else{
			current->setRightChild(deletemax( current->rightChild(),max ) );
			return current;
		}
	}
	//查找符合某种条件的数据
	bool findHlp(Link* listArray,TreeNode* current,const string k,TreeNode*&e,int pos)const{//current:如上，k：要查找的值，e：将查找到的结点赋予它
		if(current==NULL)return false;
		int number2;
		string* SubString2=stringCut(listArray[current->getValue()].data,number2);
		
		if(k>SubString2[pos])
			return findHlp(listArray,current->rightChild(),k,e,pos);
		else if(k<SubString2[pos])
			return findHlp(listArray,current->leftChild(),k,e,pos);
		else{
			e=current;
			return true;
		}
	}
	//删除某个结点,此处删除的是该结点左子树中最小的结点，然后交换两个结点的变量即可
	TreeNode* removeHlpNo(Link* listArray,TreeNode* current,int k,TreeNode*& t,int pos)const{//删除值是k的结点，并将该节点传递给t;listArray是数据存储的数组首地址，pos是主键位置
		if(current==NULL) return NULL;
		int number1,number2;
		string* SubString1=stringCut(listArray[k].data,number1);
		string* SubString2=stringCut(listArray[current->getValue()].data,number2);

		if(SubString1[pos]<SubString2[pos]){
			current->setLeftChild( removeHlpNo(listArray,current->leftChild(),k,t,pos) );
			if(current->rightChild()!=NULL)
				current->rightChild()->setparent(current);//设置右孩子的父亲结点
		}
		else if(SubString1[pos]>SubString2[pos]){
			current->setRightChild(removeHlpNo(listArray,current->rightChild(),k,t,pos) );
			if(current->rightChild()!=NULL)
				current->rightChild()->setparent(current);//设置右孩子的父亲结点
		}
		else{
			TreeNode *temp;
			t=current;
			if(current->leftChild()==NULL)
				current=current->rightChild();
			else if(current->rightChild()==NULL)
				current=current->leftChild();
			else{
				current->setRightChild(deletemin(current->rightChild(),temp) );
				int te=current->getValue();
				current->setValue(temp->getValue());
				temp->setValue(te);
				t=temp;
			}
		}
		return current;
	}

	//删除某个指定主键的数据
	TreeNode* removeHlpData(Link* listArray,TreeNode* current,string MainKeyData,TreeNode*& t,int pos)const{//删除值是k的结点，并将该节点传递给t;listArray是数据存储的数组首地址，pos是主键位置
		if(current==NULL) return NULL;
		int number2;
		string* SubString2=stringCut(listArray[current->getValue()].data,number2);

		if(MainKeyData<SubString2[pos]){
			current->setLeftChild( removeHlpData(listArray,current->leftChild(),MainKeyData,t,pos) );
			if(current->rightChild()!=NULL)
				current->rightChild()->setparent(current);//设置右孩子的父亲结点
		}
		else if(MainKeyData>SubString2[pos]){
			current->setRightChild(removeHlpData(listArray,current->rightChild(),MainKeyData,t,pos) );
			if(current->rightChild()!=NULL)
				current->rightChild()->setparent(current);//设置右孩子的父亲结点
		}
		else{
			TreeNode *temp;
			t=current;
			if(current->leftChild()==NULL)
				current=current->rightChild();
			else if(current->rightChild()==NULL)
				current=current->leftChild();
			else{
				current->setRightChild(deletemin(current->rightChild(),temp) );
				int te=current->getValue();
				current->setValue(temp->getValue());
				temp->setValue(te);
				t=temp;
			}
		}
		return current;
	}

	// 输出以某个结点为树的内容
	void printHlp(Link* listArray,TreeNode*current,int pos){
		if(current==NULL)return;
		printHlp( listArray,current->rightChild(),pos+5);
		cout<<endl;
		for(int i=0;i<pos;++i) cout<<" ";
		cout<<listArray[current->getValue()].data;
		printHlp( listArray,current->leftChild(),pos+5);
	}

	//当结点的平衡因子为-2时，进行左旋转
	void L_Balance(Link* listArray,TreeNode* & c_root,int temp,int pos){ //temp要删除的数据的位置
		//结点为2的图形为"/" 情况--------------配合PPT上的图更容易理解-------------
		if(c_root->leftChild()!=NULL && c_root->leftChild()->balance==1)
		{
			TreeNode*it=c_root->leftChild();
			c_root->setLeftChild(it->rightChild());
			it->setRightChild(c_root);
			it->setparent(c_root->parentNode());//在设置孩子和父亲结点时,一定要判断这个结点是否为空
			if(it->parentNode()!=NULL)
			{
				//将需要比较的字符串切割后，拿主键进行比较------------------------------
				int number1,number2;
			
				string* SubString1=stringCut(listArray[it->getValue()].data,number1);
				string* SubString2=stringCut(listArray[it->parentNode()->getValue()].data,number2);
				
				if(SubString1[pos]<SubString2[pos] ) it->parentNode()->setLeftChild(it);
				else it->parentNode()->setRightChild(it);
			}
			c_root->setparent(it);
			if(c_root->leftChild()!=NULL) c_root->leftChild()->setparent(c_root);
			c_root->balance=0;it->balance=0;
			c_root=it;
		}
		//结点为2的图形为折线的情况-----------------------------
		else if(c_root->leftChild()!=NULL && c_root->leftChild()->balance==-1)
		{
			TreeNode* it1=c_root->leftChild();
			TreeNode* it2=it1->rightChild();
			it1->setRightChild(it2->leftChild());
			c_root->setLeftChild(it2->rightChild());
			it2->setLeftChild(it1);
			it2->setRightChild(c_root);
			it2->setparent(c_root->parentNode());
			if(it2->parentNode()!=NULL)
			{
				//将需要比较的字符串切割后，拿主键进行比较------------------------------
				int number1,number2;
			
				string* SubString1=stringCut(listArray[it2->getValue()].data,number1);
				string* SubString2=stringCut(listArray[it2->parentNode()->getValue()].data,number2);

				if(SubString1[pos]<SubString2[pos]) it2->parentNode()->setLeftChild(it2);
				else it2->parentNode()->setRightChild(it2);