[leetcode강좌]Binary Tree -2

A Traverse a Tree - Introduction
트리순회 - 소개

Pre-order Traversal

Pre-order traversal is to visit the root first. Then traverse the left subtree.
Finally, traverse the right subtree.

루트를 먼저 지나고, 그다음 좌측노드 

마지막으로 우측노드를 지난다. 깊이우선 탐색.

In-order Traversal

In-order traversal is to traverse the left subtree first. 

Then visit the root, traverse the right subtree.

좌측을 먼저 지나고 그다음 root를 방문하고 우측을 순회한다.

Typically, for binary search tree, 

we can retrieve all the data in sorted order using in-order traversal.

일반적으로 이진탐색 트리의 경우,

우리는 모든 데이터를 정렬된 순서로 검색할 수 있다.
대칭순회(Symmetric)라고도 한다.

Post-order Traversal

Post-order traversal is to traverse the left subtree first.

Then traverse the right subtree.

Finally, visit the root.

좌측을 먼저 순회하고 그다음이 우측 마지막으로 root를 방문한다.

It is worth noting that when you delete nodes in a tree,

deletion process will be in post-order.

트리에서 노드를 삭제할때, post-order로 진행하는것에 주목할 해야한다.

That is to say, when you delete a node,
you will delete its left child and its right child before you delete the node itself.

이말은 하나의 노드를 제거할때,

지우고자 하는 노드를 제거하기 전에
좌측과 우측의 자식 노드를 지워야 하는것을 의미한다.

Also, post-order is widely use in mathematical expression.

또한 수학적 표현에서도 널리 사용되어지는데,

It is easier to write a program to parse a post-order expression.
post-order 표현으로 구문분석 프로그램을 작성하는게 더 쉽다.

Here is an example.

You can easily figure out the original expression using the in-order traversal.

in-order 순회를 사용한 원래 표현을 발견할 수 있다.

However, it is not easy for a program to handle this expression
since you have to check the priorities of operations.

그러나 이 표현은 프로그램 입장에서는 부호의 우선순위를 검사해야하는 이유로 쉽지않다.

If you handle this tree in post-order, you can easily handle the expression using a stack.

만약 이를 post-order를 이용한다면 stack을 이용하여 쉽게 표현할 수 있다.

Each time when you meet a operator,

부호를 하나 만날때마다,

you can just pop 2 elements from the stack,
스택에서 2개를 pop을 하고 

calculate the result and push the result back into the stack.

계산한 결과를 다시 스택으로 다시 넣어주면 된다.

Level-order Traversal

Level-order traversal is to traverse the tree level by level.

레벨단위로 순회.

Breath-First search is an algorithm to traverse or search in data structures 

like a tree or a graph.

넓이 우선 탐색은 트리 또는 그래프 데이터 구조에서 순회하는 알고리즘이다.

The algorithm starts with a root node and visit the node itself first.

이 알고리즘은 root노드에서 시작하고 그 자신을 먼저 방문한다.

Then traverse its neighbors,
traverse its second level neighbors,
traverse its third level neighbors, so on and so forth.

그러고나서 자신의 자식들을 순회한다.

그들의 다음레벨의 자식들을 순회하고 이렇게 쭉 진행한다.

When we do breadth-first search in a tree, 

the order of the nodes we visited is in level order.

트리의 넓이 우선 탐색은 레벨 순서로 진행한다.

한글 순회설명