Бинарное дерево.Метод решения

1.  Условие задачи

В заданном бинарном дереве подсчитать число его листьев и напечатать их значения при прямом обходе дерева.

2.  Анализ задачи

Дано: Бинарное дерево

Результат:  Число листьев бинарного дерева и их значения

Метод решения:

Для решения данной задачи понадобились следующие функции:

1.Создать стек (текущему указателю присваивает значение NULL)

2.Добавить элемент в стек (создает новое звено, присваивает ему значение нового элемента и возвращает указатель на новое звено )

3.Взять элемент из стека (если стек не пуст параметр а получает значение 1, х – значене информационного поля текущего звена и функция возвращает указатель на следующее звено, иначе параметр а получает значение 0 и функция возвращает указатель со значением NULL)

4.Ввод дерева (рекурсивная функция, которая создаёт иерархический список и возвращает указатель на корень дерева )

5.Прямой обход дерева (создаёт стек, пока текущий указатель не NULL: если указатели на левое  и  правое поддерево не нулевые помещаем указатель на правое поддерево в стек и  движемся по левой ветви, иначе если указатели на левое  и  правое поддерево нулевые (зн., перед нами лист) увеличивает число листьев, печатает значение текущего указателя, если стек не пуст берём элемент из стека, иначе тек. указатель получает значение NULL, иначе если указатель на левое поддерево не нулевой, то тек. указатель получает значение указателя на левое поддерево, иначе – правое поддерево )

3.  Структура основных входных и выходных данных

Данные задачи хранятся в двоичном динамическом дереве, представленном иерархическим  списком, корень дерева– первый элемент списка.

Каждый элемент списка состоит из трёх полей: два ссылочных поля, содержащие указатели на его левое  ( L ) и правое ( R ) поддеревья, и информационное  поле ( E ):

                                                     

4.Программа

#include <stdio.h>

#include <conio.h>

#include "a:\NONAME03.cpp"

//----------------------------- Функции работы со стеком ------------------------------------------------struct btree {char   elem; btree  *left, *right;};

struct stek {btree *top; stek *next;};

stek *sozdanie(stek *r)

{ r=NULL;

return r;

}

stek *dobavlenie (stek  *st,btree *el)

{ stek *a;

a = new stek;

a->top=el;

a->next=st;

return a;

}

//vziat element

stek *func (stek *st,btree **el,int *a)

{   if(st!=NULL)

{*a=1;stek *r; r=st; *el=st->top;st=st->next; delete r; return st;

}else{ *a=0;return NULL;}

}

//------------------------------------------------------------------------------------------------------------------btree *build_tree (FILE *m)

{char sym;

btree *d;

fscanf(m," %c",&sym);

switch(sym)

{

case '(': {

d=new btree;

fscanf(m," %c",&sym);d->elem=sym;

d->left=build_tree(m);

d->right=build_tree(m);fscanf(m," %c",&sym);

return d;

}

case '0': return NULL;

case ',': d=build_tree(m);break;}

}

int obсhod (btree *d)

{

stek *S;

sozdanie(S);

int a=1,i=0;

while ( d != NULL)

{

if ( d->left != NULL && d->right != NULL)

{S=dobavlenie(S,d->right) ; d = d->left;}

else  if ( d->left == NULL && d->right == NULL)

{printf("%c ",d->elem);

i=i+1;

if(a) S=func (S,&d,&a);

else d = NULL;}

else  if (d->left != NULL) d = d->left;

else d = d->right;

}

return i;

}

void main()

{

clrscr();

btree *d;

int i;

FILE *f;

if((f=fopen("a:\\text2.txt","r"))==NULL)printf("Cannot open.");

else{

d=build_tree (f);

i=obсhod (d);

printf ("%i",i);

fclose (f);

getch (); }

}

5.Набортестов

№	Входные данные	Результат
1	(d,(r,(w,(t,0,0),(y,0,0)),(e,(u,0,0),(i,0,0))),(q,0,0))	t y u i q 5
2	(g,0,0)	g 1