24.01_Tree_22.09.23

Tree

>의미

: 하나의 뿌리로부터 가지가 사방으로 뻗은 형태의 자료구조

: 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조

: 나무를 거꾸로 뒤집어놓은 듯한 형태

: 비선형 구조(일직선의 구조가 아님)

: 단방향 그래프

>특징

• 1. Node

: 트리 구조에 속하는 각각의 데이터

• 1-1. Edge

: 각각의 node의 연결통로

• 2. Root

: 트리 구조의 시작점이 되는 node

• 3. Parent - Child

: 두 개의 노드가 상하 계층으로 연결된 경우 부모/자식 관계가 됨.

• 3-1. Parent Node

: 부모/자식 관계에서 상위 node를 의미

• 3-2. Child Node

: 부모/자식 관계에서 하위 node를 의미

• 4. Sibling

: 같은 상위 node에서 갈라진 별개의 node를 의미

• 5. Leaf Node

: 자식 node가 없는 트리 구조의 말단 부분의 node를 의미

: 사실상 트리 구조의 끝 지점, 최하단 부분을 의미함.

• 6. Depth

: Root로부터의 거리(edge 갯수)

• 7. Level

: 같은 depth를 갖는 node끼리 묶은 것
: Sibling은 같은 level의 node이다.

• 8. Height

: Leaf node를 기준으로 Root까지의 거리(edge 갯수)를 height로 표현.

: 다른 node간 길이를 height을 이용하여 표현하기도 함.

• 9. Sub Tree

: 트리 구조  내부에 존재하는 또 다른 작은 트리 구조들을 의미.

>Tree의 실사용 예시

1. 컴퓨터 디렉토리 구조  : 여러 폴더가 있고, 폴더 내부에 폴더가 있음.

2. 조직도

3. 토너먼트 대진표

>트리 구조 구현 클래스 작성(예시. Node)

• 필드1

: 현재 노드에 저장될 값을 할당(자료형에 따른 다른 트리 사용예시. String)

• 필드2

: 자식 노드를 저장할 수 있는 list(ArrayList)

: 리스트의 자료형은 Node(트리 구조를 구현한 클래스형)

: 따라서, 자식 노드 리스트에는 Node들의 주소값들이 할당된다.

• 생성자1

: 인자 없는 경우, 필드1, 필드2 모두 null 할당

• 생성자2

: 필드1의 값을 지정한 상태로 인스턴스 생성

• setter_필드1

: 필드1의 값을 지정하는 메서드

• getter_필드1

: 필드1의 값을 반환하는 메서드

• getter_필드2

: 필드2의 값을 반환하는 메서드

• addChildNode

: 자식 노드를 추가하는 메서드

: 매개변수로 Node 주소값을 받음

: 필드2가 비었을 경우, 새로운 리스트를 생성 후 인자 정보를 필드2에 할당

: 필드2가 있을 경우, 인자 정보를 필드2에 할당

• removeChildNode

: 자식 노드를 제거하는 메서드

: 매개변수로 Node 주소값을 받음

: 제공받은 Node의 필드1을 변수로 저장(data)

: 조건문을 통해 자식 노드가 있다면 아래 작업 실행

: 메서드를 호출한 Node의 자식 노드를 전부 순회하며 data와 일치하는 값 확인, 확인되면 해당 자식 노드는 리스트에서 삭

제(반복문 사용)

: 조건문 통해 자식 노드의 자식 노드가 있다면 아래 작업 실행

: 자식노드들을 순회하며, 순회하는 노드에서 removeChildNode 메서드 호출(재귀 함수)

=>결과적으론 removeChildNode 메서드를 호출한 노드의 모든 자식 노드에서 인자로 제공하는 node와 일치하는 노드 제

거

• contains

: 트리 구조 내에 해당하는 값을 검색하기 위한 메서드

: 인자로 제공된 값과 일치하는 값의 유무를 확인 후, boolean 값으로 반환함.

: 메서드를 호출한 노드의 값과 일치 여부부터 파악

: 해당 노드의 자식노드를 순회하며 자식 노드에서 모두 contains를 호출하며 파악(재귀 함수)