자료구조의 한 종류, 컴퓨터 파일의 구조처럼 들어갔을때 거기서 또 나눠지고, 들어가는것을 트리라한다.
부모노드와 자식노드로 나눠지는 자료구조이다.
트리 내부 요소들을 순회하는 방법으로는 대표적으로
전위순회, 중위순회, 후위순회가 있다.
위에그림에서 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');
}
우리는 배열을 선언할때 arr[MAX] MAX=27이므로, 27개의 Node를 선언했다.
하지만 입력을 문자 알파벳으로 받게되면 알파벳 'A'의 아스키코드값이 65이므로
a='A' 일때 arr[a]는 arr[65]와 같다. 즉 선언한 크기를 넘어버리는것
지금 당장은 오류가 나지 않지만, 버그의 원인이 되고, 오버플로를 이르킬수 있으므로
반드시 피해야한다.
https://miiinnn23.tistory.com/55
https://monsieursongsong.tistory.com/6