Tree Traversal & Parsing

tree에는 단순한 1차원 데이터가 아닌 복잡한 구조를 넣을 수도 있음 ex)수식

Traversal

트리 전체를 돌아다니면서 전체 구조를 파악함

• Traversal means to visit all nodes in some order
• visit does not mean being at a node 방문한다는 것은 노드에 있다는 것이 아니라
• visit means doing something at a node 어떤 작업을 한다는 것

< DFS >

Traverse(Node *D){
	if(D == NULL) return;
	Visit(D);
	Traverse(D->Left);
	Visit(D);
	Traverse(D->Right);
	Visit(D);
}

 

노드 D에는 세번 위치함 → 맨 처음 방문 / 왼쪽에 갔다 오는 경우 / 오른쪽에 갔다가 오는 경우

 

Preorder

루트 → 왼쪽 서브트리 → 오른쪽 서브트리

Inorder

왼쪽 서브트리 → 루트 → 오른쪽 서브트리

Postorder

왼쪽 서브트리 → 오른쪽 서브트리 → 루트

 

Q. 같은 바이너리 트리로부터 다른 두개의 sequences가 preorder & inorder로 만들어질 수 있는가?

A. 루트를 찾은 뒤, 왼쪽 서브 트리, 오른쪽 서브트리의 집합을 맞춰나가는 방식으로 반복한다

 

복잡한 수식을 트리 구조로 나타낸 것

컴파일러에서 식의 구조를 파악하여 기계어를 만듦 → 주어진 식을 트리로 만들면 구조를 파악한 것

 infix : 원래 우리가 쓰는 식의 구조 - 우선순위에 따라 적당한 괄호를 추가해줌

postfix : 식의 다른 표현 - 컴퓨터의 식의 표현 (순서대로 계산하면 됨) _숫자_ _숫자_ _연산자_ 순서로 진행

ex) 63/와 64-를 맨 처음 할 수 있고, 그 이후는 저 값이 나온 이후에 두 자리씩 계산할 수 있음

 

Parsing (for Code Generation)

Parsing Algorithm - No Parentheses (괄호 없음)

[ Assumptions ] 

• Operators have priority 연산자 우선순위가 존재함
• Operator on the left has highter priority 연산자의 우선순위가 같으면 왼쪽 우선순위가 더 높다

while reading formula from start to end //식을 왼쪽부터 오른쪽으로 읽음
	If operand then make a node and push to 2 stack //피연산자면 노드를 만들고 두번째 스택에 넣음
	If operator then compare priority whith top of 1 stack 	//연산자면 첫번재 스택의 탑과 우선순위 비교
		Case input is hight : push to 1 stack //input의 우선순위가 더 높으면 1스택에 넣음
		Case stack top is higher or same : //stack top의 우선순위가 더 높거나 같으면 (왼쪽부터)
			pop 2 from 2 stack //두번째 스택에서 피연산자 두개를 뽑음
			make a node with stack to operator and 2 popped nodes (as children)
			push operator node to 2 stack
			//연산자와 뽑은 두 개의 피연산자를 계산하여 다시 2스택에 넣음
			//트리를 만들 때 연산자는 부모노드, 피연산자는 자식 노드로 만듦
			Repeat comparison //반복
		Case $ and $ meet : finish //어떠한 식이 있으면 앞 뒤에 $존재 (low priority) - 연산자로 생각

What about Parenthesis 괄호

Parentheses have 2 priorties 괄호는 우선순위가 2가지가 있음

• Opening Parenthesis has highest priority when on input 여는 괄호는 입력에 있을 때 가장 높은 priority
• Opening parenthesis has has lowest priority when on stack 여는 괄호는 스택에 있을 때 가장 낮은 priority
• Closing Parenthesis has lowest priority and never goes into Stack 닫는 괄호는 스택에 들어가지 않고 여는 괄호랑 만나 사라짐

ex)

....+ ( ... ) .. :  ()연산을 하기 전에 +를 할 수 없으므로 () 연산 먼저 해야함

...(... + ...) .. : + 연산을 해야 괄호를 닫을 수 있기 때문에 ()보다 +연산을 먼저 해야함