[Coding_Test] Tree 설명

Tree

Tree는 서로 연결된 Node의 계층형 자료구조로써, root와 부모-자식 관계의 subtree로 구성되어 있다.

Tree 관련 개념

• 노드(Node) : 트리는 보통 노드로 구현된다.
• 간선(Edge) : 노드 간의 연결된 선
• 루트 노드(Root) : 트리는 항상 루트에서 시작한다.
• 리프 노드(Leef) : 더 이상 뻗어나갈 수 없는 마지막 노드
• 자식 노드(Child) , 부모 노드(Parent), 형제 노드(Sibling)
• 차수(Degree) : 각 노드가 갖는 자식의 수, 모든 노드의 차수가 n개 이하인 트리를 n진 트리라 한다.
• 조상(ancestor) : 위쪽으로 간선을 따라가면 만나는 모든 노드
• 높이(Height) : 루트 노드에서 가장 멀리 있는 리프 노드까지의 거리, 즉 리프 노드 중에 최대 레벨 값
• 서브트리(Subtree) : 트리의 어떤 노드를 루트로 하고, 그 자손을 구선된 트리를 subtree라 한다.

이진트리 코드및 그림

트리순회 Traversal

트리 순회(Traversal)란 트리 탐색(Search)라고도 불리고, 트리의 각 노드를 방문하는 과정을 말한다. 모든 노드를 한 번씩 방문해야 하므로, 완전 탐색이라고도 불린다. 순회방법으로는 너비우선 탐색의 BFS와 깊이 우선 탐색의 DFS가 있다.

BFS

DFS

전위 순회(Preorder)

중위 준회(inorder)

후위 순회(Postorder)

참조 : 개발남노씨 자료구조