[자료구조]Tree

트리는 노드로 이루어진 재귀적 자료 구조이다

 이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조이다

트리는 하나의 루트 노드를 갖는다.

노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다

노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가진다

트리에는 사이클(cycle)이 존재할 수 없다.
노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다.
각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다.
각 노드는 어떤 자료형으로도 표현 가능하다.

 

 

Node	LinkedList와 비슷하게 tree에도 node가 존재한다. 각 node는 데이터를 포함하고 있다
Parent(부모)  Child(자식)	부모노드는 다수의 자식 노드를 가지고 있을수 있다  하지만 자식 노드는 하나의 부모만 가진다
루트 노드(Root)	트리에 가장 상단에 위치한 노트 이다 부모가 없고 트리는 하나의 루트 노드만을 가진다
단말 노드(Leaf)	자식이없는 노드입니다. 트리에 가장 끝부분에 위치한다
노드의 크기(Size)	자신을 포함한 자식 노드의 수	Size = 6
노드의 깊이(Depth)	루트에서 특정노드 까지 도달하는데 거쳐야하는 간선의 수	B의 깊이 1 E의 깊이 2
노드의 레벨(Level)	트리에 특정 깊이를 가진 노드의 집합	A의 레벨 1 B와 C의 레벨 2 D E F 레벨 3
노드의 차수(Degree)	각 노드가 가진 가지의 수	B의 차수: 3 A의 차수 2
트리의 차수	트리의 최대 차수	B가 가장 많은 가지수를 가지고있기 때문에 트리의 차수는 3
트리의 높이	루트 높이에서 가장 깊이있는 노드의 깊이

이진 트리(Binary tree)

자식 노드가 최대 두 개인 노드들로 구성된 트리

두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다

이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다

• 포화 이진 트리(full binary tree) : 각 레벨에 노드가 꽉 차 있는 이진 트리로, 각 노드에 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙일 수 있다. 부여된 번호는 항상 일정하다.
• 완전 이진 트리(complete binary tree) : 높이가 k일 때, 레벨 1부터 k-1까지는 노드가 채워져 있고, 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리로, 마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만, 중간에 빈 곳이 있으면 안 된다.
• 정 이진 트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 가진다
• 기타 이진 트리

 

 

 

이진 탐색 트리(Binary Search Tree)

 

이진 탐색 트리란 이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 이진트리를 말한다

이진 탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제가 가능하다.

• 각 노드에 중복되지 않는 키(Key)가 있다
• 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다
• 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다
• 좌우 서브트리도 모두 이진 탐색 트리여야 한다

이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다

 

 

1. 중위 순회: 루트 노드의 왼쪽 자식 노드를 먼저 방문 후에 루트 노드를 중간에 방문하는 방식

2. 후위 순회: 루트 노드의 왼쪽 자식, 오른쪽 자식을 방문 후 루트 노드를 마지막에 방문하는 방식

3. 전위 순회: 루트 노드를 먼저 방문 후 왼쪽 자식, 오른쪽 자식을 방문하는 방식