트리의 순회(inorder, preorder, postorder, levelorder traversal)

앞서 inorder preorder postorder 방식은 다루었었다.

이번에는 스택에서 다룬 postfix expression을 한번 트리로 구현해보자.

 

 

input: AB/C*D*E+

 

 

 

원리는 먼저  연산자가 나올때까지 operand를 스택에 넣고, 연산자가 나온다면 pop해서 오른쪽자식, 왼쪽자식에 하나씩 넣어준다. 그러면 그 부모노드가 또 스택에 들어가 다음번 연산자의 자식으로 되기때문에 inorder traversal을 통해 infix notation을 얻을수 있다.

 

추가로 구현한 leverOrder traversal