자료구조 | Binary Tree

21/08/19

개강 D - 11
무 져 웡 ㅠ

15. Binary tree traversal

이진 트리 순회

L: moving left
V: visiting the node
R: moving right

Inorder traversal(LVR)

preorder(ptr->leftChild); -> L
printf("%c", ptr->data); -> V
preorder(ptr->rightChild)l -> R

Recursion inorder traversal

재귀 형태로 함수 호출
leftchild가 null이 될 때까지 inorder를 호출하고 가장 마지막으로 호출된 inorder부터 하나씩 실행시킴

(42 피신 때 독하게 배운 재귀가 이렇게 쓰이네... 후...)

• 재귀 => 직관적이어서 좋지만 function stack을 쌓으면서 가기 때문에 메모리 낭비 존재

Iterative inorder traversal

void iterInorder(treePointer node)
{
int top = -1; //스택 초기화
treePointer stack[MAX_STACK_SIZE];
for (;;) {
	for (; node; node = node->leftChild)
      		push(node); //스택에 추가 
                //-> leftChild가 더이상 갈 때가 없을 때까지 push
           node = pop(); //스택으로부터 삭제
           //-> 
           if (!node) break; //스택 비우기
           printf("%c", node->data);
           node = node->rightChild;
	}
}

노드의 데이터를 스택에 넣지 않고 노드의 주소값들을 스택에 넣고 간 이유?

현재 LVR 순으로 데이터 값만 저장하지 않고 출력한뒤 left, right 로 이동해야하는 상황이기 때문에 push할 때 주소값을 보내줘야 노드 자체의 데이터와 더불어 노드의 LeftChild, RightChild 값도 알고 있어야하기 때문에 주소값을 저장해야한다.

Preorder Traversal (VLR)

printf("%c", ptr->data); -> V
preorder(ptr->leftChild); -> L
preorder(ptr->rightChild)l -> R

Postorder Traversal (LRV)

preorder(ptr->leftChild); -> L
preorder(ptr->rightChild)l -> R
printf("%c", ptr->data); -> V

###Level - order Traversal ("Breath-First")

트리를 단계적으로 살피고 싶을 때 사용

• 이렇게 순차적으로 레벨을 내려가면서 맨 왼쪽에 있는 애 부터 출력하기를 원할 때

포인터가 가리키는 데이터 값 출력

자신을 찍고 lr 찍고, 그 후 같은 레벨의 그 다음의 데이터로 이동해야한다는게 특징

맨 왼쪽 부터 차례대로 스캐닝하면서 출력

*어떤 상황에서 queue를 사용하고 어떤 상황에서 stack을 사용해야하는지 이해하는게 중요하다