04. tree

간단 지식/Data Structure

04. tree

납작한돌맹이 2020. 12. 6. 05:11

트리는 상위에서 하위 노드로 확장되는 계층구조를 나타내는 비선형 자료구조이다. 아래는 트리 중에서 가장 일반적인 binary tree 구조이다. 이진 트리는 결정트리, 산술식 트리, 탐색 트리 등에 사용된다.

term	description
root	부모 노드가 없는 최초의 노드 ex) A
ancestor	자식 노드가 있는 노드 ex) A, B, C, D
descendent	부모 노드가 있는 노드 ex) B, C, D, E, F, G, H, I
sibling	동일한 부모 노드를 가진 노드 ex) B와 C, D와 E, F와 G, H와 I
subtree	루트를 제거했을 때 생기는 하위 트리, 하위 트리의 집합을 forest라고 부른다.
internal node	루트를 포함하여, 부모 노드와 자식 노드를 둘 다 가진 노드 ex) A, B, C, D
external node (= leaf)	자식 노드가 없는 노드 ex) E, F, G, H, I
level	level 0인 루트를 기준으로 트리의 각 층 번호 또는 트리의 노드 개수
depth	루트에서 노드까지의 길이, level과 값이 동일 또는 트리의 노드 개수
height	height가 0인 leaf를 기준으로 노드까지의 길이 또는 트리의 노드 개수
degree	노드의 자식 노드 개수, 트리의 degree는 degree 중 가장 큰 값

트리는 그 구조가 복잡할 뿐더러 한 노드가 부모와 자식 노드를 갖기 때문에 구현을 위해서는 각 노드가 어떻게 연결되는지를 이해해야한다. 하나의 노드는 element, parent node를 위한 link, child list를 위한 link를 갖는다. 예를 들어 위 트리의 노드 D는 아래와 같은 구조로 자식 노드와 연결되어 있다.

무작정 이진트리를 구현하기보단 일반 트리를 먼저 구현해보자. 일반 트리에 필요한 클래스는 노드 클래스와 트리 클래스이다.

노드 클래스에는 다음과 같은 메소드가 구현되야 한다.

method	description
Object getElement()	노드의 element 리턴
TreeNode getParent()	노드의 parent 노드 리턴
ArrayList getChildren()	노드의 list of child 리턴
int degree()	노드의 child 개수 리턴
void setElement(Object e)	노드의 element를 e로 교체
void setParent(TreeNode p)	노드의 parent 노드를 p로 교체
void setChildren(ArrayList c)	노드의 list of child를 c로 교체

트리 클래스는 노드 클래스의 메소드들을 최대한 활용하여 다음과 같은 메소드를 구현해야한다.

method	description
int size()	트리의 전체 노드 개수 리턴
TreeNode getRoot()	트리의 root 리턴
ArrayList getChildren(TreeNode n)	노드 n의 list of child 리턴
boolean isExternal(TreeNode n)	노드 n이 leaf 노드인지 아닌지 리턴
TreeNode addRoot(Object e)	element가 e인 노드를 root로 추가
TreeNode addNode(Object e)	element가 e인 노드를 root의 child로 추가
TreeNode addChild(TreeNode n, Object e)	노드 n의 자식으로 e값을 갖는 child를 추가
TreeNode addChild(TreeNode n, int i, Object e)	노드 n의 자식 리스트에서 i번째 자리에 e값을 갖는 child 삽입
TreeNode setChild(TreeNode n, int i, Object e)	노드 n의 i번째 자식을 e값을 갖는 child로 변경
TreeNode removeChild(TreeNode n, int i)	노드 n의 자식리스트에서 i번째 child 삭제

메소드 구현은 그렇게 어렵지 않지만 주의해야 할 점을 말하자면 역시 새로운 노드를 생성후 삽입 시 부모 노드와 자식 노드와의 link가 제대로 구현되었는지 확인해야 한다는 점이다. 예를 들어 element e값을 갖는 node를 root의 자식으로 추가하는 코드는 다음과 같다.

    public TreeNode addNode(Object e){
        TreeNode node = new BinNode(e);    //1. e를 값으로 갖는 새로운 노드를 생성한다.
        node.setChildren(new ArrayList());  //2. 새로운 노드도 자식리스트를 갖게 해준다(sub트리 완성)
        node.setParent(this.root);          //3-1. 해당 트리의 부모를 root로 정해준다
        this.root.getChildren().add(node);  //3-2. 루트의 자식으로 해당 트리를 붙여준다
        node.level = 1;
        this.TreeSize++;
        return node;
    }

처음 트리를 공부할 때 1번만 구현해놓고 그 아래 단계는 다 생략해서 항상 nullpointException을 만났다. 지금은 하면 안되는 실수이다. (각 클래스들에 대한 코드는 맨 아래 깃 링크에 저장되어 있다.)

