AVLツリー構築コード(C++)

AVLツリーの構造と遍歴
基本的なAVLツリー構造の問題ですが、バランスをとるかどうか、どのようにバランスをとるかをどのように判断するかに注目しましょう.ここではflagで表記しますが、2または-2と表記されたノードはバランスが必要で、flagは左右のサブツリーの高さ差です.あるpノードp->flag=2、すなわち左サブツリーの高さが右サブツリー2より高く、p->lchild->flag値が1であると判断するとLL(p->childの左サブツリーも1高いため)、−1がLR(p->lchildの右サブツリーの高さ1)となる.回転するときはpノードがルートノードであるかどうかに注意する必要があります.そうであれば、回転後のノードをルートノードにし、updataの場合、つまり二叉木のバランスが取れているかどうかを再チェックするときは、新しいルートノードからチェックする必要があります.ルートノードでない場合、pの代わりに新しいノードはpの親ノードにリンクされます.私は最初はfatherポインタを設定していなかったのでrootタグビット判根を使っていましたが、回転後の親子のノードのリンクには父のノードが必要であることに気づきましたが、コードを変更するのがおっくうで残っていました.具体的には私のコードを参照してください.ここで重視しなければならないのは,ノード移動中に各ノードのリンクが複雑で,うっかり間違えないようにすることである.

は少し言って、私は自分で作って、結点の移動のコードを書きたいと思って、結局ふだん多く練習して利益があります.実は回転するノードのdata値を直接修正すればいいので、親ノードもルートを判断する必要がなく、便利になります.

AVLは大きい2生が比较的に复雑な1枚だと感じて、私はネット上のコードを见てjavaが多いと感じて、それからコードは比较的に简単で、新入生用に适していないので、1版の比较的に详しいことを书きました.必要な学生がいたら、伝言を残して私に相談してください.

#include
#include
#include
#include 
#include
#include
#include 
#include
#include 
#include 
#include
using namespace std;
#define rep(i, a, b) for(int i=(a); i
#define req(i, a, b) for(int i=(a); i<=(b); i++)
#define ull unsigned __int64
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d
",(t))
#define pf printf
#define prk printf("
")
#define pi acos(-1.0)
#define ms(a,b) memset((a),(b),sizeof((a)))
#define mc(a,b) memcpy((a),(b),sizeof((a)))
#define w while
#define vr vector
#define gr greater
typedef long long ll;
//next_permutation(arr, arr+size);   
//prev_permutation(arr, arr+size);

struct AVL{
	AVL *lchild;
	AVL *rchild;
	AVL *father;
	int flag;
	int data;
	int root;
}; 
AVL *t = NULL, *p = NULL;
int hh, flag;

void insert(AVL *s, int x)
{
	
	if(x > s->data)
	{
		if(s->rchild != NULL)
		insert(s->rchild, x);
		else
		{
			AVL *c;
			c = new AVL; //new   ，         
			c->data = x;
			c->lchild = c->rchild = NULL;
			c->flag = 0;
			c->root = 0;
			s->rchild = c;
			c->father = s;
		}
	}	
	else
	{
		if(s->lchild != NULL)
		insert(s->lchild, x);
		else
		{
			AVL *c;
			c = new AVL;
			c->data = x;
			c->lchild = c->rchild = NULL;
			c->flag = 0;
			s->lchild = c;
			c->father = s;
		}
	}
}

void gethigh(AVL *s, int h) //       
{
	if(s->lchild != NULL)
	{
		hh = max(hh, h+1);
		gethigh(s->lchild, h+1);
	} 
	if(s->rchild != NULL)
	{
		hh = max(hh, h+1);
		gethigh(s->rchild, h+1);
	}
	//cout << "insert" << endl;
}


void updata(AVL *s)
{
	hh = 1;
	if(s->lchild != NULL)
	{
		hh = 2;
		gethigh(s->lchild, 2); //    ，       ，       2 
		cout << "s->data = "<<s->data<<"   : the lchild is not NULL, and is " << s->lchild->data << endl;
	}
	
	int hl = hh;
	hh = 1;
	if(s->rchild != NULL)
	{
		hh = 2;
		gethigh(s->rchild, 2);
		cout << "s->data = " <<s->data<< "   : the rchild is not NULL, and is " << s->rchild->data << endl;
	}
	
	int hr = hh;
	s->flag = hl - hr;//        ，     ，flag      ，   2       
	if(s->flag == 2 || s->flag == -2)
	{
		p = s;
		cout << "p is " << p->data << "  && p->flag = " << p->flag << endl;
		flag = 1;	
	}
	//prk;
	if(s->lchild != NULL)
	updata(s->lchild);
	if(s->rchild != NULL)
	updata(s->rchild);
	
}

