Бинарное дерево. С++

  • Автор темы SuperRustam
  • Дата начала
S

SuperRustam

#1
Здравствуйте! Пожалуйста, помогите улучшить программу.
Программа работает, только надо добавить StringGrid, куда надо выводить бинарное дерево так, чтобы оно располагалось структурировано. То есть меньший элемент левее, больший – правее, а корень находился выше и посередине. И чтобы это выглядело так в не зависимости от количества элементов. Как это представить? У меня стоит CodeGear RAD Studio 2009. Пожалуйста, напишите по шагам поподробнее, что куда вставлять и писать.



1. Техническое задание

Используя динамические структуры данных, разработать программу согласно варианту. Предусмотреть:
- защиту от неправильного ввода данных;
- ввод исходных данных с клавиатуры и из текстового файла.
Построить двоичное дерево поиска. Определить функцию нахождения всех дубликатов в списке чисел. Определить рекурсивные функции обходов дерева.

Необходимо разработать программу, которая:
Создает бинарное дерево поиска на основе элементов, вводимых пользователем с клавиатуры или считываемых из файла. Выводит дерево в порядке, выбранном пользователем – прямом, симметричном, обратном. Находит все имеющиеся дубликаты в дереве. Информационной частью в нашем дереве являются числа, ограничимся на 9 знаках. При вводе значений пользователем делаем проверку на корректность данных. Перед созданием дерева следует удалять предыдущее, если оно было создано. После построения, дерево следует выводить на экран в виде, отражающем структуру дерева и принцип построения. В программе дерево выводится по умолчанию в прямом порядке.



C++:
#include <vcl.h>
#include <iostream.h>
#pragma hdrstop
#include "Unit1.h"
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;

tree_t *root = NULL;
size_t count = 0;
int *uniq_el = NULL;

void push_search_tree(tree_t **tree, int x)
{
if (*tree)
{
if (x < (*tree)->info)
{
push_search_tree( &(*tree)->left, x);
}
else
{
push_search_tree( &(*tree)->right, x);
}
}
else
{
*tree = (tree_t *) realloc(NULL, sizeof(tree_t));
(**tree).info = x;
(**tree).left = NULL;
(**tree).right = NULL;
}
}

int find(tree_t **tree, int x)
{
if (*tree)
{
if ((*tree)->info == x)
{
return 1;
}
else
if ((*tree)->info > x)
{
if ((*tree)->left)
{
return find( &(*tree)->left, x);
}
else
{
return 0;
}
}
else
{
if ((*tree)->right)
{
return find( &(*tree)->right, x);
}
else
{
return 0;
}
}
}
else
{
return 0;
}
}


void explore_and_add_search_tree(tree_t **tree)
{
if (*tree)
{
push_search_tree( &root, (*tree)->info);
explore_and_add_search_tree(&(*tree)->left);
explore_and_add_search_tree(&(*tree)->right);
}
}


void delete_tree_find(tree_t **tree, int *ind)
{
tree_t *temp = NULL;

if (*tree)
{
if ((*tree)->left)
{
if (*ind == 1)
{
(*tree)->left = NULL;
explore_and_add_search_tree(&temp->left);
explore_and_add_search_tree(&temp->right);
*ind = -1;
}
else
{
delete_tree_find( &(*tree)->left, &(--(*ind)));
}
}

if ((*tree)->right)
{
if (*ind == 1)
{
temp = (*tree)->right;
(*tree)->right = NULL;
explore_and_add_search_tree(&temp->left);
explore_and_add_search_tree(&temp->right);
*ind = -1;
}
else
{
delete_tree_find( &(*tree)->right, &(--(*ind)));
}
}
}
}


void main_delete_search_tree(tree_t **tree, int *ind)
{
tree_t *temp;
if (*ind == 1)
{
if (root)
{
if (root->left )
{
temp = root->right;
root = root->left;
explore_and_add_search_tree(&temp);
}
else
if (root->right )
{
temp = root->right;
delete(root);
root = temp;
}
else
{
delete(root);
root = NULL;
}
}
}
else
{
delete_tree_find(&root, &(--(*ind)));
}
}


void free_tree_find( tree_t **tree)
{
if (*tree)
{
free_tree_find( &(*tree)->left);
free_tree_find( &(*tree)->right);
delete(*tree);
*tree = NULL;
}
}


int count_repeat_elements( tree_t **tree, int x, int count)
{
if (*tree)
{
if ((*tree)->info == x)
{
return count_repeat_elements( &(*tree)->right, x, count+1);
}
else
if ((*tree)->info > x)
{
if ((*tree)->left)
{
return count_repeat_elements( &(*tree)->left, x, count);
}
else
{
return count;
}
}
else
{
if ((*tree)->right)
{
return count_repeat_elements( &(*tree)->right, x, count);
}
else
{
return count;
}
}
}
else
{
return count;
}
}


void add_uniq(int x)
{
int test = 1;

if (uniq_el)
{
for (size_t i = 0; i < count; ++i)
{
if (uniq_el[i] == x)
{
test = 0;
break;
}
}
}

if (test)
{
uniq_el = (int *)realloc(uniq_el, ++count * sizeof(int));
uniq_el[count-1] = x;
}
}


