배열과 연결리스트로 Tree 구현 및 기본 개념 정리

오늘은 비선형자료구조인 트리의 개념 및 배열과 연결리스를 통해서 Tree로 간단히 구현해보는 시간을 가지려고 한다.

 

ㆍTree의 개념

- 노드와 링크로 구성된 자료구조 (그래프의 일종, cycle x)
- 계층적 구조를 나타낼 때 사용

 

ㆍTree의 구조

1. 노드 (Node)
   - 트리구조3의 자료값을 담고있는 단위
2. 에지 (Edge)
   - 노드간의 연결선
3. 루트노드 (Root Node)
   - 부모가 없는 노드, 최상위 노드
4. 잎새노드 (Leaf Node)
   - 자식이 없는 노드, 단말 노드
5. 내부노드 (Internal Node)
   - 잎새노드를 제외한 모든 노드
6. 부모노드 (Parent Node)
   - 연결된 두 노드 중 상위의 노드
7. 자식노드 (Child Node)
   - 연결된 두 노드 중 하위의 노드
8. 형제노드 (Sibling Node)
   - 같은 부모를 가지는 노드
9. 깊이 (Depth)
   - 루트에서 어떤 노드까지의 간선의 수
10. 레벨 (Level)
    - 트리의 특정 깊이를 가지는 노드 집합
11. 높이 (Height)
    - 트리에서 가장 큰 레벨 값
12. 크기 (Size)
    - 자신을 포함한 자식 노드의 개수
13. 차수 (Degree)
    - 각 노드가 지닌 가지의 수
14. 트리의 Degree
    - 트리의 최대 차수

ㆍ 트리의 특징

1. 하나의 노드에서 다른 노드로 이동하는 경로는 유일
2. 노드가 N개인 트리의 Edge의 수 = N - 1개
3. Acycle
4. 모든 노드는 서로 연결되어 있다.
5. 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리

 

ㆍ 트리의 종류

1. 이진 트리 (Binary tree)
   - 각 노드는 최대 2개의 자식을 가질 수 있다.
   - 자식노드는 좌우로 구분
   - 왼쪽 자식 (부모노드의 왼쪽 아래) / 오른쪽 자식 (부모노드의 오른쪽 아래) 
2. 포화이진트리 (Perfect binary tree)
   - 모든 레벨에서 노드들이 꽉 채워져 있는 트리
3. 완전이진트리 (Complete binary tree)
   - 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리
4. 정 이진트리 (Full binary tree)
   - 모든 노드가 0개 아니면 2개의 자식노드를 갖는 트리
5. 편향트리 (Skewed binary tree)
   - 한쪽으로 기울어진 트리
6. 균형이진트리 (Balanced binary tree)
   - 모든 노드의 좌우서브트리 높이가 1이상 차이 나지 않는 트리

 

ㆍ 이진트리의 특징

1. 포화 이진트리의 높이가 h이라면, 노드의 수는 2의 h + 1 승 - 1개
2. 포와(or 완전) 이진 트리의 노드가 N개일 때, 높이는 logN
3. 이진 트리의 노드가 N개일 때, 최대 가능 높이는 N - 1

 

ㆍ 이진트리의 순회 (Traversal)

- 모든 노드를 빠뜨리지않고 중복하지 않고 방문하는 연산

1. 전위순회 (Preorder)       ->  방문순서 : 현재 - 왼쪽 - 오른쪽
2. 중위순회 (Inorder)         ->  방문순서 : 왼쪽 - 현재 - 오른쪽
3. 후위순회 (Postorder)     ->  방문순서 : 왼쪽 - 오른쪽 - 현재
4. 레벨순회 (Levelorder)    ->  방문순서 : 위쪽레벨부터 왼쪽 - 오른쪽

 

ㆍ 이진트리구조 구

import java.util.LinkedList;

public class TreeStructure {
    public static void main(String[] args) {
        char[] arr = new char[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (char)('A' + i);
        }

        BinaryTreeStructure bts = new BinaryTreeStructure(arr);
//      루트노드
        System.out.println(bts.head.data);

//      노드 찾기
        Node2 findNode = bts.findNode('A');
        System.out.print("찾은 Node : " + findNode.data);
        if (findNode.left != null) {
            System.out.print(" / left Node : " + findNode.left.data);
        } else {
            System.out.print(" / left Node : " + null);
        }
        if (findNode.right != null) {
            System.out.print(" / right Node : " + findNode.right.data);
        } else {
            System.out.print(" / right Node : " + null);
        }
        if (findNode.parent != null) {
            System.out.print(" / parent Node : " + findNode.parent.data);
        } else {
            System.out.print(" / parent Node : " + null);
        }
        System.out.println();

//      잎새노드 찾기 => 단말노드 찾기
        System.out.println("단말노드 : ");
        for (int i = 0; i < arr.length; i++) {
            Node2 node = bts.findNode((char)('A' + i));
            if (node.left == null && node.right == null) {
                System.out.print(node.data + " ");
            }
        }
        System.out.println();

//      root -> 특정 노드까지 간선 수
        System.out.println("간선의 수");
        Node2 node2 = bts.findNode('E');
        int count = 0;
        while (node2.parent != null) {
            node2 = node2.parent;
            count++;
        }

        System.out.println("루트까지의 간선의 수 : " + count);
        System.out.println();

//      특정 level의 노드들 구하기
        System.out.println("특정 level의 노드 구하기");
        for (int i = 0; i < arr.length; i++) {
            Node2 nodeLevel = bts.findNode((char)('A' + i));
            Node2 cur = nodeLevel;
            count = 0;
            while (cur.parent != null) {
                cur = cur.parent;
                count++;
            }

            if (count == 2) {
                System.out.print(nodeLevel.data + " ");
            }
        }
        System.out.println();

//      높이구하기
        System.out.println("높이 구하기");
        int h = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            Node2 node = bts.findNode((char)('A' + i));
            Node2 cur = node;
            count = 0;
            while (cur.parent != null) {
                cur = cur.parent;
                count++;
            }

            if (count > h) {
                h = count;
            }
        }

