Типове завдання

Створити дерево, в якому ключи не повторюються

 

#include<conio.h>

#include<stdlib.h>

#include<iostream.h>

class treeNode{

public:

int key; //ключ

int info; //информационное поле

treeNode *LLink, *RLink; //указатель на левый и правый узел

treeNode(){key=0;LLink=RLink=NULL;} //конструктор по умолчанию

treeNode(int k, int info_c){key=k;info=info_c;LLink=RLink=NULL;} //конструктор с параметр

~treeNode(){ //Деструктор

if(RLink!=NULL)delete RLink; //удалить левый и правый узел

if(LLink!=NULL)delete LLink;

}

//функция добавления элемента в дерево. Возвращает указатель на новый корень

void insert(int number, int info, treeNode *ptr);

treeNode* find(treeNode *ppp,int kkk); //поиск узла по заданному ключу

};

treeNode*

treeNode::find(treeNode *ppp,int kkk) //реализация поиска узла по заданному ключу

{

while((ppp!=NULL)&&(ppp->key!=kkk)){

if(ppp->key<kkk){

cout<<"Найден элемент "<<ppp->key<<" Перейти вправо."<<endl;

ppp=ppp->RLink;

}

else {

cout<<"Найден элемент "<<ppp->key<<" Перейти вправо."<<endl;

ppp=ppp->LLink;

}

}

return ppp;

}

void treeNode::insert(int n, int inf, treeNode *ptr){

cout<<"----------------"<<endl;

cout<<"Добавляем элемент ("<<n<<";"<<inf<<")n";

int flag=1;

treeNode *p, *q;

p=ptr;

while(flag){

if(n < p->key){

q=p->LLink; //a3

cout<<"Найден узел "<<p->key<<endl<<"Переход влево на элемент ";

if(q==NULL)cout<<"NULL"<<endl;else cout<<q->key<<endl;

if(q==NULL){

flag=0;

cout<<"Создается новый элемент ("<<n<<","<<inf<<")"<<endl;

q=new treeNode(n,inf);

cout<<"Обновление связей: "<<p->key<<"->LLink = "<<q->key<<endl;

p->LLink=q;

}else p=q;

}else if(n > p->key){

q=p->RLink; //a4

cout<<"Найден узел "<<p->key<<endl<<"Переход вправо на элемент";

if(q==NULL)cout<<"NULL"<<endl;else cout<<q->key<<endl;

if(q==NULL){

flag=0;

cout<<"Создается новый элемент ("<<n<<","<<inf<<")"<<endl;

q=new treeNode(n,inf);

cout<<"Обновление связей: "<<p->key<<"->RLink = "<<q->key<<endl;

p->RLink=q;

}else p=q;

}else if(n == p->key){

cout<<"Такой элемент уже существует"<<endl;

flag=0;//выход из цикла WHILE

}

}

getch();

}

void main() //главная программа

{

clrscr();

randomize();

int k_elem;

char rand_elem;

treeNode *root=new treeNode; //указатель на начало дерева

cout<<endl<<"Сколько элементов добавлять?";

cin>>k_elem;

cout<<endl<<"Генерировать случайные элементы? (y/n) ";

cin>>rand_elem;

int num,inf;

for(int tr_i=0;tr_i<k_elem;tr_i++){

if(rand_elem=='n'){

//вводить с клавиатуры

cout<<endl<<"Индекс: ";

cin>>num;

cout<<"Значение: ";

cin>>inf;

}else{

//случайные значения

num=random(100)+1;

inf=random(100)+1;

}

root->insert(num,inf,root);

}

//--- очистка памяти при выходе ---//

if(root!=NULL) delete root; //clear memory - binary trees

}