[ 정보처리기사 ] 2020 CBT 개념 공부 - 트리 + 알고리즘 식 표기법

이분들 내용 보고 정리 :
https://computer-choco.tistory.com/439
https://simuing.tistory.com/entry/2021-%EC%A0%95%EB%B3%B4%EC%B2%98%EB%A6%AC%EA%B8%B0%EC%82%AC-%ED%95%84%EA%B8%B0%EC%9A%94%EC%95%BD-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C%EB%B0%A9%EB%B2%95-%EC%B0%A8%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0https://devinus.tistory.com/20


트리

- 비선형구조의 사이클이 없는 계층형 그래프 

 

- 노드 NODE : 루트 노드 - 가장 맨 꼭대기 & 터미널 노드 - 가지가 뻗어 가장 아래 달린 노드
ㄴ 트리 노드 = 가장 마지막에 뻗은 노드

- 차수 DEGREE : 특정 노드에 연결된 자식의 수
ㄴ 트리 차수 = 가장 많이 연결된 자식이 있는 노드 가지수 기준

트리 차수는 C와 E가 두개씩이므로 2개 트리 노드는 DGHF로 4개

트리 순회방법

- 전위 순회 Preorder : 뿌리 먼저 쭉~ 방문 , 좌 중 우 차수 없으면 줄 별 인식 | ROOT > 좌 > 우
- 중위 순회 Inorder: 왼쪽 트리 모두 방문 후 뿌리 방문 | 좌 > ROOT > 우
- 후위 순회 Postorder : 하위 트리 모두 방문후 뿌리 방문, 같은 세로열일때 주의 | 좌 > 우 > ROOT

드디어 이해한 원리 :

 

더욱 다양한 사례 : https://simuing.tistory.com/entry/2021-%EC%A0%95%EB%B3%B4%EC%B2%98%EB%A6%AC%EA%B8%B0%EC%82%AC-%ED%95%84%EA%B8%B0%EC%9A%94%EC%95%BD-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C%EB%B0%A9%EB%B2%95-%EC%B0%A8%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0

 

알고리즘 순회방법

- 전위식(PRE) : 연산자가 앞에 

- 중위식(IN) : 연산자가 안에 

- 후위식(POST) : 연산자가 뒤에

 

1) 연산자 원래 용도에 맞게 따라 괄호로 묶는다

2) 연산자를 순회법에 따라 괄호를 기준으로 배치한다.

3) 괄호를 제거한다

 

1. 전위를 중위식으로 바꾸기

3+2+4*5+3/1

=> (3+(2+(4*5)+(3/1)) : 연산자가 앞에

=> +(+3(+2*(45)))/(31))

=> ++3+2*45/31

 

2. 중위를 후위식으로 바꾸기

3+2+4*5+3/1

=> ((3+2)+(4*5))+(3/1) : 연산자가 안에

=> ((32)+(45)*)+(31)/)+

=> 3245*31/+

 

3. 후위를 중위식으로 바꾸기

3245*++31/+

=> ((3(2(45)*)+)+(31)/+

=> (3+(2+(4*5)))+(3/1))

=> 3+(2+(4*5)))+(3/1)

 

4. 전위식을 후위식으로 바꾸기

-/*A+BCDE

=> (-(/(*A(+BC)D)E)

=> ((A(BC)+)*D/E)-

=> ABC+*D/E-

 

 

무방향 그래프 최대 간선수 = n(n-1)/2

 

출처 : https://simsim231.tistory.com/54