[Baekjoon][#1991] 트리순회

• [ 장르 ] 트리

1991번: 트리 순회

• My Code ( 트리생성 및 순회를 구현 )

#include <iostream>
using namespace std;

typedef struct Node
{
	char data;
	struct Node* left;
	struct Node* right;
}Node;

void MakeTree(Node* root,int n);
void MakeSubTree(Node* node, char MyData, char LData, char RData);
int IsInternal(Node* node);
void PreOrderPrint(Node *node);
void InOrderPrint(Node* node);
void PostOrderPrint(Node* node);

int main()
{
	Node root;
	int Nodecount;

	cin >> Nodecount;
	MakeTree(&root, Nodecount);
	return 0;
}
void MakeTree(Node* root,int n)
{
	char MyData, LData, RData;
	int i = 0;
	root->left = NULL;
	root->right = NULL;
	
	cin >> MyData >> LData >> RData;
	root->data = MyData;
	if (LData != '.')
	{
		Node *newNode = (Node*)malloc(sizeof(Node));
		newNode->data = LData;
		newNode->left = NULL;
		newNode->right = NULL;
		root->left = newNode;
	}
	if (RData != '.')
	{
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->data = RData;
		newNode->left = NULL;
		newNode->right = NULL;
		root->right = newNode;
	}
	while (i < n - 1)
	{
		cin >> MyData >> LData >> RData;
		MakeSubTree(root, MyData, LData, RData);
		i++;
	}
	PreOrderPrint(root); cout << endl;
	InOrderPrint(root); cout << endl;
	PostOrderPrint(root); cout << endl;
}
void MakeSubTree(Node* node, char MyData, char LData, char RData)
{
	if (node->data == MyData)
	{
		if (LData != '.')
		{
			Node* newNode = (Node*)malloc(sizeof(Node));
			newNode->data = LData;
			newNode->left = NULL;
			newNode->right = NULL;
			node->left = newNode;
		}
		if (RData != '.')
		{
			Node* newNode = (Node*)malloc(sizeof(Node));
			newNode->data = RData;
			newNode->left = NULL;
			newNode->right = NULL;
			node->right = newNode;
		}
	}
	else
	{
		if (!(IsInternal(node)))
		{
			if (node->left != NULL)
				MakeSubTree(node->left, MyData, LData, RData);
			if (node->right != NULL)
				MakeSubTree(node->right, MyData, LData, RData);
		}
	}
}
int IsInternal(Node* node)
{
	return (node->left == NULL) && (node->right == NULL);
}
void PreOrderPrint(Node* node)
{
	cout << node->data;
	if (node->left != NULL)
		PreOrderPrint(node->left);
	if (node->right != NULL)
		PreOrderPrint(node->right);
}
void InOrderPrint(Node* node)
{
	if (node->left != NULL)
		InOrderPrint(node->left);
	cout << node->data;
	if (node->right != NULL)
		InOrderPrint(node->right);
}
void PostOrderPrint(Node* node)
{
	if (node->left != NULL)
		PostOrderPrint(node->left);
	if (node->right != NULL)
		PostOrderPrint(node->right);
	cout << node->data;
}

• Another Code ( 문제의 취지에 맞는 순차리스트(배열)을 이용한 풀이 )

#include <cstdio>

char tree[26][2] = { '.', };

void preorder(char root) {
    if (root == '.') return;
    else {
        printf("%c", root);
        preorder(tree[root-'A'][0]);
        preorder(tree[root-'A'][1]);
    }
}

void inorder(char root) {
    if (root == '.') return;
    else {
        inorder(tree[root-'A'][0]);
        printf("%c", root);
        inorder(tree[root-'A'][1]);
    }
}

void postorder(char root) {
    if (root == '.') return;
    else {
        postorder(tree[root-'A'][0]);
        postorder(tree[root-'A'][1]);
        printf("%c", root);
    }
}

int main() {

    int n, i;
    char root, left, right;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf(" %c %c %c", &root, &left, &right);
        tree[root-'A'][0] = left;		// [][0] => 왼쪽자식 
        tree[root-'A'][1] = right;		// [][1] => 오른쪽자식을 의미
    }

    preorder('A');
    printf("\n");
    inorder('A');
    printf("\n");
    postorder('A');
    printf("\n");

    return 0;
}

" 트리의 생성은 재귀를 통해 구현하면 쉽다. "

[ CheckPoint ]

• 기본적인 트리의 생성 및 순회 문제였기 때문에 특이사항은 없다.
• 다만, C++로 풀이함에 있어서 C++의 강점인 STL에는 Tree Containner는 없다는 점에서 좀 더 간단한 트리조작 방법이 없는지 아쉬웠다.
• 다른 사람의 참고할 코드에선 배열을 통한 풀이를 했다.
  알파벳 대문자는 26개이고, 노드의 정보가 들어가있지 않음을 의미하는 '.'의 대한 정보만을 이용했다. 26 X 2 2차원 배열이고 0번 인덱스는
  왼쪽자식, 1번 인덱스는 오른쪽자식을 의미, 노드의 정보는 알파벳 순으로 입력됨을 이용했다.