void free_uniq()
{
uniq_el = (int *)realloc(uniq_el, 0);
uniq_el = NULL;
count = 0;
}


void __fastcall TForm1::pop_uniq()
{
Memo1->Lines->Clear();
Memo1->Lines->Add("Find all dublicate elements:");
int found = false;
for (size_t i = 0; i < count; ++i)
{
Memo1->Lines->Add(IntToStr(uniq_el[i]));
found = true;
}

if (!found) {
Memo1->Lines->Add("not found any element");
}

}


void __fastcall TForm1::view_search_tree(tree_t **tree, int cnt_space)
{
if (*tree)
{
char temp[30];

for (int i = 0; i < cnt_space; i++)
{
temp[i] = ' ';
}
temp[cnt_space] = '\0';

switch (RadioGroup1->ItemIndex)
{
case 0:
Memo1->Lines->Add(temp + IntToStr((*tree)->info));
view_search_tree(&(*tree)->left, cnt_space+1);
view_search_tree(&(*tree)->right, cnt_space+1);
break;
case 1:
view_search_tree(&(*tree)->left, cnt_space+1);
Memo1->Lines->Add(temp + IntToStr((*tree)->info));
view_search_tree(&(*tree)->right, cnt_space+1);
break;
case 2:
view_search_tree(&(*tree)->left, cnt_space+1);
view_search_tree(&(*tree)->right, cnt_space+1);
Memo1->Lines->Add(temp + IntToStr((*tree)->info));
break;
}
}
}
void scan(tree_t **tree)
{
if (*tree)
{
scan( &(*tree)->left);
if (find(&(*tree)->right, (*tree)->info))
{
add_uniq((*tree)->info);
}
scan( &(*tree)->right);
}
}



//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
if (OpenDialog1->Execute())
{
FILE *fh;
int temp;

fh = fopen(OpenDialog1->FileName.t_str() , "r");

if (fh)
{
free_tree_find( &root);
Memo1->Lines->Clear();
Memo1->Lines->Add("Creating a binary search tree:");

fscanf(fh, "%u", &count);
for (size_t i = 0; i < count; ++i)
{
fscanf(fh, "%d", &temp);
push_search_tree(&root, temp);
}
if (root)
{
view_search_tree(&root, 0);
}
else
{
Memo1->Lines->Add("empty search tree");
}
count = 0;
fclose(fh);
}
else
{
ShowMessage("Error open input file");
}
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
if (Edit1->Text != "")
{
char *def = Edit1->Text.t_str();
char *end;
int num = strtol((strlen(def) == 0)?"0":def, &end,10);
Edit1->Text = IntToStr(num);

if (find( &root, num))
{
ShowMessage( Edit1->Text + " was found");
}
else
{
ShowMessage( Edit1->Text + " not found");
}
}
else
{
ShowMessage("Incorrect number");
}
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button3Click(TObject *Sender)
{
if (Edit1->Text != "")
{
char *def = Edit1->Text.t_str();
char *end;
int num = strtol((strlen(def) == 0)?"0":def, &end,10);
Edit1->Text = IntToStr(num);
int number = count_repeat_elements( &root, num, 0);

if (number)
{
ShowMessage( Edit1->Text + " repeat " + IntToStr(number));
}
else
{
ShowMessage( Edit1->Text + " not found");
}
}
else
{
ShowMessage("Incorrect number");
}
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button4Click(TObject *Sender)
{
free_uniq();
scan( &root );
pop_uniq();
}
//---------------------------------------------------------------------------


void __fastcall TForm1::Button6Click(TObject *Sender)
{
if (Edit2->Text != "")
{
char *def = Edit2->Text.t_str();
char *end;
if (strlen(def)>9)
{
ShowMessage("Count digit > 9");
}
else
{
int num = strtol((strlen(def) == 0)?"0":def, &end,10);
Edit2->Text = IntToStr(num);

push_search_tree(&root, num);
Memo1->Lines->Clear();
Memo1->Lines->Add("View a binary search tree:");
view_search_tree(&root, 0);
}
}
else
{
ShowMessage("Incorrect number");
}
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button7Click(TObject *Sender)
{
if (Edit3->Text != "")
{
if (!root)
{
ShowMessage("Empty a binary search tree");
}
else
{
char *def = Edit3->Text.t_str();
char *end;
int ind = strtol((strlen(def) == 0)?"0":def, &end,10);
Edit3->Text = IntToStr(ind);

if (ind<1)
{
ShowMessage("Incorrect number");
}
else
{
main_delete_search_tree(&root, &ind);
Memo1->Lines->Clear();
Memo1->Lines->Add("View a binary search tree:");
view_search_tree(&root, 0);
}
}
}
else
{
ShowMessage("Incorrect number");
}
}
//---------------------------------------------------------------------------

void __fastcall TForm1::RadioGroup1Click(TObject *Sender)
{
Memo1->Lines->Clear();
Memo1->Lines->Add("View a binary search tree:");
view_search_tree(&root, 0);
}
//---------------------------------------------------------------------------