Traversal

[자료구조 ] Tree(트리) 필수 개념, 트리 순회

트리란? 트리는 Node 로 이루어진 자료구조 이다. 하지만 Node로 이루어져있다고 다 트리라고 부를 수 있을까? 아니다. 트리는 그래프와 구별되며 다음과 같은 특징을 가지고 있다. 트리는 최소 연결 트리라고 불린다. 두 Node 사이에 반드시 1가지의 경로만을 가진다. (ex, A에서 F로 가는 경로는 한가지이다.) 트리는 오직 한개의 Root Node를 가진다. 트리에는 loop, circuit, self-loop가 존재하지 않는다. (사이클이 없는 방향 그래프(DAG)) 트리의 순회는 Pre-Order, Inorder, Post-order로 이루어진다. Edge는 항상 Node의 개수 - 1 의 개수이다. 이진트리(Binary Tree)에 대해서 우리가 보통 BT 라고 부르는 Binary Tree..