tree

#include <iostream>

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode* next;

    TreeNode(int val) : value(val), left(nullptr), right(nullptr), next(nullptr) {}
};

// Функция для связывания узлов одного уровня с помощью указателя next
void ConnectNext(TreeNode* left, TreeNode* right) {
    if (!left || !right) return;

    left->next = right;

    // Связываем узлы одного родителя
    ConnectNext(left->left, left->right);
    ConnectNext(right->left, right->right);

    // Связываем правого ребёнка одного узла с левым ребёнком следующего
    ConnectNext(left->right, right->left);
}

// Обёртка для обработки дерева
TreeNode* Process(TreeNode* root) {
    if (!root) return nullptr;
    ConnectNext(root->left, root->right);
    return root;
}

// Построение дерева из ввода
TreeNode* BuildTree() {
    TreeNode* root = nullptr;

    std::cout << "Введите дерево в формате: Родитель Левый_Ребёнок Правый_Ребёнок.\n";
    std::cout << "Для пропуска ребёнка введите -1. Завершите ввод пустой строкой.\n";

    TreeNode* nodes[100] = {nullptr}; // Максимум 100 узлов; индекс узла соответствует его значению

    while (true) {
        int parent, left, right;
        if (!(std::cin >> parent >> left >> right)) break;

        // Создаём узел-родитель, если он ещё не создан
        if (!nodes[parent]) {
            nodes[parent] = new TreeNode(parent);
            if (!root) root = nodes[parent]; // Первый узел считается корнем
        }

        // Создаём левого ребёнка, если он задан
        if (left != -1) {
            if (!nodes[left]) {
                nodes[left] = new TreeNode(left);
            }
            nodes[parent]->left = nodes[left];
        }

        // Создаём правого ребёнка, если он задан
        if (right != -1) {
            if (!nodes[right]) {
                nodes[right] = new TreeNode(right);
            }
            nodes[parent]->right = nodes[right];
        }
    }

    return root;
}

// Вспомогательная функция для вывода дерева с учётом указателей next
void PrintTreeWithNext(TreeNode* root) {
    if (!root) return;

    TreeNode* level = root;
    while (level) {
        TreeNode* current = level;
        level = nullptr;

        while (current) {
            std::cout << current->value << " -> ";
            if (!level && (current->left || current->right)) {
                level = current->left ? current->left : current->right;
            }
            current = current->next;
        }
        std::cout << "NULL\n";
    }
}

int main() {
    // Построение дерева
    TreeNode* root = BuildTree();

    // Обработка дерева
    Process(root);

    // Вывод результата
    std::cout << "Результат (уровни дерева с указателями next):\n";
    PrintTreeWithNext(root);

    // Освобождение памяти (опционально)
    // Здесь можно добавить функцию для рекурсивного удаления узлов.

    return 0;
}