Tree 자료형 구현(JAVA)

Tree 구조
코드
리뷰
깃허브

Tree 구조

트리 구조는 비선형 구조로 계층구조이다.
맨 위를 루트로 잡고, 계층별로 부모, 자식이 나뉘어지고 부모는 자식 노드들을 가진다.
부모는 자식노드들에 대한 참조값을 가질 수 있고, 자식은 본인의 부모에 대한 참조값을 가질 수 있다.
트리구조를 가지고 활용한 알고리즘 들에는 DFS BFS 이진탐색 완전 이진 트리(힙) 세그먼트 트리 등이 있다.

코드

package Structure;

import Utils.ArrayUtils;

public class Tree <T>{
    private T data;
    private Tree<T> parents;
    private Tree<T>[] childrens;
    private int depth;

    public Tree (T data, int startDepth, Tree<T> parents) {
        this.parents = parents;
        this.data = data;
        this.childrens = new Tree[0];
        this.depth = startDepth;
    }
    public Tree (T data, int startDepth) {
        this.data = data;
        this.childrens = new Tree[0];
        this.depth = startDepth;
    }
    public void addChildren (T data) {
        this.childrens = ArrayUtils.arrExtends(this.childrens, this.childrens.length+1);
        this.childrens[this.childrens.length-1] = new Tree<T>(data, this.depth+1, this);
    }
    public static <T> void addChildren (Tree<T> node,T data) {
        node.childrens = ArrayUtils.arrExtends(node.childrens, node.childrens.length+1);
        node.childrens[node.childrens.length-1] = new Tree<T>(data, node.depth+1, node);
    }
}

Tree 오버로딩

	public Tree (T data, int startDepth, Tree<T> parents) {
        this.parents = parents;
        this.data = data;
        this.childrens = new Tree[0];
        this.depth = startDepth;
    }
    public Tree (T data, int startDepth) {
        this.data = data;
        this.childrens = new Tree[0];
        this.depth = startDepth;
    }

트리를 생성할때 참조시킬 부모노드가 존재하면 parents인자를 넘기고 참조시킬 부모노드가 없다면 그냥 값과 depth만 넘기도록 만들어봤다.

addChildren 오버로딩

	public void addChildren (T data) {
        this.childrens = ArrayUtils.arrExtends(this.childrens, this.childrens.length+1);
        this.childrens[this.childrens.length-1] = new Tree<T>(data, this.depth+1, this);
    }
    public static <T> void addChildren (Tree<T> node,T data) {
        node.childrens = ArrayUtils.arrExtends(node.childrens, node.childrens.length+1);
        node.childrens[node.childrens.length-1] = new Tree<T>(data, node.depth+1, node);
    }

트리에 자식을 추가할때 외부에서 트리를 생성시켜서 그 트리에 자식을 추가 할 경우 따로 부모노드에 대한 참조값이 필요가 없지만, 생성된 트리의 직계자식이 아닌 그 이상 밑으로 내려갈 경우 부모노드의 참조값이 필요함으로 인자값으로 부모노드값을 넣어봤다.
위에서 필요한 부모노드값을 찾기 위해서 DFS 방법으로 부모노드를 찾도록 만들었는데 그 부분은 따로 정리해서 올릴예정이다.

리뷰

addChildren메소드의 경우 스태틱 메소드와, 인스턴스 메소드로 구분지어서 만들어봤는데, 외부에서 사용할 경우 조금 어색했던 것 같다.

깃허브

깃허브