트리 자료구조의 입출력

트리 정보를 입력하여 생성하는 것은 쉽지 않은 일이다. 일반적으로 많이 사용되는 이진 트리 형태로 데이터를 읽어 구축하는 프로그램을 생각해 보자.

먼저 후위표기식 형태의 이진연산자로 구성된 수식을 읽어들여 트리를 구축할 수 있다. 다음과 같은 후위표기식을 입력으로 받아 이진 트리를 구축하는 문제를 생각해 보자.

94-385%+*435+2*++

이 수식에 대한 이진트리는 다음과 같은 형태로 나타낼 수 있다. 이것은 트리의 출력기능을 통해 출력한 결과다.

트리의 노드는 연산자인 경우 넌터미널로 자식을 가진 노드가 되고 숫자는 터미널 노드여서 자식을 갖지 않는다. 그리고 숫자의 경우는 그 숫자를 노드의 데이터로 가진다. 다음 코드는 스택을 이용해 후위표기식의 계산과 같은 방식으로 숫자는 푸시하고 연산자가 나오면 스택에서 두 개를 팝하여 좌우 자식노드로 달아준 다음 푸시한다. 이러한 과정을 수식(input 배열에 있는 문자열)의 끝까지 계속하면 스택에는 루트 노드가 남아있게 된다. 

TreeNode* construct_tree(char* input)
{
	TreeNode* lnode, * rnode, * parent;
	char ch;
	int index = 0;
	StackType* stack = (StackType*)malloc(sizeof(StackType));
	stack->top = -1;
	while ((ch = input[index++]) != '\0') {  // "94-385%+*435+2*++";
		if (ch >= '0' && ch <= '9')
			parent = new_node(ch, 0);
		else {
			parent = new_node(ch, 0);
			rnode = pop(stack);
			lnode = pop(stack);
			add_child(parent, lnode);
			add_child(parent, rnode);
		}
		push(stack, parent);
		//print_tree(parent, 0);
	}
	return pop(stack);
}

여기서 new_node는 새로운 트리 노드를 하나 만드는 함수고 add_child는 왼쪽, 오른쪽에 자식 노드를 붙이는 함수다.

이렇게 만들어진 이진트리를 위에서 본 것처럼 트리 구조로 출력하는 방법은 선방문 순회의 순환적인 호출을 통해 가능하다.

void print_tree(TreeNode* node, int depth)
{
	if (node == NULL)
		return;
	print_node(node, depth);
	print_tree(node->left, depth+1);
	print_tree(node->right, depth+1);
}