[알고리즘] 기본 추상자료형(9) - 예제(트리ADT)

[문제1] 트리의 순회(선위순회, 중위순회, 후위순회)

- 다음과 같이 트리를 구현

- 없는 노드번호를 입력받는다면, -1출력

- 선위순회는 1, 중위순회는 2, 후위순회는 3

- id를 입력받아서 그 노드부터 순회를 하여 출력

입력예시    출력예시

1 2

30 70 90

입력예시    출력예시

2 3	50 130 120 80

입력예시    출력예시

1 9

-1

#include<stdio.h> #include<stdlib.h> struct node { int id; int data; struct node *left; struct node *right; }; void addLeftchild(struct node *parent, int value, int id){ struct node *newnode = (struct node*)malloc(sizeof(struct node)); newnode->data = value; newnode->id = id; newnode->left = NULL; newnode->right = NULL; parent->left = newnode; } void addRightchild(struct node *parent, int value, int id){ struct node *newnode = (struct node*)malloc(sizeof(struct node)); newnode->data = value; newnode->id = id; newnode->left = NULL; newnode->right = NULL; parent->right = newnode; } void preOrder(struct node *tree){ if (tree == NULL) { return; } printf(" %d", tree->data); preOrder(tree->left); preOrder(tree->right); } void inOrder(struct node *tree) { if (tree == NULL) { return; } inOrder(tree->left); printf(" %d", tree->data); inOrder(tree->right); } void postOrder(struct node *tree){ if (tree == NULL) { return; } postOrder(tree->left); postOrder(tree->right); printf(" %d", tree->data); } void freeTree(struct node *tree) { if (tree == NULL) { return; } freeTree(tree->left); freeTree(tree->right); free(tree); } void treeOrder(struct node *tree, int order, int id) { if (tree == NULL) { return; } if (tree->id == id) { if (order == 1) { preOrder(tree); } else if (order == 2) { inOrder(tree); } else if (order == 3) { postOrder(tree); } } else { treeOrder(tree->left, order, id); treeOrder(tree->right, order, id); } } void main(){ int order, id; struct node *root, *p, *tree = (struct node*)malloc(sizeof(struct node)); root = tree; tree->data = 20; tree->id = 1; tree->left = NULL; tree->right = NULL; addLeftchild(tree, 30, 2); addRightchild(tree, 50, 3); addLeftchild(tree->left, 70, 4); addRightchild(tree->left, 90, 5); addRightchild(tree->right, 120, 6); addLeftchild(tree->right->right, 130, 7); addRightchild(tree->right->right, 80, 8); scanf("%d", &order); scanf("%d", &id); if ((1 <= id) && (id <= 8)) { treeOrder(root, order, id); printf("\n"); } else { printf("-1\n"); } freeTree(root); }

[문제2] 위 문제에서 id를 받아서 부트리의 용량의 합을 계산하는 프로그램

- 합을 계산할 때 입력된 id의 노드도 포함

입력예시    출력예시

3

380

입력예시    출력예시

4

70

입력예시    출력예시

9

-1

#include<stdio.h> #include<stdlib.h> struct node { int id; int data; struct node *left; struct node *right; }; void addLeftchild(struct node *parent, int value, int id){ struct node *newnode = (struct node*)malloc(sizeof(struct node)); newnode->data = value; newnode->id = id; newnode->left = NULL; newnode->right = NULL; parent->left = newnode; } void addRightchild(struct node *parent, int value, int id){ struct node *newnode = (struct node*)malloc(sizeof(struct node)); newnode->data = value; newnode->id = id; newnode->left = NULL; newnode->right = NULL; parent->right = newnode; } int preOrder(struct node *tree){ if (tree == NULL) { return 0; } return tree->data + preOrder(tree->left) + preOrder(tree->right); } void freeTree(struct node *tree) { if (tree == NULL) { return; } freeTree(tree->left); freeTree(tree->right); free(tree); } void treeOrder(struct node *tree, int id) { if (tree == NULL) { return; } if (tree->id == id) { printf("%d\n",preOrder(tree)); } else { treeOrder(tree->left, id); treeOrder(tree->right, id); } } void main(){ int id; struct node *root, *p, *tree = (struct node*)malloc(sizeof(struct node)); root = tree; tree->data = 20; tree->id = 1; tree->left = NULL; tree->right = NULL; addLeftchild(tree, 30, 2); addRightchild(tree, 50, 3); addLeftchild(tree->left, 70, 4); addRightchild(tree->left, 90, 5); addRightchild(tree->right, 120, 6); addLeftchild(tree->right->right, 130, 7); addRightchild(tree->right->right, 80, 8); scanf("%d", &id); if ((1 <= id) && (id <= 8)) { treeOrder(root, id); } else { printf("-1\n"); } freeTree(root); }