void change(AVL *s)
{
	cout << "p is " << p->data << "  && p->flag = " << p->flag << endl;
	//     ，               、      ，         
	if(p->flag == 2)
	{
		if(p->lchild->flag == 1) //LL 
		{
			AVL *r = p->lchild;
			if(r->rchild != NULL)
			p->lchild = r->rchild;
			else p->lchild = NULL;
			r->rchild = p;
			p->father = p->father;
			p->father = r;
			if(p->root == 1)
			{
				r->root = 1;
				p->root = 0;
				t = r;
			}
			else
			{
				AVL *c = r->father;
				if(c->lchild->data == p->data)
				c->lchild = r;
				else c->rchild = r;
			}
		}
		else //LR 
		{
			AVL *r = p->lchild;
			AVL *rr = r->rchild;
			if(rr->lchild != NULL)
			r->rchild = rr->lchild;
			else r->lchild = NULL;
			rr->lchild = r;
			r->father = rr;
			if(rr->rchild != NULL)
			p->lchild = rr->rchild;
			else p->lchild = NULL;
			rr->rchild = p;
			rr->father = p->father;
			p->father = r;
			if(p->root == 1)
			{
				rr->root = 1;
				p->root = 0;
				t = rr;
			}
			else
			{
				AVL *c = rr->father;
				if(c->lchild->data == p->data)
				c->lchild = rr;
				else c->rchild = rr;
			}
		}
	}
	else
	{
		if(p->rchild->flag == -1) //RR 
		{
			AVL *r = p->rchild;
			if(r->lchild != NULL)
			p->rchild = r->lchild;
			else p->rchild = NULL;
			r->lchild = p;
			r->father = p->father;
			p->father = r;
			if(p->root == 1)
			{
				r->root = 1;
				p->root = 0;
				t = r;
			}
			else
			{
				AVL *c = r->father;
				if(c->lchild->data == p->data)
				c->lchild = r;
				else c->rchild = r;
			}
		}
		else //RL 
		{
			AVL *r = p->rchild;
			AVL *rr = r->lchild;
			if(rr->rchild != NULL)
			r->lchild = rr->rchild;
			else r->lchild = NULL;
			rr->rchild = r;
			r->father = rr;
			if(rr->lchild != NULL)
			p->rchild = rr->lchild;
			else p->rchild = NULL;
			rr->lchild = p;
			rr->father = p->father;
			p->father = rr;
			if(p->root == 1)
			{
				rr->root = 1;
				p->root = 0;
				t = rr;
			}
			else
			{
				AVL *c = rr->father;
				if(c->lchild->data == p->data)
				c->lchild = rr;
				else c->rchild = rr;
			}
		}
	}
	flag = 0;
	updata(t);
	if(flag)
	change(p);
}

void pre(AVL *s)
{
	cout << s->data << " ";
	if(s->lchild != NULL)
	pre(s->lchild);
	if(s->rchild != NULL)
	pre(s->rchild);
}

void ord(AVL *s)
{
	
	if(s->lchild != NULL)
	ord(s->lchild);
	cout << s->data << " ";
	if(s->rchild != NULL)
	ord(s->rchild);
}

void bac(AVL *s) 
{
	if(s->lchild != NULL)
	ord(s->lchild);
	if(s->rchild != NULL)
	ord(s->rchild);
	cout << s->data << " ";
}

int main()
{
	int x;
	sc(x);
	t = new AVL;
	p = new AVL;
	t->data = x;
	t->lchild = NULL;
	t->rchild = NULL;
	t->flag = 0;
	t->root = 1;
	t->father = NULL;
	w(sc(x) && x!=-1)
	{
		insert(t, x); //     
		flag = 0;
		updata(t); //       
		if(flag)
		{
			cout << endl << "*************" <<endl;
			change(p); //      AVL 
		}
		
	}
	pre(t); //     
	prk; 
	ord(t); //     
	prk;
	bac(t); //     
	prk;
	return 0;
}