[자료구조] 트리

트리의 개념

트리란 그래프의 한 종류로 여러 서로다른 노드들과 그 노드들을 한방향으로 이어놓은 자료구조이다.

• 노드(Node) : 데이터를 저장해놓은 하나의 공간, 값(Value)와 자식정보를 가진다.
• 루트노드(Root Node) : 트리의 가장 최상단에 위치한 노드
• 리프노드(Leaf Node) : 트리의 가장 최하단에 위치한 노드
• 부모노드(Parent Node) : 트리구조에서 자식노드를 가진 노드를 말하며, 어떤 노드에 대한 상대적인 위치이다.
• 자식노드(Child Node) : 부모노드의 자식노드
• 형제노드(Sibling Node) : 동일한 부모노드를 가진 노드들

트리순회(Tree Traversal)

트리순회란? 트리의 모든 노드들을 거쳐가는 방법이다.

• 전위순회(Preorder Traversal): Root -> Left -> Right
• 중위순회(Inorder Traversal): Left -> Root -> Right
• 후위순회(Postorder Traversal): Left -> Right -> Root
• 레벨순회(Level Traversal): 레벨순서대로

전위순회(Preorder Traversal)

중위순회(Inorder Traversal)

후위순회(Postorder Traversal)