알고리즘 공부 - 트리

트리(Tree)

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

구조

노드(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로 분리됨

이진 트리

• 각 노드는 최대 2개의 자식을 가질 수 있음
• 자식 노드는 좌우를 구분함
  • 왼쪽 자식 : 부모 노드의 왼쪽 아래
  • 오른쪽 자식 : 부모 노드의 오른쪽 아래

종류

포화 이진 트리 : 모든 레벨에서 노드들이 꽉 채워져 있는 트리
완전 이진 트리 : 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리
정 이진 트리 : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
편향 트리(사향 트리) : 한쪽으로 기울어진 트리
균형 이진 트리 : 모든 노드의 좌우 서브 트리 높이가 1 이상 차이 나지 않는 트리

특징

• 포화 이진 트리의 높이가 h일 때, 노드의 수는 아래와 같다
• 포화(or 완전) 이진 트리의 노드가 N개 일 때, 높이는 logN
• 이진 트리의 노드가 N개 일 때, 최대 가능 높이는 N

이진 트리의 순회

모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산
(전위, 중위, 후위 : DFS, 레벨 : BFS)

• 전위 순회(PreOrder) : 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드
• 중위 순회(InOrder) : 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드
• 후위 순회(PostOrder) : 왼쪽 노드 -> 오른쪽 노드 -> 현재 노드

이진 트리 구현

배열을 이용한 이진 트리

static class BinaryTree {
	char[] arr;
    
    BinaryTree(char[] data) {
    	this.arr = data;
    }
    
    public void preOrder(int idx) {
    	System.out.print(this.arr[idx]+" ");
        
        int left = 2*idx+1;
        int right = 2*idx+2;
        if(left<this.arr.length) {
        	this.preOrder(left);
        }
        
        if(right<this.arr.length) {
        	this.preOrder(right);
        }
    }
    
    public void InOrder(int idx) {
    	int left = 2*idx+1;
        int right = 2*idx+2;
        if(left<this.arr.length) {
        	this.InOrder(left);
        }
        
        System.out.print(this.arr[idx]+" ");
        
        if(right<this.arr.length) {
        	this.InOrder(right);
        }
    }
    
    public void postOrder(int idx) {
        int left = 2*idx+1;
        int right = 2*idx+2;
        if(left<this.arr.length) {
        	this.postOrder(left);
        }
        
        if(right<this.arr.length) {
        	this.postOrder(right);
        }
        
        System.out.print(this.arr[idx]+" ");
    }
    
    public void levelOrder(cint idx) {
    	for(int i=0; i<this.arr.length; i++) {
        	System.out.print(this.arr[i]+" ");
        }
        System.out.println();
    }
}
public static void main(String[] args) {
	char[] arr =new char[10];
    for(int i=0; i<arr.length; i++) {
    	arr[i] = (char)('A'+i);
    }
    
    BinaryTree bt = new BinaryTree(arr);
    // A B D H I E J C F G
    bt.preOrder(0);
    // H D I B J E A F C G
    bt.inOrder(0);
    // H I D J E B F G C A
    bt.postOrder(0);
    // A B C D E F G H I J
    bt.levelOrder(0);
}

연결 리스트를 이용한 이진트리

static class Node {
	char data;
    Node left, right;
    public Node {
    	this.data = data;
        this.left = left;
        this.right = right;
    }
}
static class BinaryTree {
	Node root;
    
    BinaryTree(){}
    BinaryTree(char[] arr) {
    	Node[] nodes = new Node[arr.length];
        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.root = 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 void inOrder(Node node) {
    	if(node==null) return;
        
        this.inOrder(node.left);
        System.out.print(node.data+" ");
        this.inOrder(node.right);
    }
    
    public void 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> q = new LinkedList<>();
        q.add(node);
        
        while(!q.isEmpty()) {
        	Node cur = q.poll();
            
            System.out.print(cur.data+" ");
            if(cur.left!=null) {
            	q.offer(cur.left);
            }
            
            if(cur.right!=null) {
            	q.offer(cur.right);
            }
        }
    }
}
public static void main(String[] args) {
	char[] arr =new char[10];
    for(int i=0; i<arr.length; i++) {
    	arr[i] = (char)('A'+i);
    }
    
    BinaryTree bt = new BinaryTree(arr);
    // A B D H I E J C F G
    bt.preOrder(bt.root);
    // H D I B J E A F C G
    bt.inOrder(bt.root);
    // H I D J E B F G C A
    bt.postOrder(bt.root);
    // A B C D E F G H I J
    bt.levelOrder(bt.root);
}

트리 구조 코드 구현

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

static class BinaryTree {
	Node root;
    
    BinaryTree(char[] arr) {
    	Node[] nodes = new Node[arr.length];
        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];
              nodes[left].parent = nodes[i];
            }
            
            if(right<arr.length) {
            	nodes[i].right = nodes[right];
                nodes[right].parent = nodes[i];
            }
        }
        this.root = nodes[0];
    }
    
    public Node searchNode(char data) {
    	Queue<Node> q = new LinkedList<>();
        q.add(this.root);
        while(!q.isEmpty()) {
        	Node cur = q.poll();
            if(cur.data==data) {
            	return cur;
            }
            
            if(cur.left!=null) q.offer(cur.left);
            if(cur.right!=null) q.offer(cur.right);
        }
        return null;
    }
    
    public Integer checkSize(char data) {
    	Node node = this.searchNode(data);
        
        Queue<Node> q = new LinkedList<>();
        q.add(node);
        int size=0;
        while(!q.isEmpty()) {
        	Node cur = q.poll();
            
            if(cur.left!=null) {
            	q.offer(cur.left);
                size++;
            }
            
            if(cur.right!=null) {
            	q.offer(cur.right);
                size++;
            }
        }
        return size+1;
    }
}

