앞서 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 |