트리 (Tree) 와 이진트리

• 계층적 구조
• 트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됨
• 맨 위를 (root)라고 부르고 노드들을 연결하는 선을 "link", "edge", "branch"라고 부름
• 부모(parent) - 자식(child) 의 관계, 조상-자손 관계
• 리프(leaf)노드 - 자식이 없는 노드들을 가리켜서 부름
• subtree 부트리 
• 레벨 : Level1, Level2, ...... root부터 아래에서
• 높이
• 트리의 기본적인 성질 : 노드가 n개면 링크의 개수는 n-1개를 가진다.

 

이진 트리 (binary tree)

• 이진 트리에서 각 노드는 최대 2개의 자식을 가진다.
• 각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지가 지정된다. (자식이 한 명인 경우에도)
• 이진 트리의 응용 예 : 중위순위 연산, Huffman Code

Full and Complete Binary Trees

• 모든 레벨의 노드들이 다 꽉 차 있는 이진트리
• 마지막 레벨을 제외한 레벨들이 꽉 차 있는 이진트리 (단 마지막레벨에서 오른쪽에서 왼쪽으로 몇개만 빌 수 있는 형태)
• 높이가 h인 full binary tree는 2^h-1개의 노드를 가진다.
• 노드가 N개인 full 혹은 complete 이진 트릐의 높이는 O(logN)이다.
  ( 노드가 N개인 이진트리의 높이는 최악의 경우 N이 될 수도 있다. 한쪽으로 기형적으로 쭉 쏠려 있을때)

이진트리의 표현 - 연결리스트

• 부모노드의 주소를 알고 기는 경우는 드물다. 반드시 그런건 아니다. Not Bad

이진트리의 순회 (traversal)

• 순회 : 이진 트리의 모든 노드를 방문하는 일
• 중순위(inorder) 순회 Left - Root - Right
• 선순위(preorder) 순회 Root - Left - Right
• 후순위(postorder) 순회 Left - Right - Root
• -> 레벨오더(level-order) 순회

레벨오더 (Level-Order) 순회

• 레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로
• 큐(queue)를 이용하여 구현 

 

예제와 코드 구현 연습해보기 좋은문제

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class 트리의순회 {

	static class Node {

		String data;
		Node left, right;

		public Node(String data) {
			this.data = data;
		}
	}

	static int N;
	static String data[] = new String[3];

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());

		Tree tree = new Tree();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				data[j] = st.nextToken();
			}
			tree.add(data[0], data[1], data[2]);
		}

		tree.preorder(tree.root);
		System.out.println();
		tree.inorder(tree.root);
		System.out.println();
		tree.postorder(tree.root);

		bw.flush();
		bw.close();

	}

	static class Tree {

		Node root;

		public void add(String data, String leftData, String rightData) {

			if (root == null) {

				if (data.compareTo(".") != 0)
					root = new Node(data);

				if (leftData.compareTo(".") != 0)
					root.left = new Node(leftData);

				if (rightData.compareTo(".") != 0)
					root.right = new Node(rightData);
			} 
			else
				search(root, data, leftData, rightData);

		}

		private void search(Node root, String data, String leftData, String rightData) {

			if (root == null)
				return;

			else if (root.data.compareTo(data) == 0) {
				if (leftData.compareTo(".") != 0)
					root.left = new Node(leftData);
				if (rightData.compareTo(".") != 0)
					root.right = new Node(rightData);
			} else {

				search(root.left, data, leftData, rightData);
				search(root.right, data, leftData, rightData);
			}

		}

		public void preorder(Node root) {
			System.out.print(root.data);
			if (root.left != null)
				preorder(root.left);
			if (root.right != null)
				preorder(root.right);
		}

		public void inorder(Node root) {

			if (root.left != null)
				inorder(root.left);
			System.out.print(root.data);
			if (root.right != null)
				inorder(root.right);
		}

		public void postorder(Node root) {

			if (root.left != null)
				postorder(root.left);
			if (root.right != null)
				postorder(root.right);

			System.out.print(root.data);
		}

	}
}