Формирование дерева поиска

Пример 1. Формируется и выводится на экран дерево поиска. Указываются уровни узлов.

#include <iostream.h>

#include <stdlib.h>

struct Point {//описание структуры бинарного дерева

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

Point* left; //указатель на левое поддерево

Point* right; //указатель на правое поддерево

};

Point* Add(Point*root,int d); //построение дерева поиска

void Out(Point* p,int n); //печать дерева

void main() {

int k;

cout<<"k= ";

cin>>k;

Point* p=new Point;

p->number=k;

p->left=0;

p->right=0;

do {

cout<<"k= ";

cin>>k;

Add(p,k);

}

while(k!=0);

Out(p,0);

}

Point* Add(Point*root,int d) {

//добавление элемента d в дерево поиска

Point*p=root;//корень дерева

Point*r;

//флаг для проверки существования элемента d в дереве

int ok=0;

while(p&&!ok){

r=p;

if(d==p->number)ok=1;//элемент уже существует

else

if(d<p->number)p=p->left;//пойти в левое поддерево

else p=p->right;//пойти в правое поддерево

}

if(ok) return p;//найдено, не добавляем

//создаем узел

Point* New_point=new Point();//выделили память

New_point->number=d;

New_point->left=0;

New_point->right=0;

//если d<r->key, то добавляем его в левое поддерево

if(d<r->number)r->left=New_point;

//если d>r->key, то добавляем его в правое поддерево

else r->right =New_point;

return New_point;

}

void Out(Point* p, int n) {//Печать бинарного дерева

//*p - указатель на корень дерева.

cout <<"\nУровень "<<n<<": ";

cout<<p->number<<' ';

n++;

if(p->left!=NULL) Out(p->left,n);

if(p->right!=NULL) Out(p->right,n);

}

Пример 2. Формируется и выводится на экран идеально сбалансированное дерево.

#include <iostream.h>

#include <stdlib.h>

struct Point {//описание структуры бинарного дерева

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

Point* left; //указатель на левое поддерево

Point* right; //указатель на правое поддерево

};

Point* Tree(int n, Point* p);

//построение идеально сбалансированного дерева

void Out(Point* p,int n); //печать дерева

void main(){

int k;

cout<<"Число узлов дерева: k= ";

cin>>k;

Point* p=new Point;

delete p;

p->left=0;

p->right=0;

Tree(k, p);

Out(p,0);

}

//построение идеально сбалансированного дерева

Point* Tree(int n,Point* p) {

Point*r;

int nl,nr;

if(n==0){

p=NULL;

return p;

}

nl=n/2;

nr=n-nl-1;

r=new Point;

cout<<"?";

cin>>r->number;

r->left=Tree(nl,r->left);

r->right=Tree(nr,r->right);

p=r;

return p;

}

//печать бинарного дерева

void Out(Point* p, int n) {

// *p - указатель на корень дерева

cout <<"\nУровень "<<n<<": ";

cout<<p->number<<' ';

n++;

if(p->left!=NULL) Out(p->left,n);

if(p->right!=NULL) Out(p->right,n);

}

Перед компиляцией кода в среде MSVC++ необходимо в меню Options/Project отключить режим Use Microsoft Foundation Classes.

Задания

1.Наберите код программы из Примера 1. Выполните компиляцию и запуск программы.

2.Найдите количество четных элементов дерева поиска. Укажите эти элементы и их уровни.

Домашние задания

1.Наберите код программы из Примера 2. Выполните компиляцию и запуск программы.

2.Найдите сумму элементов идеально сбалансированного дерева, находящихся на уровне k.