        System.out.println("높이 : " + h);

//      자신을 포함한 자식노드들의 수 구하기
        System.out.println(bts.countChildNodePlusMe('B'));
    }
}


class Node2 {
    char data;
    Node2 left;
    Node2 right;
    Node2 parent;

    public Node2(char data, Node2 left, Node2 right, Node2 parent) {
        this.data = data;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}

class BinaryTreeStructure {
    Node2 head;

    BinaryTreeStructure() {}
    BinaryTreeStructure(char[] arr) {
        Node2[] node = new Node2[arr.length];

        for (int i = 0; i < arr.length; i++) {
            node[i] = new Node2(arr[i], null, null, null);
        }

        for (int i = 0; i < arr.length; i++) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < arr.length) {
                node[i].left = node[left];
                node[left].parent = node[i];
            }
            if (right < arr.length) {
                node[i].right = node[right];
                node[right].parent = node[i];
            }
        }

        head = node[0];
    }

    public Node2 findNode(char data) {
        LinkedList<Node2> list = new LinkedList<>();
        list.add(head);
        Node2 result = null;

        while (!list.isEmpty()) {
            Node2 node = list.removeFirst();

            if (node.data == data) {
                result = node;
                break;
            } else {
                if (node.left != null) {
                    list.add(node.left);
                }
                if (node.right != null) {
                    list.add(node.right);
                }
            }
        }

        return result;
    }

    public int countChildNodePlusMe(char data) {
        Node2 node = findNode(data);
        int count = 0;
        LinkedList<Node2> list = new LinkedList<>();
        list.add(node);

        while (!list.isEmpty()) {
            Node2 nodeOutput = list.removeFirst();
            count++;

            if (nodeOutput.left != null) {
                list.add(nodeOutput.left);
            }
            if (nodeOutput.right != null) {
                list.add(nodeOutput.right);
            }
        }

        return count;
    }
}

 

 

ㆍ 이진트리 순회구현 (배열)

레벨 순회 순으로 배열로 Tree를 구현 후 전위, 중위, 후휘, 레벨 순휘를 구현

class BinaryTreeArray {
    char[] arr;

    public BinaryTreeArray(char[] data) {
        this.arr = data.clone();
    }

    public void preOrder(int idx) {
        System.out.print(arr[idx] + " ");

        int left = idx * 2 + 1;
        int right = idx * 2 + 2;

        if (left < arr.length) {
            preOrder(left);
        }
        if (right < arr.length) {
            preOrder(right);
        }
    }

    public void inOrder(int idx) {
        int left = idx * 2 + 1;
        int right = idx * 2 + 2;

        if (left < arr.length) {
            inOrder(left);
        }

        System.out.print(arr[idx] + " ");

        if (right < arr.length) {
            inOrder(right);
        }
    }

    public void postOrder(int idx) {
        int left = idx * 2 + 1;
        int right = idx * 2 + 2;

        if (left < arr.length) {
            postOrder(left);
        }
        if (right < arr.length) {
            postOrder(right);
        }

        System.out.print(arr[idx] + " ");
    }

    public void levelOrder(int idx) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

 

 

ㆍ이진트리 순회구현 (연결리스)

값과 간선을 관리하기 위한 노드로 연결리스트 구성해서 간단하게 Tree를 구현 후 전위, 중위, 후휘, 레벨 순휘를 구현

class NodeTree {
    char data;
    NodeTree left;
    NodeTree right;

    public NodeTree(char data, NodeTree left, NodeTree right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

class BinaryTreeLinkedList {
    NodeTree head;

    BinaryTreeLinkedList() {}
    BinaryTreeLinkedList(char[] arr) {
        NodeTree[] nodeTrees = new NodeTree[arr.length];
        for (int i = 0; i < arr.length; i++) {
            nodeTrees[i] = new NodeTree(arr[i], null, null);
        }

        for (int i = 0; i < arr.length; i++) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < arr.length) {
                nodeTrees[i].left = nodeTrees[left];
            }
            if (right < arr.length) {
                nodeTrees[i].right = nodeTrees[right];
            }
        }

        head = nodeTrees[0];
    }

    public void preOrder(NodeTree nodeTree) {
        if (nodeTree == null) {
            return;
        }

        System.out.print(nodeTree.data + " ");
        preOrder(nodeTree.left);
        preOrder(nodeTree.right);
    }

    public void inOrder(NodeTree nodeTree) {
        if (nodeTree == null) {
            return;
        }

        preOrder(nodeTree.left);
        System.out.print(nodeTree.data + " ");
        preOrder(nodeTree.right);
    }

    public void postOrder(NodeTree nodeTree) {
        if (nodeTree == null) {
            return;
        }

        preOrder(nodeTree.left);
        preOrder(nodeTree.right);
        System.out.print(nodeTree.data + " ");
    }

    public void levelOrder(NodeTree nodeTree) {
        LinkedList<NodeTree> list = new LinkedList<>();
        list.addFirst(nodeTree);

        while(!list.isEmpty()){
            NodeTree n = list.removeFirst();

            System.out.print(n.data + " ");

            if (n.left != null) {
                list.addLast(n.left);
            }
            if (n.right != null) {
                list.addLast(n.right);
            }
        }
    }
}