#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    int isThreaded;
} Node;


Node* createNode(int data);
Node* insert(Node* root, int data);
void printTree(Node* root, int level, int showThreads);
void inorder(Node* root);
void preorder(Node* root);
void postorder(Node* root);
void createThreadedBST(Node* root, Node** lastNode);
void threadedInorderTraversal(Node* root);
Node* leftMost(Node* node);
void deleteSubtree(Node** root, int key);
void freeTree(Node* root);
void clearInputBuffer();
int search(Node* root, int key);
void deleteSubtreeRecursive(Node** root, int key);
Node* copyTree(Node* root);

int main() {
    Node* root = NULL;
    Node* threadedRoot = NULL;
    int choice, data, key;
    Node* lastNode = NULL;

    while (1) {
        printf("1. Построить дерево двоичного поиска и вывести\n");
        printf("2. Выполнить 3 полных обхода (с выделением)\n");
        printf("3. Сделать симметричную правую прошивку и вывести\n");
        printf("4. Удаление из прошитого дерева и вывод\n");
        printf("5. Выход\n");
        printf("Выберите пункт: ");

        if (scanf("%d", &choice) != 1) {
            printf("Ошибка ввода!\n");
            clearInputBuffer();
            continue;
        }
        clearInputBuffer();

        switch (choice) {
            case 1:
                freeTree(root);
                freeTree(threadedRoot);
                root = NULL;
                threadedRoot = NULL;

                printf("Введите элементы (для завершения введите -1):\n");
                while (1) {
                    printf("Элемент: ");
                    if (scanf("%d", &data) != 1) {
                        printf("Некорректный ввод. Попробуйте снова.\n");
                        clearInputBuffer();
                        continue;
                    }
                    if (data == -1) break;
                    root = insert(root, data);
                }
                printf("\nДерево:\n");
                printTree(root, 0, 0);
                break;

            case 2:
                if (root == NULL) {
                    printf("Дерево пусто!\n");
                    break;
                }
                printf("\nПрямой обход (трассировка): ");
                preorder(root);
                printf("\nСимметричный обход (трассировка): ");
                inorder(root);
                printf("\nОбратный обход (трассировка): ");
                postorder(root);
                printf("\n");
                break;

            case 3:
                if (root == NULL) {
                    printf("Дерево пусто!\n");
                    break;
                }
                freeTree(threadedRoot);
                threadedRoot = copyTree(root);
                lastNode = NULL;
                createThreadedBST(threadedRoot, &lastNode);

                if (lastNode != NULL && lastNode->right == NULL) {
                    lastNode->right = threadedRoot;
                    lastNode->isThreaded = 1;
                }

                printf("\nПрошитый симметричный обход: ");
                threadedInorderTraversal(threadedRoot);
                printf("\n\nПрошитое дерево:\n");
                printTree(threadedRoot, 0, 1);
                break;

            case 4:
                if (root == NULL) {
                    printf("Дерево пусто!\n");
                    break;
                }
                printf("Введите ключ для удаления: ");
                if (scanf("%d", &key) != 1) {
                    printf("Ошибка ввода!\n");
                    clearInputBuffer();
                    break;
                }
                if (!search(root, key)) {
                    printf("Элемент %d не найден.\n", key);
                }
                else {
                    deleteSubtree(&root, key);
                    deleteSubtree(&threadedRoot, key);

                    if (threadedRoot != NULL) {
                        lastNode = NULL;
                        createThreadedBST(threadedRoot, &lastNode);

                        if (lastNode != NULL && lastNode->right == NULL) {
                            lastNode->right = threadedRoot;
                            lastNode->isThreaded = 1;
                        }
                    }

                    printf("\nПосле удаления:\n");
                    printf("Исходное дерево:\n");
                    printTree(root, 0, 0);
                    printf("\nПрошитое дерево:\n");
                    printTree(threadedRoot, 0, 1);
                    printf("\nОбновлённый прошитый обход: ");
                    threadedInorderTraversal(threadedRoot);
                    printf("\n");
                }
                break;

            case 5:
                freeTree(root);
                freeTree(threadedRoot);
                printf("Программа завершена.\n");
                return 0;

            default:
                printf("Неверный выбор! Попробуйте снова.\n");
        }
    }
    return 0;
}

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Ошибка выделения памяти!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->isThreaded = 0;
    return newNode;
}

Node* insert(Node* root, int data) {
    if (root == NULL) return createNode(data);
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    return root;
}

int search(Node* root, int key) {
    if (root == NULL) return 0;
    if (key == root->data) return 1;
    if (key < root->data) return search(root->left, key);
    if (!root->isThreaded) return search(root->right, key);
    return 0;
}

