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

Тема в разделе "C/C++/C#", создана пользователем SuperRustam, 29 дек 2010.

  1. SuperRustam

    SuperRustam Гость

    Репутация:
    0
    Здравствуйте! Пожалуйста, помогите улучшить программу.
    Программа работает, только надо добавить 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);
    }
    //---------------------------------------------------------------------------
     
Загрузка...
Похожие Темы - Бинарное дерево С++
  1. Maestresa
    Ответов:
    2
    Просмотров:
    1.817
  2. newslayer
    Ответов:
    0
    Просмотров:
    1.158
  3. European
    Ответов:
    0
    Просмотров:
    2.107
  4. Hanja
    Ответов:
    0
    Просмотров:
    1.127
  5. MrSpoon
    Ответов:
    0
    Просмотров:
    1.108

Поделиться этой страницей