최종적으로 아무 트리를 만들어보면 아래와 같은 결과를 얻을 수 있다.

Tree1 t = new Tree1();
t.addRoot('A');         //node0 = 루트
t.addNode('B');         //node1
t.addNode('C');         //node2
t.addNode('D');         //node3

if(t.isExternal(t.getRoot())){
   System.out.println("level 0짜리 트리입니다.");
   System.out.println("[level 0]: " + t.getRoot().getElement());
}
else{
   TreeNode node1 = (TreeNode)t.getRoot().getChildren().get(0);
   t.addChild(node1, 'E');             //node 1_1
   t.addChild(node1, 'F');             //node 1_2

   TreeNode node2 = (TreeNode) t.getChildren(t.getRoot()).get(1);
   t.addChild(node2, 'G');             //node 2_1

   TreeNode node3 = (TreeNode) t.getChildren(t.getRoot()).get(2);
   t.addChild(node3, 'H');             //node 3_1
   t.addChild(node3, 'I');             //node 3_2

   System.out.println("[level 0]: " + t.getRoot().getElement());

   System.out.print("[level 1]: ");
   for(int i = 0; i<t.getRoot().degree(); i++){
       TreeNode nodeLv1 = (TreeNode) t.getRoot().getChildren().get(i);
       System.out.print(nodeLv1.getElement() + "  ");
   }
   System.out.println();

   System.out.print("[level 2]: ");
   ArrayList level2_1 = node1.getChildren();
   ArrayList level2_2 = node2.getChildren();
   ArrayList level2_3 = node3.getChildren();
   level2_1.addAll(level2_2);
   level2_1.addAll(level2_3);
   for(int i = 0; i<level2_1.size(); i++){
       TreeNode nodeLv2 = (TreeNode) level2_1.get(i);
       System.out.print(nodeLv2.getElement() + "  ");
   }

이진트리를 구현하기 위한 순서는 다음과 같다.

1. 노드 클래스 생성

2. 트리 클래스 생성

3. 바이너리 노드 클래스 생성

4. 바이너리 트리 클래스 생성

이미 일반 트리에서 1번과 2번을 구현했으니 3번 4번에 집중해보자. 이들은 1번과 2번 클래스를 상속받아 구현하기 때문에 크게 어렵지 않다.

자식이 여러개일 수 있는 일반 트리와 달리 자식 리스트에서 차지하는 공간은 0, 1 index이다. 따라서 get, set 메소드가 다음과 같이 약간 변형된다.

public class BinNode extends TreeNode{
    //0은 왼쪽, 1은 오른쪽
    BinNode(){
        super();
    }

    BinNode(Object e){
        super(e);
    }

    //자식 노드 중 왼쪽 노드를 찾자
    public BinNode getLeft(){
        return (BinNode) super.getChildren().get(0);
    }

    //자식 노드 중 오른쪽 노드를 찾자
    public BinNode getRight(){
        return (BinNode) super.getChildren().get(1);
    }

    //왼쪽 자식 노드를 설정하자
    public void setLeft(BinNode n){
        super.getChildren().set(0, n);
    }

    //오른쪽 자식 노드를 설정하자
    public void setRight(BinNode n){
        super.getChildren().set(1, n);
    }
}

바이너리 트리 클래스로 넘어가기 전에 잠시 위에서 언급했던 Tree 클래스의 addRoot 메소드에 있는 new 연산자로 돌아가보자.

    public TreeNode addNode(Object e){
        TreeNode node = new BinNode(e);    <- 이부분
        node.setChildren(new ArrayList()); 
        node.setParent(this.root);          
        this.root.getChildren().add(node);  
        node.level = 1;
        this.TreeSize++;
        return node;
    }

만일 이진 트리는 구현 안하고 일반 트리만 구현하고 싶다면 해당 부분을 new TreeNode(e)로 바꿔줘도 아무 문제가 없다. 그러나 이 상속을 이용해서 이진 트리를 구현하고 싶다면 저렇게 바꿔줘야 한다. 바로 상속 및 생성자 호출 관계가 아래와 같은 구조이기 때문이다. 생성자 호출 ver.1이 new TreeNode(e)이고 ver.2가 new BinNode(e)라고 보면 된다. Tree1을 상속하는 BinTree가 BinNode를 사용하기 위해서는 ver.2가 필수이다!

이제 마지막으로 binary tree class를 구현해야하는데 이 역시 일반 트리에 있는 메소드들을 상속하면 쉽게 구현할 수 있다.

package tree;

import java.util.ArrayList;

public class BinTree extends Tree1{
    BinTree(){
        super();
    }

    BinTree(Object e){
        super(e);
        super.getRoot().getChildren().add(null);    //왼쪽 자식
        super.getRoot().getChildren().add(null);    //오른쪽 자식
   }

    public boolean isEmpty(){
        return super.size() == 0; 
    }

    public boolean isExternal(BinNode n){
        //external
        if(n.getChildren().get(0)==null && n.getChildren().get(1)==null){
            return true;
        }
        //internal
        else{
            return false;
        }
    }

    public BinNode getRoot(){
        return (BinNode)super.getRoot();
    }

    public BinNode getParent(BinNode n){
        return (BinNode)n.getParent();
    }

    public ArrayList getAllChild(BinNode n){
        return super.getChildren(n);
    }

    public BinNode getLeftChild(BinNode n){
        return (BinNode) n.getChildren().get(0);
    }

    public BinNode getRightChild(BinNode n){
        return (BinNode) n.getChildren().get(1);
    }

    public BinNode addRoot(Object e){
        BinNode root = (BinNode)super.addRoot(e);
        super.getRoot().getChildren().add(null);
        super.getRoot().getChildren().add(null);
        return root;
    }

    public BinNode addLeftChild(BinNode n, Object e){
        BinNode left = null;
        if(!(n.getChildren().get(0) != null)){
            left = (BinNode)super.setChild(n,0,e);
            left.getChildren().add(null);
            left.getChildren().add(null);
        }
        return left;
    }

    public BinNode addRightChild(BinNode n, Object e){
        BinNode right = null;
        if(!(n.getChildren().get(1) != null)){
            right = (BinNode)super.setChild(n,1,e);
            right.getChildren().add(null);
            right.getChildren().add(null);
        }
        return right;
    }
}

이진 트리를 생성하고 출력하는 코드는 아래와 같다.

 	BinTree bt = new BinTree();
        bt.addRoot('a');                        //node 0
        bt.addLeftChild(bt.getRoot(), 'b');     //node 1_1
        bt.addRightChild(bt.getRoot(), 'c');    //node 1_2
        bt.addLeftChild(bt.getRoot().getLeft(), 'd');   //node 2_1
        bt.addRightChild(bt.getRoot().getLeft(), 'e');  //node 2_2
        bt.addLeftChild(bt.getRoot().getRight(), 'f');  //node 3_1
        bt.addRightChild(bt.getRoot().getRight(), 'g'); //node 3_2

        if(bt.isExternal(bt.getRoot())){
            System.out.println("level 0짜리 트리입니다.");
            System.out.println("[level 0]: " + bt.getRoot().getElement());
        }
        else{
            BinNode node1 = (BinNode)bt.getRoot().getChildren().get(0);    //node1 = 루트의 왼쪽 자식

            BinNode node2 = (BinNode)bt.getRoot().getChildren().get(1);    //node2 = 루트의 오른쪽 자식

            System.out.println("[level 0]: " + bt.getRoot().getElement());

            System.out.print("[level 1]: ");
            for(int i = 0; i<bt.getRoot().degree(); i++){
                BinNode nodeLv1 = (BinNode) bt.getRoot().getChildren().get(i); 
                System.out.print(nodeLv1.getElement() + "  ");
            }
            System.out.println();

            System.out.print("[level 2]: ");
            ArrayList level2_1 = node1.getChildren();       //루트의 왼쪽 자식의 자식리스트
            ArrayList level2_2 = node2.getChildren();       //루트의 오른쪽 자식의 자식리스트
            level2_1.addAll(level2_2);
            for(int i = 0; i<level2_1.size(); i++){
                BinNode nodeLv2 = (BinNode) level2_1.get(i);
                System.out.print(nodeLv2.getElement() + "  ");
            }
        }

생성한 트리와 실행 결과는 다음과 같다.

(이 글이 도움이 됐다면 광고 한번씩만 클릭 해주시면 감사드립니다, 더 좋은 정보글 작성하도록 노력하겠습니다 :) )

https://github.com/srtktx/DataStructure_java

srtktx/DataStructure_java

자료구조_자바. Contribute to srtktx/DataStructure_java development by creating an account on GitHub.

github.com

저작자표시 비영리 변경금지

'간단 지식 > Data Structure' 카테고리의 다른 글

03. stack, queue (0)	2020.11.21
02. List(배열리스트, 단순연결리스트, 이중연결리스트) (0)	2020.06.26
01. 재귀호출(Recursion)과 반복호출 (0)	2020.06.18

현재글04. tree

뚝딱뚝딱QA

04. tree

'간단 지식 > Data Structure' 카테고리의 다른 글

'간단 지식/Data Structure'의 다른글

티스토리툴바

04. tree

'간단 지식 > Data Structure' 카테고리의 다른 글

'간단 지식/Data Structure'의 다른글

관련글

티스토리툴바