trees.cpp - master - g1eson/BinaryTree

trees.cpp
150 строк4 KB
g1eson
Загрузить файлы в «»
23 окт 2025, 23:12
23 окт 2025, 23:129975c88
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
using namespace std;

struct tnode {
    int field;
    struct tnode *left;
    struct tnode *right;
};

tnode* newNode(int key) {
    tnode* node = new tnode();
    node->field = key;
    node->left = nullptr;
    node->right = nullptr;
    return node;
}

tnode* insert(tnode* root, int key) {
    if (root == nullptr) {
        return newNode(key);
    }
    if (key < root->field) {
        root->left = insert(root->left, key);
    } else {
        root->right = insert(root->right, key);
    }
    return root;
}

//прямой обход 
void treeStraight(tnode *tree, vector<int>& result) {
    if (tree != nullptr) {
        result.push_back(tree->field);
        treeStraight(tree->left, result);
        treeStraight(tree->right, result);
    }
}

//симметричный обход
void treeSymmetric(tnode *tree, vector<int>& result) {
    if (tree != nullptr) {
        treeSymmetric(tree->left, result);
        result.push_back(tree->field);
        treeSymmetric(tree->right, result);
    }
}

//обратный обход
void treeRev(tnode *tree, vector<int>& result) {
    if (tree != nullptr) {
        treeRev(tree->left, result);
        treeRev(tree->right, result);
        result.push_back(tree->field);
    }
}

// поиск
bool search(tnode* root, int key) {
    if (root == nullptr) {
        return false;
    }
    if (key == root->field) {
        return true;
    }
    if (key < root->field) {
        return search(root->left, key);
    }
    return search(root->right, key);
}

bool isSortedNonDecreasing(const vector<int>& v) {
    for (size_t i = 1; i < v.size(); ++i) {
        if (v[i-1] > v[i]) return false;
    }
    return true;
}

int main() {
    const int N = 1000000;
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<int> dist(1, 1500000);

    auto start = chrono::high_resolution_clock::now();
    tnode* root = nullptr;
    for (int i = 0; i < N; ++i) {
        int value = dist(gen);
        root = insert(root, value);
    }
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double> build_time = end - start;
    cout << "Время построения дерева: " << build_time.count() << " с\n";

    // Прямой обход
    vector<int> pre;
    start = chrono::high_resolution_clock::now();
    treeStraight(root, pre);
    end = chrono::high_resolution_clock::now();
    chrono::duration<double> pre_time = end - start;
    cout << "Время прямого обхода: " << pre_time.count() << " с\n";

    // Симметричный обход
    vector<int> ino;
    start = chrono::high_resolution_clock::now();
    treeSymmetric(root, ino);
    end = chrono::high_resolution_clock::now();
    chrono::duration<double> ino_time = end - start;
    if (!isSortedNonDecreasing(ino)){
        cout << "Ошибка";
        return 1;
    }
    cout << "Время симметричного обхода: " << ino_time.count() << " с\n";

    // Обратный обход
    vector<int> post;
    start = chrono::high_resolution_clock::now();
    treeRev(root, post);
    end = chrono::high_resolution_clock::now();
    chrono::duration<double> post_time = end - start;
    cout << "Время обратного обхода: " << post_time.count() << " с\n";

    if (pre.size() != N || ino.size() != N || post.size() != N) {
        cout << "Ошибка: Неполный обход!\n";
        return 1;
    }
    int key;
    cout << "Введите число, которое хотите найти: ";
    cin >> key;
    // Поиск
    start = chrono::high_resolution_clock::now();
    bool finded = search(root, key);
    end = chrono::high_resolution_clock::now();
    chrono::duration<double> search_time = end - start;
    bool flag = false;
    for (int i = 0; i < ino.size(); i++){
        if (ino[i] == key){
            flag = true;
            break;
        }
    }
    if (flag != finded){
        cout << "Ошибка";
        return 1;
    }
    cout << "Время поиска заняло: " << search_time.count() << " с\n";
    cout << (finded ? "Число найдено" : "Число не найдено");
}