알고리즘 스터디 4회차 - Linked List로 Heap Sort구현

실패했다. ㅈㅈ...

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
typedef struct node *nodeptr;
void swap(int *a, int *b);
 
typedef struct node {
    int key;
    nodeptr left;
    nodeptr right;
    nodeptr next;
    nodeptr parent;
}node;
 
typedef struct queue {
    nodeptr head;
    nodeptr tail;
}queue;
 
typedef struct tree {
    node *root;
}tree;
 
void push(queue *queue, node *newnode);
 
int n = 0;
 
void push(queue *queue, node *newnode) {
 
    if (queue->head == NULL && queue->tail == NULL) {
        queue->head = newnode;
        queue->tail = newnode;
    }
 
    else {
        queue->tail->next = newnode;
        queue->tail = newnode;
    }
 
    printf("Succeessfully added\n");
}
 
void pop(queue *q) {
    /*
    node *lastnode = queue->head;
    printf("%d ", queue->head->key);
    if (lastnode->next != NULL) queue->head = lastnode->next;
    */
    if (q->head == NULL) {
        printf("pop error\n");
        return;
    }
 
    printf("%d ", q->head->key);
    q->head = q->head->next;
}
 
void AddNode(tree *tree, int key, queue *queue) {
    node *newNode = (node *)malloc(sizeof(node));
    node *currentNode = (node *)malloc(sizeof(node));
 
    printf("키값: %d\n", key);
 
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;
 
    printf("들어간 키값: %d\n", newNode->key);
 
    if (tree->root == NULL) {
        tree->root = newNode;
        push(queue, newNode);
        printf("루트 생성");
        return;
    }
 
    printf("[노드 생성]뉴노드 생성\n");
    currentNode = queue->head;
 
    if (currentNode->left == NULL) {
        currentNode->left = newNode;
        newNode->parent = currentNode;
        push(queue, newNode);
        printf("[노드 추가]왼쪽 자식에 뉴 노드 추가\n");
        return;
    }
 
    else if (currentNode->right == NULL) {
        currentNode->right = newNode;
        newNode->parent = currentNode;
        push(queue, newNode);
        printf("[노드 추가]오른쪽 자식에 뉴 노드 추가\n");
        pop(queue);
        return;
    }
    printf("[알림] 트리에 %d값이 추가되었습니다.\n", queue->tail->key);
}
 
void downhip(node *node) {
    if (node->left == NULL && node->right == NULL) {
        return;
    }
    else {
        printf("[PRE] key : %d, left : %d, right : %d\n", node->key, node->left->key, node->right->key);
    }
    //printf("[로그] 다운힙 호출\n");
 
    if (node->left == NULL && node->right == NULL) {
        //printf("[경고] 자식 노드가 비어부럿서\n");
        return;
    }
 
    if (node->left != NULL) downhip(node->left);
    else if (node->right != NULL) downhip(node->right);
    int* cur = &node->key; //printf("현재 노드 값:%d\n", cur);
 
    if (node->left == NULL) {
        if (node->right->key > *cur) {
            swap(&node->right->key, &node->key);
            //printf("오른쪽 노드와 자신 교환\n");
        }
    }
 
    else if (node->right == NULL) {
        if (node->left->key > *cur) {
            swap(&node->left->key, &node->key);
            //printf("왼쪽 노드와 자신 교환\n");
        }
    }
 
    else {
        int* left = &node->left->key; //printf("좌측 노드 값:%d\n", left);
        int* right = &node->right->key; //printf("우측 노드 값:%d\n", right);
 
        if (*left < *right) {
            swap(&node->right->key, &node->left->key);
            //printf("왼쪽 노드와 오른쪽 노드 교환\n");
        }
        if (*left > *cur) {
            swap(&node->left->key, &node->key);
            //printf("왼쪽 노드와 자신 교환\n");
        }
        if (*left < *right) {
            swap(&node->right->key, &node->left->key);
            //printf("왼쪽 노드와 오른쪽 노드 교환\n");
        }
    }
    //printf("[알림] 다운힙 실행\n");
 
    printf("[POST] key : %d, left : %d, right : %d\n\n", node->key, node->left->key, node->right->key);
}
 
void levelOrder(tree *tree) {
    node *newNode = (node *)malloc(sizeof(node));
    newNode = tree->root;
    queue *newQueue = (queue *)malloc(sizeof(queue));
 
    newQueue->head = newNode;
    newQueue->tail = newNode;
 
    while (newNode != NULL) {
        if (newNode->left != NULL) {
            push(newQueue, newNode->left);
        }
 
        if (newNode->right != NULL) {
            push(newQueue, newNode->right);
        }
 
        pop(newQueue);
        if (newQueue->head == NULL) break;
        newNode = newQueue->head;
    }
}
 
void Postorder(nodeptr ptr) {
    if (ptr != NULL) {
        Postorder(ptr->left);
        Postorder(ptr->right);
        printf(" %d ", ptr->key);
    }
}
 
void showmethemoney(tree *tree) {
    Postorder(tree->root);
}
 
void swap(int *a, int *b) {
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
 
int main(void) {
    tree *btree = (tree *)malloc(sizeof(tree));
    queue *que = (queue *)malloc(sizeof(queue));
 
    btree->root = NULL;
    que->head = NULL;
    que->tail = NULL;
 
    for (int i = 0; i < 20; i++) {
        int num = (rand() % 50) + 1;
        printf("[로그] 난수값:%d\n", num);
        AddNode(btree, num, que);
    }
    n = 0;
    for (int j = 0; j < 21; j++) {
        downhip(btree->root);
    }
 
    //return 0;
    levelOrder(btree);
    printf("\n");
    showmethemoney(btree);
    printf("끝");
    _getch();
}