[자료구조] 트리(Tree)

트리(Tree)

 

- 트리는 비선형 구조이다. 비선형 구조란 선형구조(예: 큐(Queue), 스택(Stack))과 다르게 데이터가 계층적(혹은 망)으로 구성되어있다. 

- 컴퓨터의 디렉터리 구조가 트리의 대표적인 예라고 볼 수 있는데, 이렇듯 계층적인 구조를 갖는 것이 트리라 할 수 있다. 

- 트리 용어

 

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

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

 

 

- 트리의 구현에는 배열을 이용하는 것과 연결리스트를 이용하는 것이 있다. 배열을 이용한 트리 구현은 힙(Heap)이라는 자료구조를 사용한다. 연결리스트를 이용하는 트리 구현은 하나의 노드에 왼쪽, 오른쪽에 자식의 정보를 담고 있다. 

 

 

[출처]monsieursongsong.tistory.com/6