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

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

  1. SuperRustam

    SuperRustam Гость

    Здравствуйте! Пожалуйста, помогите улучшить программу.
    Программа работает, только надо добавить 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.670
  2. newslayer
    Ответов:
    0
    Просмотров:
    1.114
  3. European
    Ответов:
    0
    Просмотров:
    2.069
  4. Hanja
    Ответов:
    0
    Просмотров:
    1.037
  5. MrSpoon
    Ответов:
    0
    Просмотров:
    1.056

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