Tree

1. Tree

트리 구조는 비선형 구조로 데이터가 계층적으로 구성되어 있다.

트리는 노드들과 노드를 연결하는 edge(간선)들로 이루어진 자료 구조로 하나의 루트로드를 가지고 루트 노드는 0개 이상의 자식 노드를 가지고 그 자식 노드 또한 0개 이상의 자식 노드를 가지는 구조가 반복된다. 

Tree 구조

• Root Node : 트리 구조에서 최상위에 존재하는 노드 (A)
• Node : 트리의 구성요소에 해당하는 요소 (A, B, C, D, E, F, G, H, I)
• Edge : 노드와 노드를 연결하는 연결선
• Terminal Node(Leaf Node) : 밑으로 다른 노드가 연결되어 있지 않은 노드 (H, I, F, G)
• Sub -Tree : 큰 트리에 속하는 작은 트리
• Level : 트리에서 각 층별로 숫자를 매긴다.
• Height : 트리의 최고 레벨 (3) 

트리의 종류 

• 이진트리 : 루트 노드를 중심으로 둘로 나뉘는 두 개의서브트리도 이진 트리이고 , 그 서브 트리의 모든 서브 트리도 이진트리이다.
  
• 포화 이진 트리(Full Binary Tree) : 모든 레벨이 꽉 찬 이진 트리
• 완전 이진 트리(Complete Binart Tree) : 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 이진 트리

위의 그림은 이진트리의 구조이다. 이진 트리 구조는 하나의 노드에 왼쪽, 오른쪽 각각의 자식의 정보를 담는 변수와 자신의 데이터를 가지고 있다. 

 

Psuedo Code

값을 추가할 때

1. 자신의 값과 자식노드의 값을 담을 객체를 생성한다.
2. 입력된 값을 객체의 값과 비교하여 작으면 왼쪽으로 크면 오른쪽으로 에 할당하는 함수를 만든다.
3. Leaf노드 까지 함수를 돌려주도록 한다.

값을 삭제할 때

1. 삭제할 값을 찾는 포문을 만들어 준다.
2. 포문 내에 이프문을 통해 찾는 값이면 삭제하고 아니면 다음 값으로 넘어가게 만들어 준다.