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

/* 定義引線二元搜尋樹結構 */
typedef struct student {
    char name[20];      /* 學生姓名 */
    int score;          /* 學生成績 */
    struct student *left;   /* 左子指標 */
    struct student *right;  /* 右子指標 */
    int leftThread;     /* 左線索標記 */
    int rightThread;    /* 右線索標記 */
} student;

/* 全域變數 */
student *root = NULL;
student *head = NULL;

/* 函數原型 */
void insert(char [], int);
void remove_node(char []);
void show_tree();
student *search(char []);
student *find_inorder_successor(student *);
student *find_inorder_predecessor(student *);
void free_tree(student *);

/* 找尋中序後繼節點 */
student *find_inorder_successor(student *node) {
    if (node->rightThread)
        return node->right;

    node = node->right;
    while (!node->leftThread)
        node = node->left;
    return node;
}

/* 找尋中序前驅節點 */
student *find_inorder_predecessor(student *node) {
    if (node->leftThread)
        return node->left;

    node = node->left;
    while (!node->rightThread)
        node = node->right;
    return node;
}

/* 插入節點 */
void insert(char name[], int score) {
    student *new_node, *current, *parent;

    /* 檢查節點是否已存在 */
    if (search(name) != NULL) {
        printf("%s 已存在!\n", name);
        return;
    }

    new_node = (student *)malloc(sizeof(student));
    strcpy(new_node->name, name);
    new_node->score = score;
    new_node->leftThread = new_node->rightThread = 1;

    if (root == NULL) {
        /* 建立表頭節點 */
        head = (student *)malloc(sizeof(student));
        head->leftThread = head->rightThread = 0;
        head->right = head;
        head->left = new_node;

        /* 第一個節點 */
        new_node->left = head;
        new_node->right = head;
        root = new_node;
        return;
    }

    current = root;
    while (1) {
        parent = current;
        if (strcmp(name, current->name) < 0) {
            if (current->leftThread)
                break;
            current = current->left;
        } else {
            if (current->rightThread)
                break;
            current = current->right;
        }
    }

    if (strcmp(name, parent->name) < 0) {
        /* 左子節點 */
        new_node->left = parent->left;
        new_node->right = parent;
        parent->left = new_node;
        parent->leftThread = 0;
    } else {
        /* 右子節點 */
        new_node->right = parent->right;
        new_node->left = parent;
        parent->right = new_node;
        parent->rightThread = 0;
    }
}

/* 中序遍歷 */
void show_tree() {
    student *current;

    if (root == NULL) {
        printf("樹是空的!\n");
        return;
    }

    current = root;
    while (!current->leftThread)
        current = current->left;

    printf("字典變數內部儲存的元素(key：value)如下\n");
    while (current != head) {
        printf("%s：%d\n", current->name, current->score);
        current = find_inorder_successor(current);
    }
}

/* 搜尋節點 */
student *search(char target[]) {
    student *current = root;

    while (current != NULL) {
        if (strcmp(target, current->name) == 0)
            return current;
        
        if (strcmp(target, current->name) < 0) {
            if (current->leftThread)
                break;
            current = current->left;
        } else {
            if (current->rightThread)
                break;
            current = current->right;
        }
    }
    return NULL;
}

/* 刪除節點 */
void remove_node(char name[]) {
    student *node = search(name);
    if (node == NULL) {
        printf("%s 不在樹中!\n", name);
        return;
    }

    // 刪除節點的實作較為複雜，這裡會有更多細節需要處理
    printf("刪除節點的實作在引線二元搜尋樹中較為複雜，需要特別處理線索。\n");
}

/* 釋放樹的記憶體 */
void free_tree(student *node) {
    if (node == NULL) return;

    if (!node->leftThread)
        free_tree(node->left);
    if (!node->rightThread)
        free_tree(node->right);

    printf("刪除'w[%s]=%d'節點\n", node->name, node->score);
    free(node);
}

int main() {
    char line[128], key[20];
    int value;

    printf("輸入存取字典的陳述，按<Enter>結束程式\n");
    while (1) {
        printf("\n指令 => ");
        fgets(line, 128, stdin);

        if (line[0] == '\n') break;

        if (sscanf(line, "w[%[^]]] = %d", key, &value) == 2) {
            insert(key, value);
            printf("新增w[%s]=%d\n", key, value);
        } else if (sscanf(line, "w[%[^]]]?", key) == 1) {
            student *found = search(key);
            if (found)
                printf("字典元素w[%s]=%d\n", key, found->score);
            else
                printf("錯誤! %s 不在此樹中!\n", key);
        } else if (line[0] == 'w' && line[1] == '?') {
            show_tree();
        }
    }

    free_tree(root);
    free(head);
    return 0;
}