#include "stdafx.h" #include<iostream> using namespace std ; struct node { int data ; int h; node *leftchild; node *current; node *rightchild; }; int h(struct node* x) { if (x == NULL) return 0; return x->h; } int balanceavl(struct node *n) { if (n == NULL) return 0; return (h(n->leftchild) , h(n->rightchild)); } node* ll(struct node *b) { struct node *a = b->leftchild; struct node *c = a->rightchild; a->rightchild = b; b->leftchild = c; b->h = max(h(b->leftchild), h(b->rightchild))+1; a->h = max(h(a->leftchild), h(a->rightchild))+1; return a; } node* rr(struct node*a) { struct node *b = a->rightchild; struct node *c = b->leftchild; a->rightchild = c->leftchild; b->leftchild = c->rightchild; c->rightchild = b; c->leftchild = a; a->h = max ( h(a->leftchild) , h(a->rightchild) ) + 1 ; b->h = max ( h(b->leftchild) , h(b->rightchild) ) + 1 ; c->h= max ( h(a) , h(b) ) + 1 ; return c; } node* insert( struct node *current,int data) { if( current==NULL ) { node* x = new node ; x->data = data; x->leftchild = NULL; x->rightchild = NULL; x->h = 1; return(x); } else if( data < current->data ) { current->leftchild = insert(current->leftchild,data ); } else current->rightchild =insert (current->rightchild,data); current->h =max(h(current ->leftchild), h(current->rightchild)) + 1; int b = balanceavl(current); //ll if (b > 1 && data < current->leftchild->data) return ll(current); //rr if (b < -1 && data > current->rightchild->data) return rr(current); //lr if (b > 1 && data> current->leftchild->data) { current->leftchild = rr(current->leftchild); return ll(current); } //rl if (b < -1 && data < current->rightchild->data) { current->rightchild = ll(current->rightchild); return rr(current); } return current; } /////////////////////////////////////////////////////// void preorder(struct node *current) { if(current != NULL) { cout<<current->data; preorder(current->leftchild); preorder(current->rightchild); } } ////////////////////////////////////// void inorder(struct node *current) { if(current !=NULL) { inorder(current->leftchild); cout<<current->data; inorder(current->rightchild); } } node* Remove(struct node* current , int data) { if (current== NULL) return current ; if (data< current->data) current->leftchild = Remove(current->leftchild, data); else if(data > current->data ) current->rightchild = Remove(current->rightchild, data); else { if( (current->leftchild == NULL) || (current->rightchild == NULL) ) { struct node *temp = current->leftchild ? current->leftchild :current->rightchild; if(temp == NULL) { temp = current; current = NULL; } else { *current = *temp; } free(temp); } else { struct node* root = current->rightchild; while (root->leftchild != NULL) root = root->leftchild; struct node* temp = root; current->data= root->data; current->rightchild = Remove(current->rightchild, root->data); } } if (current == NULL) return current; current->h = max(h(current->leftchild), h(current->rightchild)) + 1; int b = balanceavl(current); //ll if (b > 1 && balanceavl(current->leftchild) >= 0) return ll(current); //lr if (b > 1 && balanceavl(current->leftchild) < 0) { current->leftchild = rr(current->leftchild); return ll(current); } //rr if (b < -1 && balanceavl(current->rightchild) <= 0) return rr(current); //rl if (b < -1 && balanceavl(current->rightchild) > 0) { current->rightchild = ll(current->rightchild); return rr(current); } return current; } int main() { struct node *current= NULL; int k,m; do{ cout<<"if u want add item in avl tree plz enter 1\nif u want remove item from avl tree plz enter 2\nif u want show item plz enter 3\nif u want exit enter 0\n"; cin >>k; switch(k) { case 1: { cout<<"enter your item:"; cin>>m; current =insert(current, m); cout<<endl; break; } case 2: { cout<<"enter your item:"; cin>>m; remove(current,m); inorder(current); cout<<endl; break; } case 3: { cout<<"preorder: "; preorder(current); cout<<"\t"<<"inorder: "; inorder(current); cout<<endl; break; } default: cout<<" no item :( "; } }while(k!= 0); return 0; }
int remove(const char *path)
var
This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)