/*
#include <stdio.h>
typedef struct treeNode_ {
int data;
struct treeNode_ *left, *right;
}treeNode;
treeNode* insertNode(treeNode *p, int x)
{
treeNode *newNode;
if(p==NULL) {
newNode=(treeNode*)malloc(sizeof(treeNode*));
newNode->data=x;
newNode->left=NULL;
newNode->right=NULL;
return newNode;
}
else if(x<p->data)
p->left=insertNode(p->left, x);
else if(x>p->data)
p->right=insertNode(p->right, x);
else printf("\nerror\n");
return p;
}
void deleteNode(treeNode *root, int key)
{
treeNode *parent, *child, *p, *succ, *succ_parent;
parent=NULL;
p=root;
while((p!=NULL)&&(p->data!=key)) {
parent=p;
if(key<p->data) p=p->left;
else p=p->right;
}
if(p==NULL) {
printf("\nerror\n");
return;
}
if((p->left==NULL)&&(p->right==NULL)) {
if(parent!=NULL) {
if(parent!=NULL) {
if(parent->left==p) parent->left=NULL;
else parent->right=NULL;
}
else root=NULL;
}
}
else if((p->left==NULL)||(p->right==NULL)) {
if(p->left!=NULL) child=p->left;
else child=p->right;
if(parent!=NULL) {
if(parent->left==p) parent->left=child;
else parent->right=child;
}
else root=child;
}
else {
succ_parent=p;
succ=p->left;
while(succ->right!=NULL) {
succ_parent=succ;
succ=succ->right;
}
if(succ_parent->left==succ) succ_parent->left=succ->left;
else succ_parent->right=succ->left;
p->data=succ->data;
p=succ;
}
free(p);
}
void displayInorder(treeNode* root)
{
if(root) {
displayInorder(root->left);
printf("%d ", root->data);
displayInorder(root->right);
}
}
int main()
{
treeNode *root=NULL;
FILE *fp;
int n, ro, button;
fp=fopen("data.txt", "r");
if(fp==NULL) {
printf("file not found\n");
return 0;
}
fscanf(fp, "%d", &ro);
root=insertNode(root, ro);
while(!feof(fp)) {
fscanf(fp, "%d", &n);
insertNode(root, n);
}
printf("1:출력 2:삽입 3:삭제 4:종료\n");
while(1) {
scanf("%d", &button);
if(button==1) {
printf("이진 트리 출력 : ");
displayInorder(root);
}
else if(button==2) {
}
else if(button==3) {
}
else if(button==4) {
printf("종료합니다.\n");
return 0;
}
else {
printf("다시 입력하세요.\n");
}
}
return 0;
}
*/
/*
#include <stdio.h>
typedef struct treeNode_ {
int data;
struct treeNode_ *left, *right;
}treeNode;
treeNode* insertNode(treeNode *p, int x)
{
treeNode *newNode;
if(p==NULL) {
newNode=(treeNode*)malloc(sizeof(treeNode));
newNode->data=x;
newNode->left=NULL;
newNode->right=NULL;
return newNode;
}
else if(x<p->data)
p->left=insertNode(p->left, x);
else if(x>p->data)
p->right=insertNode(p->right, x);
else printf("\nerror\n");
return p;
}
void deleteNode(treeNode *root, int key)
{
treeNode *parent, *child, *p, *succ, *succ_parent;
parent=NULL;
p=root;
while((p!=NULL)&&(p->data!=key)) {
parent=p;
if(key<p->data) p=p->left;
else p=p->right;
}
if(p==NULL) {
printf("\nerror\n");
return;
}
if((p->left==NULL)&&(p->right==NULL)) {
if(parent!=NULL) {
if(parent!=NULL) {
if(parent->left==p) parent->left=NULL;
else parent->right=NULL;
}
else root=NULL;
}
}
else if((p->left==NULL)||(p->right==NULL)) {
if(p->left!=NULL) child=p->left;
else child=p->right;
if(parent!=NULL) {
if(parent->left==p) parent->left=child;
else parent->right=child;
}
else root=child;
}
else {
succ_parent=p;
succ=p->left;
while(succ->right!=NULL) {
succ_parent=succ;
succ=succ->right;
}
if(succ_parent->left==succ) succ_parent->left=succ->left;
else succ_parent->right=succ->left;
p->data=succ->data;
p=succ;
}
free(p);
}
void displayInorder(treeNode* root)
{
if(root) {
displayInorder(root->left);
printf("%d ", root->data);
displayInorder(root->right);
}
}
int main()
{
treeNode *root=NULL;
FILE *fp;
int n, ro, button;
fp=fopen("data.txt", "r");
if(fp==NULL) {
printf("file not found\n");
return 0;
}
fscanf(fp, "%d", &ro);
root=insertNode(root, ro);
while(!feof(fp)) {
fscanf(fp, "%d", &n);
insertNode(root, n);
}
printf("1:출력 2:삽입 3:삭제 4:종료\n");
while(1) {
scanf("%d", &button);
if(button==1) {
printf("이진 트리 출력 : ");
displayInorder(root);
}
else if(button==2) {
}
else if(button==3) {
}
else if(button==4) {
printf("종료합니다.\n");
return 0;
}
else {
printf("다시 입력하세요.\n");
}
}
return 0;
}
*/
/* 전위 중위 후위 순회
#include <stdio.h>
typedef struct treeNode_ {
int data;
struct treeNode_ *left, *right;
}treeNode;
treeNode* insertNode(treeNode *p, int x)
{
treeNode *newNode;
if(p==NULL) {
newNode=(treeNode*)malloc(sizeof(treeNode));
newNode->data=x;
newNode->left=newNode->right=NULL;
return newNode;
}
else if(x<p->data)
p->left=insertNode(p->left, x);
else if(x>p->data)
p->right=insertNode(p->right, x);
else printf("\nerror\n");
return p;
}
void Preorder(treeNode* root)
{
if(root) {
printf("%d ", root->data);
Preorder(root->left);
Preorder(root->right);
}
}
void Inorder(treeNode* root)
{
if(root) {
Inorder(root->left);
printf("%d ", root->data);
Inorder(root->right);
}
}
void Postorder(treeNode* root)
{
if(root) {
Postorder(root->left);
Postorder(root->right);
printf("%d ", root->data);
}
}
int main()
{
treeNode *root=NULL;
FILE *fp;
int n, ro, button;
fp=fopen("data.txt", "r");
if(fp==NULL) {
printf("file not found\n");
return 0;
}
while(!feof(fp)) {
fscanf(fp, "%d", &n);
root=insertNode(root, n);
}
printf("전위 순회 : ");
Preorder(root);
printf("\n중위 순회 : ");
Inorder(root);
printf("\n후위 순회 : ");
Postorder(root);
return 0;
}
*/
#include <stdio.h>
#define MAX_ELEMENT 100
typedef struct {
int heap[MAX_ELEMENT], heap_size;
}Heap;
Heap *createHeap()
{
Heap *h=(Heap*)malloc(sizeof(Heap));
h->heap_size=0;
return h;
}
void insertHeap(Heap *h, int item)
{
int i;
h->heap_size=h->heap+1;
i=h->heap_size;
while((i!=1)&&(item>h->heap[i/2])) {
h->heap[i]=h->heap[i/2];
i/=2;
}
h->heap[i]=item;
}
int deleteHeap(Heap *h)
{
int parent, child, item, tmp;
item=h->heap[1];
tmp=h->heap[h->heap_size];
h->heap_size=h->heap_size-1;
parent=1;
child=2;
while(child<=h->heap_size) {
if((child<h->heap_size)&&(h->heap[child])<h->heap[child+1])
child++;
if(tmp>=h->heap[child]) break;
else {
h->heap[parent]=h->heap[child];
parent=child;
child=child*2;
}
}
h->heap[parent]=tmp;
return item;
}
void printHeap(Heap *h)
{
int i;
printf("Heap : ");
for(i=1;i<=h->heap_size;i++) {
printf("[%d] ", h->heap[i]);
}
}
void main()
{
int i, n, item;
Heap *heap=createHeap();
insertHeap(heap, 10);
insertHeap(heap, 45);
insertHeap(heap, 19);
insertHeap(heap, 11);
insertHeap(heap, 96);
printHeap(heap);
n=heap->heap_size;
for(i=1;i<=n;i++) {
item=deleteHeap(heap);
printf("\n delete : [%d] ", item);
}
getchar();
}