Задать вопрос
@Gioo12x

Как показать все листья в бинарном дереве?

Нужна помощь с бинарным деревом. Задали задание в универе условие каторае выглядит вот так:
Разработать программу, которая выводит на экран элементы из всех листьев дерева.
Какой добавить метод или изменение в коде нужна сделать чтоб программа работала с соответствует с условием.
Вот код.
spoiler
//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit4.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm4 *Form4;
//---------------------------------------------------------------------------
__fastcall TForm4::TForm4(TComponent* Owner)
	: TForm(Owner)
{
}struct Tree {
 int info;
 Tree *left, *right;
}*root; // Корень
//----------------- Декларации прототипов функций работы с деревом -------------
void Add_List(Tree*, int);
void View_Tree (Tree*, int);
Tree* Del_Info(Tree*, int);
void Del_Tree(Tree*);
Tree* List(int);
//---------------------------------------------------------------------------
void __fastcall TForm4::Button6Click(TObject *Sender)
{    if(root!=NULL){
 Del_Tree(root);
 ShowMessage(" Tree Delete!");
 }
 Close();

}
//---------------------------------------------------------------------------
void __fastcall TForm4::Button1Click(TObject *Sender)
{
 if(root != NULL) Del_Tree(root);
 root = List (StrToInt(Edit1->Text));}
//---------------------------------------------------------------------------
void __fastcall TForm4::Button3Click(TObject *Sender)
{
if( root == NULL ) ShowMessage(" Create TREE !");
 else {
 Memo1->Lines->Add("---------- View -----------");
View_Tree(root, 0);
 }
}
//---------------------------------------------------------------------------
void __fastcall TForm4::Button2Click(TObject *Sender)
{
if(root == NULL) root = List (StrToInt(Edit1->Text));
 else Add_List (root, StrToInt(Edit1->Text));
}
//---------------------------------------------------------------------------
void __fastcall TForm4::Button4Click(TObject *Sender)
{
int b = StrToInt(Form4->Edit1->Text);
 root = Del_Info(root, b);
}
//---------------------------------------------------------------------------
void __fastcall TForm4::Button5Click(TObject *Sender)
{
Del_Tree(root);
 ShowMessage(" Tree Delete!");
 root = NULL;
}
//---------------------------------------------------------------------------
 Tree* List(int inf) {
	Tree *t = new Tree;	// Захват памяти
t -> info = inf;// Формирование информационной части
t -> left = t -> right = NULL;	// Формирование 							//адресных частей
return t;		// Возврат созданного указателя
}
void Add_List(Tree *root, int key)
{	Tree *prev, *t;	// prev – указатель предка нового листа
 bool find = true;
		t = root;
		while ( t && find) {
		  	prev = t;
		  	if( key == t->info) {
                        find = false;	// Ключ должен быть уникален
                                ShowMessage("Dublucate Key!");
			}
		   	else
				if ( key < t -> info ) t = t -> left;
				else   t = t -> right;
		}
		if (find) {			// Нашли нужное место
			t = List(key);		// Создаем новый лист
			if ( key < prev -> info ) prev -> left = t;
			else    prev -> right = t;
		}
}
void View_Tree(Tree *p, int level )	{
  String str;
	if ( p )	  {
	View_Tree (p -> right , level+1);	// Правое поддерево
	   for ( int i=0; i<level; i++) str = str + "    ";
		Form4->Memo1->Lines->Add(str + IntToStr(p->info));
	View_Tree(p -> left , level+1); // Левое поддерево
	   }
	}
void Del_Tree(Tree *t) {
  	if ( t != NULL)  {
    	Del_Tree ( t -> left); // На левую ветвь
    	Del_Tree ( t -> right); // На правую ветвь
      	delete t;
   	}
}


Tree* Del_Info(Tree *root, int key)  {
	Tree *Del, *Prev_Del, *R, *Prev_R;
// Del,Prev_Del – удаляемый узел и его предыдущий (предок);
// R,Prev_R – элемент, на который заменяется удаленный, и его предок;

     	Del = root;
	Prev_Del = NULL;
 while  (Del != NULL && Del -> info != key) {
		Prev_Del = Del;
		if (Del->info > key)  Del = Del->left;
			else Del = Del->right;
		}
	if (Del == NULL)	{		// Элемент не найден
	ShowMessage ( "NOT Key!");
			return root;
	}
 if (Del -> right == NULL) R = Del->left;
	else
		if (Del -> left == NULL) R = Del->right;
		else { //---------------- Ищем самый правый узел в левом поддереве
			Prev_R = Del;
			R = Del->left;
			while (R->right != NULL) {
				Prev_R = R;
				R = R->right; }
		 //----------- Нашли элемент для замены R и его предка Prev_R
			if( Prev_R == Del)  R->right = Del->right;
			else {
				R->right = Del->right;
				Prev_R->right = R->left;
				R->left = Prev_R; }
			 }
	if (Del== root) root = R;		// Удаляя корень, заменяем его на R
	else //------- Поддерево R присоединяем к предку удаляемого узла -----------
	if (Del->info < Prev_Del->info)
			Prev_Del->left = R;	// На левую ветвь
		else	Prev_Del->right = R;	// На правую ветвь
	delete Del;
	return root; }
  • Вопрос задан
  • 182 просмотра
Подписаться 1 Простой 1 комментарий
Пригласить эксперта
Ответы на вопрос 1
@res2001
Developer, ex-admin
Листьями в дереве считаются узлы, у которых нет потомков.
Потомки в коде задаются членами узла left и right, соответственно if(p->left == NULL && p->right == NULL), то узел - лист.
Делаете проход по всем узлам и выводите только те узлы, где условие выполняется.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы