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

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

 

 

input: AB/C*D*E+

 

 

 

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

 

추가로 구현한 leverOrder traversal

 

 

'Data Structure' 카테고리의 다른 글

트리 - Max heap  (0) 2020.06.14
명제식 이진트리  (2) 2020.06.14
트리(Tree)  (0) 2020.06.14
요셉의문제(Circular Linked List)  (0) 2020.06.14
연결리스트(Linked List)  (0) 2020.06.10