Developing.ru

Код: Выделить всё

#include "stdafx.h"
#include"conio.h"
#include<stdlib.h>
#include <stdio.h>
#include<fstream>
#include <iostream>
using namespace std;

Tree:: ~Tree()
{
	root=DelR(root);
}

Tree Tree: :o perator =(Tree &tr)
{
	if(this==&tr)
		return *this;
	DelR(root);
	root=TreeCopyNodeR(tr.root);
	find=tr.find;
	find->pred=tr.find->pred;
	return *this;
}
Node* Tree::TreeCopyNodeR(Node *n)
{
	if(n==NULL)
		return NULL;
	Node* node=new Node(n->key);
	node->left=TreeCopyNodeR(n->left);
	node->right=TreeCopyNodeR(n->right);
	return node;
}
Tree::Tree(Tree &t)
{
	root=TreeCopyNodeR(t.root);
	find=t.find;
	find->pred=t.find->pred;
}

Node *Tree: :D elR(Node *p)
{
	if(p==NULL)return p; 
	p->left=DelR(p->left);
	p->right=DelR(p->right);
	delete p;
	return NULL;
}

bool Tree::Find(int k)
{
	find=poisk(k);
	if (find) return 1;
	else return 0;
}
void Tree::AddNode (int x)
{ 
	if (root!=NULL)
		AddR(root,x);
	else
	{
		root=new Node (x);
		AddR(root,x);
	}

}
Node *Tree::AddR(Node*p,int k)
{
	if(p==NULL)
	{
		p=new Node(k);
		return p;
	}
	if(p->key==k)return p;
	if(k<p->key)
		p->left=AddR(p->left,k);
	else p->right=AddR(p->right,k);
	return p;
}
Node* Tree:: poisk (int k) 
{

	Node *x=root;
	Node*pr=NULL;
	int y;
	while(x!=NULL)
	{
		y=x->key;
		if(y==k)
		{
			x->pred=pr;
			return x;
		}
		if(y>k)
		{
			pr=x;
			x=x->left;
		}

		if(y<k)
		{
			pr=x;
			x=x->right;
		}
	}
	return NULL;
}
void Tree: :D el (int x)
{
	Node *p=poisk (x);
	if (p==find)find=NULL;
	if(p==NULL){return;} 
	else
	if ((p->right==NULL)&&(p->left==NULL)) 
	{
		if (p==root) 
		{
			delete p;
			root=NULL;
			return;
		 }
		if (p->pred->left==p) p->pred->left=NULL;
		else p->pred->right=NULL;
		delete p;
		return;
	}
	if (p->right==NULL) {    
		if (p==root) {
			root=p->left;
			delete p;
			return;
		}
		if (p->pred->left==p)
			p->pred->left=p->left;
		   else p->pred->right=p->left;
		p->left->pred=p->pred;
		delete p;
		return;
	}
	if (p->left==NULL) {    
		if (p==root) {
			root=p->right;
			delete p;
			return;
		}
		if (p->pred->left==p)
			p->pred->left=p->right;
		else p->pred->right=p->right;
		p->right->pred=p->pred;
		delete p;
		return;
	}
	
	Node* p1=p->right,q;
	p1->pred=p;
	while (p1->left!=NULL)
	{
		p1->left->pred=p1;
		p1=p1->left;
	}
	if (p==root) 
	{
		if (p1->pred!=p) 
		{
			if (p1->right!=NULL) 
			{
			p1->right->pred=p1->pred;
			p1->pred->left=p1->right;
			} 
			else 
			p1->pred->left=NULL;
			p1->right=p->right;
			p->right->pred=p1;
		}
		p1->left=p->left;
		p->left->pred=p1;
		root=p1;
		delete p;	
	} 
	else 
	{
	if (p->pred->left==p) 
	{
		if (p1->pred!=p) 
		{
			if (p1->right!=NULL) 
			{
			p1->right->pred=p1->pred;
			p1->pred->left=p1->right;
			} 
			else p1->pred->left=NULL;
			p1->right=p->right;
			p->right->pred=p1;
		}
		p->pred->left=p1;
		p1->pred=p->pred;
		p1->left=p->left;
		p->left->pred=p1;
		delete p;
	}
	else 	
	{
		if (p1->pred!=p) 
		{
			if (p1->right!=NULL) 
			{
			p1->right->pred=p1->pred;
			p1->pred->left=p1->right;
			} 
			else p1->pred->left=NULL;
			p1->right=p->right;
			p->right->pred=p1;
		}
		p->pred->right=p1;
		p1->pred=p->pred;
		p1->left=p->left;
		p->left->pred=p1;
		delete p;
	}
	}
}