#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
// 노드의 구조
typedef struct treeNode *treePointer;
typedef struct treeNode {
char data;
treePointer left, right;
} treeNode;
//* data를 만족하는 node와 그 노드의 부모 노드까지 찾아라.
//*
//* @param node 현재 node
//* @param data 찾고자 하는 data
//* @param parent 현재 node의 부모 node - tree 중간에 insert가 된다면 필요.
//* @return 못찾으면 NULL, 찾으면 node 반환.
treePointer search(treePointer node, char data, treePointer* parent)
{
if (node == NULL) {
return NULL;
}
else {
if (node->data == data) {
return node;
}
}
{
treeNode *temp;
*parent = node;
if ((temp = search(node->left, data, parent))) {
return temp;
}
*parent = node;
if ((temp = search(node->right, data, parent))) {
return temp;
}
}
}
void preorder(treePointer node)
{
if (node == NULL)
return;
printf("%c", node->data);
preorder(node->left);
preorder(node->right);
}
treePointer malloc_node(char data, treePointer left, treePointer right)
{
treePointer node = (treePointer)malloc(sizeof(treeNode));
if (node == NULL) {
fprintf(stderr, "ERROR: fails to malloc\n");
exit(0);
}
node->data = data;
node->left = left;
node->right = right;
return node;
}
//* 삽입연산 함수
//*
//* data를 이진 탐색 트리 root에 삽입한다.
//* data가 이미 root안에 있으면 삽입되지 않는다.
//* 입력받는 3가지 경우 : [CASE1] 현재 노드가 비었다. [CASE2] data1노드x, data2노드o, 현재노드o. [CASE3] data1노드o, 현재노드o
void insert_node(treePointer* root, char data1, char key, char data2)
{
treePointer current;
treePointer parent = NULL;
assert(key == 'F' || key == 'M');
current = search(*root, data1, &parent);
if (current) {
// 자식을 검색해서 아빠, 엄마를 추가한다. [CASE3]
//
treePointer node = malloc_node(data2, NULL, NULL);
current->left = key == 'F' ? node : current->left;
current->right = key == 'M' ? node : current->right;
return;
}
parent = NULL;
current = search(*root, data2, &parent);
if (current) {
// 아빠, 엄마를 검색해서 자식을 추가한다. [CASE2]
// - 자식을 추가해야 하는 경우는 root가 부모일때.
*root = malloc_node(data1, key == 'M' ? current : NULL, key == 'F' ? current : NULL);
return;
}
// 둘다 검색안되면 tree가 빈 경우거나, 조건에 맞는 데이터가 없는 경우인데
// 여기서는 tree가 빈 경우로만 생각한다. [CASE1]
//
{
treePointer node = malloc_node(data2, NULL, NULL);
*root = malloc_node(data1, key == 'F' ? node : NULL, key == 'M' ? node : NULL);
}
}
//* data1를 갖는 노드와 data2를 갖는 노드를 출력하라.
//* @param root 최종노드
//* @variable start data1를 갖는 노드
//* @variable end data2를 갖는 노드
//* @variable exp 왔던적 있는 노드
void find_relation(treePointer root, char data1, char data2)
{
treePointer start = NULL;
treePointer end = NULL;
treePointer temp = NULL;
treePointer exp = NULL;
start = search(root, data1, &temp);
end = search(start, data2, &temp);
{
int stack_top = -1;
treePointer node_stack[100];
char char_stack[100];
treePointer temp = start;
char key;
// depth-first in-order traverse
// 저장.
while (stack_top != -1 || temp != NULL) {
if (temp != NULL) {
//--스택 저장,도착지 판단
node_stack[++stack_top] = temp;
char_stack[stack_top] = key;
if (temp == end)
break;
//-----------------------
temp = temp->left;
key = 'F';
}
else if (temp == NULL) { // temp == NULL
temp = node_stack[stack_top];
if ((temp->left == NULL && temp->right != NULL) || (temp->left == exp && temp->right != NULL)) {
stack_top--;
temp = temp->right;
}
if ((temp->left == NULL && temp->right != NULL) || (temp->left == exp && temp->right != NULL)) {
exp = temp;
stack_top--;
stack_top--;
temp = node_stack[stack_top];
for (; temp->right == exp ;) {
exp = temp;
stack_top--;
temp = node_stack[stack_top];
}
temp = temp->right;
}
key = 'M';
}
}
// 출력.
printf("%c", start->data);
for (int i = 1 ; i <= stack_top ; i++) {
printf(" - %c - %c", char_stack[i], node_stack[i]->data);
}
}
}
// 이진 탐색 프로그램
void main()
{
char string[10];
char a, b, c;
treePointer root = NULL;
while (1){
printf(">>");
scanf_s("%s", string, sizeof(string));
a = string[0];
b = string[2];
c = string[4];
if (b == '?')
{
find_relation(root, a, c);
}
else
{
insert_node(&root, a, b, c);
preorder(root);
}
printf("\n");
}
}
본인삭제금지
글쓰기