C언어 구조체 및 공용체 주요예제4 (트리 방문 프로그램)

트리(tree) 방문 프로그램

※ 참고 : 트리는 노드(node)라 부르는 원소들로 구성된다. 또한 루트(root) 노드를 하나 보유하는데, 루트를 제외한 나머지 노드들은 서로 별개인 부트리(subtree)로 나눌 수 있다.

■ 2진 트리(Binary tree) : 두 개 이하의 자손을 원소로 갖는 트리

● 이진 트리 구조는 왼쪽 자손(left offspring), 오른쪽 자손(right offspring)이라는 두개의 링크 필드를 가진 자료 구조로 간주할 수 있으므로, 이러한 표현 방식을 따르면 잎 노드는 왼쪽 자손과 오른쪽 자손의 값을 NULL로 가지는 노드이다.

■ 2진 트리의 원소를 방문하는 방법

● 중위순(inorder) : 왼쪽 부트리 -> 루트 -> 오른쪽 부트리 순으로

● 전위순(preorder) : 루트 -> 왼쪽 부트리 -> 오른쪽 부트리 순으로

● 후위순(postorder) : 왼쪽 부트리 -> 오른족 부트리 -> 루트 순으로

// A linked list implementation of a queue.

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

typedef char DATA;

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

typedef NODE* BTREE;

BTREE create_tree(DATA a[], int i, int size);
BTREE init_node(DATA d1, BTREE p1, BTREE p2);
BTREE new_node(void);
void inorder(BTREE root);
void preorder(BTREE root);
void postorder(BTREE root);


int main()
{
	BTREE t;
	DATA a[] = "GAHBEIJCDF";
	int size = 10;			//size of a[]

	t = create_tree(a, 0, size);

	printf("inorder binary tree traversal: ");
	inorder(t);
	printf("\n");

	printf("preorder binary tree traversal: ");
	preorder(t);
	printf("\n");

	printf("postorder binary tree traversal: ");
	postorder(t);
	printf("\n");
}

//create a linked binary tree from an array
BTREE create_tree(DATA a[], int i, int size)
{
	if (i >= size) {
		return NULL;
	}
	else {
		return (init_node(a[i], create_tree(a, 2 * i + 1, size), create_tree(a, 2 * i + 2, size)));
	}
}

//initialize a node in a binary tree
BTREE init_node(DATA d1, BTREE p1, BTREE p2)
{
	BTREE t;
	
	t = new_node();
	t->d = d1;
	t->left = p1;
	t->right = p2;

	return t;
}

//create a new node
BTREE new_node(void)
{
	BTREE t;

	t = (BTREE)malloc(sizeof(NODE));
	assert(t != NULL);

	return t;
}

//inorder binary tree traversal
void inorder(BTREE root)
{
	if (root != NULL) {
		preorder(root->left);	//recur left
		printf("%c ", root->d);
		preorder(root->right);	//recur right
	}
}

//preorder binary tree traversal
void preorder(BTREE root)
{
	if (root != NULL) {
		printf("%c ", root->d);
		preorder(root->left);
		preorder(root->right);
	}
}

//postorder binary tree traversal
void postorder(BTREE root)
{
	if (root != NULL) {
		postorder(root->left);
		postorder(root->right);
		printf("%c ", root->d);
	}
}