[자료구조] 2-3 tree 자바로 구현하기

목차

Node.java - 기본적인 노드 자료구조
Tree23.java - 노드의 조합으로 트리 구성
Tree23Test.java - main()함수가 들어있는 구동파일

본문내용

# 클래스 구성도
1. Node.class
2. Tree23.class
3. Tree23Test.class
Node.class는 Tree(Tree23)을 구성하는 각 노드에 대한 자료구조이다.
Tree23.class은 노드로 구성된 트리에 대한 자료구조이며,
Tree23Test.class는 실제 트리를 생성하고 화면에 출력하는 실행화일이다.
각 클래스별로 내용을 살펴본다.

# Tree23Test.class
test클래스.
1. 트리를 구성할 리프갯수 n을 입력받는다.
2. 1~99 사이의 값을 중복을 피해 n개 생성한다.
3. 트리를 새로 생성하고 n개의 숫자를 입력한다.
4. 트리정보를 출력한다.

# Tree23.class
두개의 숫자를 받아 트리가 생성되면
이후로는 임의의 숫자를 입력받아 트리에 추가한다.
최초로 insert()가 불리면
먼저 입력값이 위치할 노드를 찾아(locate->p)
입력값을 리프노드로 감싼 다음(createLeaf->q)
그 자리에 붙인다(attach).
attach할때는 우선 q가 p의 왼쪽 노드라면 위치를 swap한 뒤에
다음과같은 경우로 나눠서 처리한다.
1. p가 root일때
2. p의 부모의 sibling이 없을떄
a. p가 부모의 left 자식일때
b. p가 부모의 middle 자식일때
3. p의 부모의 sibling이 있을때
a. p가 부모의 left 자식일때
b. p가 부모의 middle 자식일때
c. p가 부모의 right 자식일때
1의 경우는 새로운 root노드가 생겨서 p,q의 부모노드가 된다.
2의 경우는 부모노드의 분할이 필요없지만,
3의 경우는 부모노드의 분할이 생긴다.

# Node.class
노드의 자료구조.
하나의 부모노드와 세개의 자식노드를 가지며
세개의 키값을 가진다. 키값은 숫자가 아닌 객체로 구성하였다.
화면출력을 보기좋게하기 위해 toString()을 오버라이딩하였다.

참고자료

· 없음