[자료구조 알고리즘] 트리, 이진트리, 이진트리 순회

[트리란]

1) 비선형자로구조 : 데이터의 관계를 나타내는 것에 비중이 큼

2) 뿌리에서 가지를 뻗어나가는 형태의 자료구조 : 계층을 나타냄

[트리 관련 개념]

1) 노드 : 트리 구성요소

2) 엣지 : 노드와 노드를 연결하는 선

3) 루트노드 : 트리구조에서의 최상위노드(서브트리도 포함, 어떤 트리가 문제해결의 중심이냐에 따라)

4) 단말노드 : 아래로 다른 노드와의 연결없는 노드

5) 내부노드 : 단말노드를 제외한 노드, 관계가 있는 노드

6) 레벨 : 같은 높이에 있는 노드들

7) 높이 : 루트노드(0)를 기준으로 가지가 총 몇단계에 걸쳐 뻗어져있는가?, 최대 레벨은 높이와 같음

8) 서브트리 : 루트노드에서 뻗어져나온 노트들이 또 뻗었을 때 그때 트리 형태

9) 형제관계 : 같은 레벨의 노드

10) 부모관계

11) 포화이진트리 : 모든 레벨에 꽉찬 이진트리

12) 완전이진트리 : 차곡차곡 쌓여진 이진트리(포화이진트리X), 아래에서 위, 왼쪽에서 오른쪽

[이진트리란]

1) 루트노드가 2개의 노드를 가짐 : 상하위 관계

2) 서브노드의 서브노드는 이진트리 구조 : 2개 노드

- 0~1개 가질 떄에도 이진트리 : 3개 이상을 가지는 순간 이진트리X, 공노드라고 함

[이진트리 만들기 - 정확히는 이진트리를 구성할 수 있는 도구]

1) 배열 : 접근이 용이하다는 장점

2) 연결리스트

- 트리 관계 표현을 쉽게할 수 있다는 장점

- 루트 노드 1개로 전체 트리를 가져올 수 있다는 장점

- 주로 연결리스트를 사용하지만 배열을 사용할 때가 있음

[연결리스트 기반 이진트리]

1) BTree(BTreeNode) 객체타입 1개를 가지고 이진트리 표현

- 스택, 큐와 같이 노드 / 자료구조 기능 따로 2개의 타입을 만들었다면 이진트리는 BTreeNode가 두가지 역할 모두함

- 노드와 노드 간의 관계를 가짐 : 상하위

2) 선형자료구조와 달리 비선형자료구조는 데이터 관계 표현이 주목적

- 선형자료구조가 저장, 변경, 삭제 기능이 우선시 되었다면

- 비선형자료구조는 데이터 간의 관계 표현을 우선시

3) 루트노드 주소값만 가지고 있으면 나머지 노드는 연결되어있으므로 딸려다님

- 노드를 단순로드로 보지않고 이진트리의 루트노드로

[이진트리 순회]

1) 순회 종류 : 전위, 후위, 중위가 있는데 루트노드를 언제 순회하느냐에 따라 차이, 횡은 왼쪽 -> 오른쪽

2) 루트노드 관점에서 순회코드 짜기

3) 재귀 : 패턴 + 언제 끝(탈출조건 == 루트노드)


[이진트리 관계 맺기 + 순회 코드]
- 깃헙 레포 :  https://github.com/imjinbro/datastructure/tree/master/src/main/java/com/jinbro/source/tree/binarytree

import java.util.NoSuchElementException;

public class BTreeTest {
    public static void main(String[] args) {

        try{
            BTreeNode bt1 = new BTreeNode(1);
            BTreeNode bt2 = new BTreeNode(2);
            BTreeNode bt3 = new BTreeNode(3);
            BTreeNode bt4 = new BTreeNode(4);

            /* 노드 간 이진트리 관계 맺어주기 : 루트노드 -> 서브노드 -> 서브노드 */
            bt1.setLeftSubTree(bt2);
            bt1.setRightSubTree(bt3);
            bt2.setLeftSubTree(bt4);

            /* 중위순회 : 재귀 */
            BTreeNode.Traverse(bt1);

        } catch(NoSuchElementException e){
            System.out.println(e.getMessage());
        }

    }
}

import java.util.NoSuchElementException;

public class BTreeNode { //노드이자 이진트리의 루트노드 즉, 이진트리

    //왼쪽 노드는 곧 왼쪽 서브트리의 루트노드
    private BTreeNode leftSubTree;
    private BTreeNode rightSubTree;

    private Object data;

    public BTreeNode(Object data) {
        this.data = data;

        leftSubTree = null;
        rightSubTree = null;
    }

    public BTreeNode getLeftSubTree() {
        if(leftSubTree == null){
            //호출하는 쪽에서 처리를 해야함
            throw new NoSuchElementException();
        }

        return leftSubTree;
    }

    /*
        [서브트리 세팅메서드 쓰임새 : 나눠주는게 좋지않을까] : 추가 / 변경 / 삭제
        1) 아무것도 설정되어있지않을 때 관계를 설정함
        - 추가되는 노드가 곧 서브트리의 루트노드

        2) 기존에 설정되어있는 서브트리에서 루트 노드만 변경할 떄?
        - 노드일 경우와 트리일 경우 모두 생각해야함
        (1) 서브트리라고 칭해진 루트노드의 왼쪽 오른쪽 null 체크하고 null일 경우는 그대로 붙이고
        (2) null이 아니라면 2가지 경우 : 서브트리 자체를 변경하느냐 루트노드 데이터만


        3) 서브트리 삭제 : set 메서드는 서브트리를 null 만들 때도 사용
        - 순회하면서 null 처리 : 메모리 낭비를 하지않기위해 참조를 끊어줌
        - 순회의 방법은? 루트노드를 타고 들어가?
     */
    public void setLeftSubTree(BTreeNode leftSubTree) {
        this.leftSubTree = leftSubTree;
    }

    public BTreeNode getRightSubTree() {
        if(rightSubTree == null){
            throw new NoSuchElementException();
        }

        return rightSubTree;
    }

    public void setRightSubTree(BTreeNode rightSubTree) {
        this.rightSubTree = rightSubTree;
    }



    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        //데이터 변경
        this.data = data;
    }



    /*
        [순회] : 순회하는 것을 보여주려고 출력만 설정함
        1) 노드로만 보지않고 서브 트리의 루트노드로 봐야함 : 노드 + 트리 관점 접근
        2) 같은 패턴, 깊이는 몰라(반복하되 탈출조건은 있는) : 재귀 호출
        3) 재귀 : 같은 메서드지만 다른 스택프레임 생성 - 종료되어야 호출한 쪽 코드 흐름 실행
    */
    static void Traverse(BTreeNode root){
        /* [이진트리 관점] */
        if(root == null){
            return;
        }

        Traverse(root.leftSubTree);
        System.out.println(root.getData());
        Traverse(root.rightSubTree);

        /*
        [단순 노드 관점]
        if(root.leftSubTree != null){
            Traverse(root.leftSubTree);
        }
        System.out.println(root.getData());
        if(root.rightSubTree != null){
            Traverse(root.rightSubTree);
         }
         */
    }
}