트리 순회

---

트리

자료구조의 한 종류, 컴퓨터 파일의 구조처럼 들어갔을때 거기서 또 나눠지고, 들어가는것을 트리라한다.
부모노드와 자식노드로 나눠지는 자료구조이다.

트리 순회

트리 내부 요소들을 순회하는 방법으로는 대표적으로
전위순회, 중위순회, 후위순회가 있다.

위에그림에서 A부터 전위순회
ABDHIEJCFG, 부모노드 -> 왼쪽자식 -> 오른쪽자식 순서로 순회
A부터 중위순회
HDIBJEAFCG, 왼쪽자식 -> 부모 -> 오른쪽자식
A부터 후위순회
HIDJEBFGCA, 왼쪽자식 -> 오른쪽자식 -> 부모

위에 D H I 로 구성된 Sub-tree로 예시를 들면
전위 : DHI, 중위 : HDI, 후위 : HID 이다.

---

배열 구현방법

left,right로 구성된 노드구조를 배열로 만든다.

typedef struct node {
	char left;
	char right;
} NODE ;

NODE arr[MAX];

---

실제 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <set>

using namespace std;
#define endl "\n"

#define MAX 26+1

typedef struct node {
	char left;
	char right;
} NODE ;

NODE arr[MAX];
int N;

void pre(char root) {
	if (root =='.')
	{
		return;
	}
	cout << root;
	pre(arr[root-'A'].left);
	pre(arr[root-'A'].right);
}
void in(char root) {
	if (root=='.')
	{
		return;
	}
	in(arr[root-'A'].left);
	cout << root;
	in(arr[root-'A'].right);
}
void post(char root) {
	if (root=='.')
	{
		return;
	}
	post(arr[root-'A'].left);
	post(arr[root-'A'].right);
	cout << root;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		char a, b, c;
		cin >> a >> b >> c;
        
		arr[a-'A'].left = b;
		arr[a-'A'].right = c;
	}

	pre('A');
	cout << endl;
	in('A');
	cout << endl;
	post('A');
}

---

배열 인덱스에 -'A'를 해야하는 이유

우리는 배열을 선언할때 arr[MAX] MAX=27이므로, 27개의 Node를 선언했다.
하지만 입력을 문자 알파벳으로 받게되면 알파벳 'A'의 아스키코드값이 65이므로
a='A' 일때 arr[a]는 arr[65]와 같다. 즉 선언한 크기를 넘어버리는것
지금 당장은 오류가 나지 않지만, 버그의 원인이 되고, 오버플로를 이르킬수 있으므로
반드시 피해야한다.

---

참고

https://miiinnn23.tistory.com/55
https://monsieursongsong.tistory.com/6