Код программы#pragma once #include"stdafx.h" #include<stdio.h> #include<stdlib.h> #include<iostream> #include<fstream> #include<string> #include<string.h> #include<iomanip> // для функции setw() #include<windows.h> int oip=0;
struct tree { int name; // число tree *left; // указатель на левую ветку дерева tree *right; // указатель на правую ветку дерева };
// (Создание первого элемента бинарного дерева) tree *first (int name) { tree *pv = new tree; pv->left = 0; pv->right = 0; pv->name = name; return pv; }
int name; bool flag = false; tree *root = 0;
//void readfile(tree **root); tree *first (int name); void add(tree *root, int n); tree *descent(tree *p); tree *del(tree *root, int name); tree *delder(tree *root);
namespace U5 {
using namespace System; using namespace System::ComponentModel; using namespace System::Collections; using namespace System::Windows::Forms; using namespace System::Data; using namespace System::Drawing;
/// <summary> /// Сводка для Form1 /// </summary> public ref class Form1: public System::Windows::Forms::Form { public: Form1(void) { InitializeComponent(); // //TODO: добавьте код конструктора // }
protected: /// <summary> /// Освободить все используемые ресурсы. /// </summary> ~Form1() { if (components) { delete components; } } private: System::Windows::Forms::Button^ button1; protected: private: System::Windows::Forms::ComboBox^ comboBox1; private: System::Windows::Forms::ListBox^ listBox1; private: System::Windows::Forms::TextBox^ textBox1; private: System::Windows::Forms::Label^ label1; private: System::Windows::Forms::Label^ label2;
private: /// <summary> /// Требуется переменная конструктора. /// </summary> System::ComponentModel::Container ^components;
#pragma region Windows Form Designer generated code /// <summary> /// Обязательный метод для поддержки конструктора - не изменяйте /// содержимое данного метода при помощи редактора кода. /// </summary> void InitializeComponent(void) { this->button1 = (gcnew System::Windows::Forms::Button()); this->comboBox1 = (gcnew System::Windows::Forms::ComboBox()); this->listBox1 = (gcnew System::Windows::Forms::ListBox()); this->textBox1 = (gcnew System::Windows::Forms::TextBox()); this->label1 = (gcnew System::Windows::Forms::Label()); this->label2 = (gcnew System::Windows::Forms::Label()); this->SuspendLayout(); // // button1 // this->button1->Location = System::Drawing::Point(18, 169); this->button1->Name = L"button1"; this->button1->Size = System::Drawing::Size(242, 152); this->button1->TabIndex = 0; this->button1->Text = L"Решить!"; this->button1->UseVisualStyleBackColor = true; this->button1->Click += gcnew System::EventHandler(this, &Form1::button1_Click); // // comboBox1 // this->comboBox1->FormattingEnabled = true; this->comboBox1->Items->AddRange(gcnew cli::array< System::Object^ >(10) {L"0.Считать из текстового файла", L"1.Добавить число", L"2.Найти число", L"3.Найти дубликаты", L"4.Прямой обход", L"5.Обратный обход", L"6.Симметричный обход", L"7.Удалить число", L"8.Удалить дерево",L"9.Найти число листьев"}); this->comboBox1->Location = System::Drawing::Point(18, 62); this->comboBox1->Name = L"comboBox1"; this->comboBox1->Size = System::Drawing::Size(242, 21); this->comboBox1->TabIndex = 1; // // listBox1 // this->listBox1->FormattingEnabled = true; this->listBox1->Location = System::Drawing::Point(278, 31); this->listBox1->Name = L"listBox1"; this->listBox1->Size = System::Drawing::Size(347, 290); this->listBox1->TabIndex = 2; // // textBox1 // this->textBox1->Location = System::Drawing::Point(18, 131); this->textBox1->Name = L"textBox1"; this->textBox1->Size = System::Drawing::Size(242, 20); this->textBox1->TabIndex = 3; // // label1 // this->label1->AutoSize = true; this->label1->Location = System::Drawing::Point(15, 31); this->label1->Name = L"label1"; this->label1->Size = System::Drawing::Size(93, 13); this->label1->TabIndex = 4; this->label1->Text = L"Выбор действия:"; // // label2 // this->label2->AutoSize = true; this->label2->Location = System::Drawing::Point(15, 101); this->label2->Name = L"label2"; this->label2->Size = System::Drawing::Size(35, 13); this->label2->TabIndex = 5; this->label2->Text = L"Ввод:"; // // Form1 // this->AutoScaleDimensions = System::Drawing::SizeF(6, 13); this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font; this->ClientSize = System::Drawing::Size(643, 342); this->Controls->Add(this->label2); this->Controls->Add(this->label1); this->Controls->Add(this->textBox1); this->Controls->Add(this->listBox1); this->Controls->Add(this->comboBox1); this->Controls->Add(this->button1); this->Name = L"Form1"; this->StartPosition = System::Windows::Forms::FormStartPosition::CenterScreen; this->Text = L"Лабораторная работа №5 // Зубов Иван, А-07-11"; this->ResumeLayout(false); this->PerformLayout();
}
// Считывание текстового файла /*void readfile(tree **root) { FILE *file; int n = 0; char* file_name = "text.txt"; char load_string[50] = ""; string str,last; bool flag = false;
file = fopen(file_name,"r"); // r означает открытие текстового файла на чтение if(file!= 0) { fgets(load_string,50,file); _tcprintf(_T("%s\r\n"), _T("В текстовом файле лежат такие данные: ")); cout << load_string << endl; } else _tcprintf(_T("%s\r\n"), _T("Файл не найден.")); fclose(file);
str = load_string;
string::size_type begin, end = 0, pos=0;
_tcprintf(_T("%s\r\n"), _T("Среди них распознаны числа: ")); while(1) { begin = str.find_first_of("0123456789",end); if(begin == string::npos) break; // если нет else flag = true; end = str.find_first_not_of("0123456789",begin); last = str.substr (begin, end-begin); n = atoi(last.c_str()); cout << n << " "; if (*root == 0) *root = first(n); else add(*root, n); if(pos > end-1) break; } if (flag == false) _tcprintf(_T("%s\r\n"), _T("В текстовом файле нет чисел.")); }*/
//============================================================ // Начальное формирование данных
//============================================================ // Добавление числа void add(tree *root, int n) { tree *pv = new tree; tree *prev = 0; tree *p; bool flag; pv->left = 0; pv->right = 0; do { flag = 1; p = root; pv->name = n; while (p!=0) { prev = p; if (pv->name <= p->name) p = p->left; else p = p->right; } } while (flag == 0); if (pv->name <= prev->name) prev->left = pv; else if (pv->name > prev->name) prev->right = pv; }
//============================================================ // Спуск по дереву (для функции удаления) tree *descent(tree *p) { tree *prev, *y = p->right; if (y->left == 0) y->left = p->left; else { do { prev = y; y = y->left; } while (y->left);
y->left = p->left; prev->left = y->right; y->right = p->right; } return y; }
//============================================================ // Удаление числа tree *del(tree *root, int name) { tree *parent, *p, *y; parent = p = root; bool found = 0; while (p!=0) { if (name == p->name) { found = 1; break; } else if (name < p->name) { parent = p; p = p->left; } else { parent = p; p = p->right; } }
if (found == 0) listBox1->Items->Add("Нет такого числа."); else { if (p->left==0) y = p->right; else if (p->right==0) y = p->left; else y = descent(p); if (p == root) root = y; else { if (p->name < parent->name) parent->left = y; else parent->right = y; } delete p; } return root; }
//============================================================ // Удаление дерева tree *delder(tree *root) { if (root) root = 0; return root; }
//============================================================ // Рекурсивный обход 0 (Прямой обход) void obhod0 (tree *root) { if (root == 0) return;
obhod0(root->left); // Рекурсия obhod0(root->right); oip++;// Рекурсия }
//============================================================ // Рекурсивный обход 1 (Прямой обход) void obhod1 (tree *root) { if (root == 0) return;
listBox1->Items->Add(root->name);
obhod1(root->left); // Рекурсия obhod1(root->right); oip++;// Рекурсия
}
//============================================================ // Рекурсивный обход 2 (Обратный обход) void obhod2 (tree *root) { if (root == 0) return;
obhod2(root->left); // Рекурсия obhod2(root->right); // Рекурсия listBox1->Items->Add(root->name); }
//============================================================ // Рекурсивный обход 3 (Симметричный обход) void obhod3 (tree *root) { if (root == 0) return;
obhod3(root->left); // Рекурсия listBox1->Items->Add(root->name); obhod3(root->right); // Рекурсия }
//============================================================ // Поиск данных void search_dubl (tree *root) { if(root == 0) return;
if(root->left!= 0 && root->name == root->left->name) listBox1->Items->Add(root-> name);
search_dubl(root->left); // Рекурсия search_dubl(root->right); // Рекурсия }
//============================================================ //Поиск данных void search (tree *root, int name) { bool found = 0; tree *p = root; while (p!=0) { if (p->name > name) p = p->left; else if (p->name < name) p = p->right; else { // иначе, если переменные равны found = 1; listBox1->Items->Add("Найдено: "); listBox1->Items->Add(p->name); break; } } if (found == 0) listBox1->Items->Add("Число не найдено."); }
//============================================================
#pragma endregion private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
switch (comboBox1->SelectedIndex) { //Считать из текстового файла /*case 0: if (root == 0) readfile(&root); else { root = delder(root); readfile(&root); } break;*/
//Добавить число case 1: { name = Convert::ToInt32(textBox1->Text); listBox1->Items->Add("Добавлено число: " + name); // name=5;//cin >> name; if (root == 0) root = first(name); else add(root,name); } break;
//Найти число case 2: if (root == 0) listBox1->Items->Add("Нет дерева."); else {
name = Convert::ToInt32(textBox1->Text); listBox1->Items->Add("Ищем число: " + name);
//name=this->textBox1->Text; //name=4;//cin >> name search(root,name); } break; //Найти дубликаты case 3: if (root == 0) listBox1->Items->Add("Нет дерева."); else search_dubl(root);
break; //Прямой обход case 4: if (root == 0) listBox1->Items->Add("Нет дерева."); else { listBox1->Items->Add("Прямой обход:"); obhod1(root); printf("%d",oip); } break; //Обратный обход case 5: if (root == 0) listBox1->Items->Add("Нет дерева."); else { listBox1->Items->Add("Обратный обход:"); obhod2(root); } break; //Симметричный обход case 6: if (root == 0) listBox1->Items->Add("Нет дерева.:"); else { listBox1->Items->Add("Симметричный обход:"); obhod3(root); } break; //Удалить число case 7: if (root == 0) listBox1->Items->Add("Нет дерева."); else { listBox1->Items->Add("Введите число, которое хотите удалить: "); name = Convert::ToInt32(textBox1->Text); //name=5;//cin >> name root = del(root, name); } break; //Удалить дерево case 8: if (root == 0) listBox1->Items->Add("Нет дерева."); else { root = delder(root); listBox1->Items->Add("Дерево удалено."); } break; //Найти число листьев case 9: { oip=0; obhod0(root); listBox1->Items->Add("Число листьев равно " + oip); } break;
}
} }; }
|