void printTree(Node* root, int level, int showThreads) {
    if (root == NULL) return;

    for (int i = 0; i < level; i++) {
        printf("    ");
    }
    printf("%d", root->data);

    if (showThreads && root->isThreaded && root->right != NULL) {
        printf(" (%d)", root->right->data);
    }
    printf("\n");

    int hasLeft = (root->left != NULL);
    int hasRight = (!root->isThreaded && root->right != NULL);

    if (hasLeft && hasRight) {
        printTree(root->left, level + 1, showThreads);
        printTree(root->right, level + 1, showThreads);
    }

    else if (hasLeft && !hasRight) {
        printTree(root->left, level + 1, showThreads);
        for (int i = 0; i < level + 1; i++) {
            printf("    ");
        }
        printf("-\n");
    }

    else if (!hasLeft && hasRight) {
        for (int i = 0; i < level + 1; i++) {
            printf("    ");
        }
        printf("-\n");
        printTree(root->right, level + 1, showThreads);
    }

}


void inorder(Node* root) {
    if (root == NULL) {
        printf("0 ");
        return;
    }
    printf("%d ", root->data);
    inorder(root->left);
    printf("(%d) ", root->data);
    inorder(root->right);
    printf("%d ", root->data);
}


void preorder(Node* root) {
    if (root == NULL) {
        printf("0 ");
        return;
    }
    printf("(%d) ", root->data);
    preorder(root->left);
    printf("%d ", root->data);
    preorder(root->right);
    printf("%d ", root->data);
}

void postorder(Node* root) {
    if (root == NULL) {
        printf("0 ");
        return;
    }
    printf("%d ", root->data);
    postorder(root->left);
    printf("%d ", root->data);
    postorder(root->right);
    printf("(%d) ", root->data);
}

Node* leftMost(Node* node) {
    if (node == NULL) return NULL;
    while (node->left != NULL)
        node = node->left;
    return node;
}


void createThreadedBST(Node* root, Node** lastNode) {
    if (root == NULL) return;

    createThreadedBST(root->left, lastNode);

    if (*lastNode != NULL && (*lastNode)->right == NULL) {
        (*lastNode)->right = root;
        (*lastNode)->isThreaded = 1;
    }
    *lastNode = root;

    if (!root->isThreaded) {
        createThreadedBST(root->right, lastNode);
    }
}

void threadedInorderTraversal(Node* root) {
    if (root == NULL) {
        printf("(пусто)");
        return;
    }

    Node* current = leftMost(root);
    int first = 1;
    int rootVisited = 0;

    while (current != NULL) {
        if (!first) {
            printf(" ");
        }
        printf("%d", current->data);
        first = 0;

        if (current == root) {
            if (rootVisited) {
                break;
            }
            rootVisited = 1;
        }

        if (current->isThreaded) {
            current = current->right;
        }
        else {
            current = leftMost(current->right);
        }
    }
}

Node* copyTree(Node* root) {
    if (root == NULL) return NULL;

    Node* newNode = createNode(root->data);
    newNode->left = copyTree(root->left);
    newNode->right = copyTree(root->right);
    newNode->isThreaded = 0;

    return newNode;
}


void deleteSubtree(Node** root, int key) {
    if (*root == NULL) return;


    if ((*root)->data == key) {
        freeTree(*root);
        *root = NULL;
        return;
    }

    deleteSubtreeRecursive(root, key);
}

void deleteSubtreeRecursive(Node** root, int key) {
    if (*root == NULL) return;

    if ((*root)->data == key) {
        Node* leftSubtree = (*root)->left;
        Node* rightSubtree = (*root)->right;

        free(*root);

        if (leftSubtree != NULL && rightSubtree != NULL) {
            Node* maxNode = leftSubtree;
            while (maxNode->right != NULL && !maxNode->isThreaded) {
                maxNode = maxNode->right;
            }
            *root = maxNode;
            maxNode->left = (maxNode != leftSubtree) ? leftSubtree : maxNode->left;
            maxNode->right = rightSubtree;
        }
        else if (leftSubtree != NULL) {
            *root = leftSubtree;
        }
        else {
            *root = rightSubtree;
        }
        return;
    }

    if (key < (*root)->data) {
        deleteSubtreeRecursive(&(*root)->left, key);
    } else {
        deleteSubtreeRecursive(&(*root)->right, key);
    }
}

void freeTree(Node* root) {
    if (root == NULL) return;
    freeTree(root->left);
    if (!root->isThreaded) {
        freeTree(root->right);
    }
    free(root);
}

void clearInputBuffer() {
    int c;
    while ((c = getchar()) != '\n' && c != EOF);
}