C언어 구조체 및 공용체 주요예제 6 (트리 오름차순 정렬 (미완성))

내용 출처 : YES C (정보공학연구소 /생능출판사)

데이터를 입력받아 트리에 저장한 후 출력한다.

단 값이 입력될 때, root보다 작으면 왼쪽 노드에, 크면 오른쪽 노드에 저장한다.

이렇게 저장한 후 중위순 운행을 하면 오름차순으로 정렬된 결과가 출력된다.

//제대로 작동 안함.  다시 분석해야할 예제

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>

#define LEFT 0
#define RIGHT 1

typedef int DATA;

struct NODE {
	DATA d;
	NODE *left;
	NODE *right;
};

typedef NODE* BTREE;

BTREE add_node(BTREE parent, BTREE r_node, DATA d1, int r_1);
BTREE new_node(DATA d1);
void inorder(BTREE root);

BTREE root = NULL;

int main()
{
	DATA a;
	int size = 10;
	int i;

	for (i = 0; i < size; i++) {
		scanf_s("%d", &a);
		add_node(root, root, a, 0);
	}

	printf("Inorder binary tree traversal : ");
	inorder(root);
	printf("\n");	
}

BTREE add_node(BTREE parent, BTREE r_node, DATA d1, int r_1)
{
	if (root == NULL) {
		root = new_node(d1);
	}
	else {
		if (r_node == NULL) {
			if (r_1 == 0) {
				parent->left = new_node(d1);
			}
			else {
				parent->right = new_node(d1);
			}
		}
		else if (d1 > r_node->d) {
			parent = r_node;
			add_node(parent, r_node->left, d1, RIGHT);
		}
		else {
			parent = r_node;
			add_node(parent, r_node->left, d1, LEFT);
		}
	}

	return root;
}

BTREE new_node(DATA d1)
{
	BTREE t;

	t = (BTREE)malloc(sizeof(NODE));
	assert(t != NULL);
	t->d = d1;
	t->left = NULL;
	t->right = NULL;

	return t;
}

void inorder(BTREE root)
{
	if (root != NULL) {
		inorder(root->left);
		printf("%d ", root->d);
		inorder(root->right);
	}
}