public static void main(String[] args) {
	char[] arr =new char[10];
    for(int i=0; i<arr.length; i++) {
    	arr[i] = (char)('A'+i);
    }
    
    BinaryTree bt = new BinaryTree(arr);
    // Root node
    System.out.println(bt.root.data); // A
    
    // B's child
    Node B = bt.searchNode('B');
    if(B.left!=null) System.out.println("B left child : "+B.left.data); //D
    if(B.right!=null) System.out.println("B rigth child : "+B.rigth.data); // E
    
    // F's parent node
    Node F = bt.searchNode('F');
    System.out.println("F parent : "+F.parent.data); // C
    
    // Leaf node
    for(int i=0; i<arr.length; i++) {
    	Node cur = bt.searchNode((char)('A'-i));
        
        if(cur.left==null && cur.right==null) {
        	// F G H I J
        	System.out.print(cur.data+" ");
        }
    }
    
    // E's depth
    Node E = bt.searchNode('E');
    Node cur = E;
    int cnt = 0;
    while(cur.parent!=null) {
    	cur = cur.parent;
        cnt++;
    }
    System.out.println(cnt); // 2
    
    // Level2 node
    for(int i=0; i<arr.length; i++) {
    	Node target = bt.searchNode((char)('A'+i));
        cur = target;
        cnt = 0;
        while(cur.parent!=null) {
        	cur = cur.parent;
            cnt++;
        }
        
        if(cnt==2) {
        	// D E F G
        	System.out.print(target.data+" ");
        }
    }
    System.out.println();
    
    // Height
    int maxCnt = Integer.MIN_VALUE;
    for(int i=0; i<arr.length; i++) {
    	Node target = bt.searchNode((char)('A'+i));
        cur = target;
        cnt = 0;
        while(cur.parent!=null) {
        	cur = cur.parent;
            cnt++;
        }   
        maxCnt = Math.max(maxCnt, cnt);
    }
   	System.out.println(maxCnt); // 3
    
    // B's size
    System.out.println(bt.checkSize('B')); // 6
}