트리 (Tree)

• 노드와 링크로 구성도니 자료구조 (그래프의 일종, Cycle 없음)
• 계층적 구조를 나타낼 때 사용
  ex) 폴더구조 (디렉토리, 서브디렉토리)
  ex) 조직도, 가계도, ...

구조

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

특징

• 하나의 노드에서 다른 노드로 이동하는 경로는 유일
• 노드가 N개인 트리의 Edge의 수는 N-1개
• Acyclic (Cycle이 존재하지 않음)
• 모든 노드는 서로 연결되어있음
• 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리됨

이진트리 (Binary Tree)

• 각 노드가 최대 2개의 자식을 가질 수 있는 트리구조
• 자식노드는 좌우를 구분함 (왼쪽, 오른쪽)

종류

포화 이진트리 (Perfect Binary Tree)

모든 레벨에서 노드들이 꽉 채워져있는 트리

완전 이진트리 (Complete Binary Tree)

마지막 레벨을 제외하고 노드들이 모두 채워져있는 트리

정 이진 트리 (Full Binary Tree)

모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

편향 트리 (Skewed Binary Tree)

한 쪽으로 기울어진 트리
ex) LinkedList

균형이진트리 (Balanced Binary Tree)

모든 노드의 좌우 서브트리 높이가 1이상 차이나지 않는 트리

특징

• 포화 이진트리의 높이가 h 일때, 노드의 수는 $2^{h+1}-1$ 개
• 포화(or 완전) 이진 트리의 노드가 N개 일 때, 높이는$logN$
• 이진 트리의 노드가 N개 일 때, 최대가능 높이는 $N$

순회 (Traversal)

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

전위순회 (Preorder Traversal)

방문순서는 루트노드 - 왼쪽노드 - 오른쪽 노드
루트노드로 부터 왼쪽 노드 부터 오른쪽 노드로 감

중위순회 (Inorder Traversal)

방문 순서는 왼쪽노드 - 루트노드 - 오른쪽 노드
왼쪽노드 쪽으로 깊이를 쭉 파서 말단노드까지 간 후 오른쪽 노드들을 거침

후위순회 (Postorder Traversal)

방문 순서는 왼쪽노드 - 오른쪽노드 - 루트노드
아래 왼쪽부터 오른쪽 노드들을 거쳐 루트노드로 감

레벨순회 (Levelorder Traversal)

방문 순서는 위쪽 레벨부터 왼쪽노드 - 오른쪽노드

구현

배열

레벨순회순으로 배열에 구성

• 부모노드: $\div2$
• 왼쪽노드: $\times2$
• 오른쪽노드: $\times2+1$

ex) 1 -> 2,3 | 2-> 4,5 | 3-> 6,7

LinkedList

값과 간선을 관리하기 위한 노드로 연결리스트 구성

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

class BinaryTree2{
	Node head;
    BinaryTree2(){}
    BinaryTree2(char[] arr){
    for(int i = 0; i< arr.length; i++){
    	nodes[i] = new Node(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){
        	nodes[i].left = nodes[left];
		}
        if( right< arr.length){
        	nodes[i].right = nodes[right];
		}
        this.head = nodes[0];
	}
    
	}
    public void preOrder(Node node){
        if(node == null){
            return;
        }

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

    public inOrder(Node node){
        if(node == null){
            return;
        }
        this.inOrder(node.left);
        System.out.print(node.data + " ");
        this.inOrder(node.right);
    }

    public postOrder(Node node){
        if(node == null){
            return;
        }
        this.postOrder(node.left);
        this.postOrder(node.right);
        System.out.print(node.data + " ");
    }
    public void levelOrder(Node node){
    	Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while(!queue.isEmpty(){
        	Node cur = queue.poll();
            System.out.print(cur.data+ " ");
            if(cur.left != null){
            	queue.offer(cur.left);
			}
            if(cur.right != null){
            	queue.offer(cur.right);
			}
		}
	}

}

levelOrder의 경우 Queue를 이용해 쉽게 할 수 있다.