Завдання 2. Написати програму, в якій запрошується ввести кількість елементів для бінарного дерева і введення самих елементів

Написати програму, в якій запрошується ввести кількість елементів для бінарного дерева і введення самих елементів, програма будує бінарне дерево для одної ланки.

У структурі слід оголосити інформаційний елемент і покажчики на саму праву і на саму ліву частину майбутнього дерева.

Оголошуємо покажчик на нашу структуру (на ланку дерева) і уникнення непередбачених помилок відразу ініціалізіруем цей покажчик в нуль

struct node

{

int info; //Інформаційне поле

node *l, *r;//Ліва і Права частина дерева

};

node * tree=NULL;

Після опису структури-ланки бінарного дерева і оголошення на неї покажчика, в головній функції слід записати стандартні рядки (скільки елементів ввести) і виконати цикл по введенню елементів вказаних число разів. При цьому потрібно кожен новий елемент відразу записувати в дерево, з цією метою записати окрему функцію.

void push(int a,node **t)

{

if ((*t)==NULL) //якщо дерева не існує

{

(*t)=new node; //виділяємо пам’ять

(*t)->info=a; //вставляємо у виділене місце аргумент а

(*t)->l=(*t)->r=NULL; //очистимо пам'ять для наступного росту

return;

}

//дерево вже існує

if (a>(*t)->info) push(a,&(*t)->r); //якщо аргумент а більш ніж поточний елемент, ставимо його праворуч

else push(a,&(*t)->l); // інакше ліворуч

//функція відображення дерева на екрані

void print (node *t,int u)

{

if (t==NULL) return; //якщо дерево порожнє, виходимо з програми

else //інакше

{

print(t->l,++u);//за допомогою рекурсії переходимо у ліве піддерево

for (int i=0;i<u;++i)

cout<<"|";

cout<<t->info<<endl; //і демонструємо елемент

u--;

}

print(t->r,++u); //за допомогою рекурсії переходимо до правого піддерева

}

int main ()

{

int n; //кількість елементів

int s; //кількість, що передається у дерево

cout<<"vedit kol-vo element ";

cin>>n; //вводимо кількість елементів

for (int i=0;i<n;++i)

{

cout<<"bedit chislo ";

cin>>s; //зчитуємо елемент за елементом

push(s,&tree); //і кожний кладемо у дерево

}

cout<<"vashe derevo\n";

print(tree,0);

getch();

}

У наведеному коді функція приймає 2 параметра. Перший – записуване число, другий покажчик на покажчик ланки дерева.

При занесення інформації, двійкове дерево або містить інформацію, або ще не заповнювався, тому перший крок – перевірка на наявність даних в дереві.

В даному коді використаний параметр u. При виведенні на екран ви будете бачити палички, які виводяться за допомогою циклу. Знайти в коді це місце неважко. Ці палички символічно позначають кількість вузлів