[은행 필기대비 자료구조-02] 이진 트리 순회 경로

1. 트리(Tree)

Degree(차수) : 루트 노드로부터 퍼저나간 간선안의 노드수

 

Leaf : Node의 차수가 0인 Node or 자식 없는 Node

 

Root Node : 제일 최상위 노드

2.전위순회(Pre-order Traversal)

==> ROOT-좌측 - 우측

3. 중위순회(IN-order Traversal)

==>좌측 - Root - 우측

4.  후위순회(Post-order Traversal)

==> 좌측 - 우측 - ROOT

 

 

5. 중위식(Infix) ==> 후위식(Postfix)

EX-01)  A / B * (C + D) + E

 

==> (AB /) * ( CD +) + E

==> (AB /)(CD+*) + E

==> (AB /)(CD+*)(E+)

 

==> 곱셈, 나눗셈 먼저 뒤로 옮긴다.

 

EX-02) A = (B-C) * D +E

 

 ==> A = {(BC-)*D} + E

 

==> A= {(BC-D*) + E}

 

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

 

==> BC-D*E+A=

 

5. 후위식(Postfix) ==> 중위식(Infix)

ABC- /DEF+ * +

 

==> (ABC-/)(DEF+*+)

==>{A/ (BC-)}+(DEF+*)

==> {A/(B-C)} + {D* (EF+) }

==> A/(B-C)+D*(E+F)