Tree

.·2022년 6월 25일
0

Computer Science

목록 보기
3/81
  • root node(최상위 노드), leaf node(자식 노드가 없는 노드), internal node

Binary Tree (이진 트리)

부모 노드가 최대 2개의 자식 노드를 가지는 트리

Binary Search Tree (BST, 이진 검색 트리)

왼쪽 자식 노드 포함 아래의 모든 노드의 데이터가 현재 노드의 데이터보다 작고, 오른쪽 자식 노드 아래의 모든 노드의 데이터가 현재 노드의 데이터보다 클 경우

tree_bst

Full Binary Tree (정 이진 트리)

모든 노드들이 0개 혹은 2개의 자식만 가질 경우

tree_full

Complete Binary Tree (완전 이진 트리)

마지막 레벨을 제외한 모든 서브트리의 레벨이 같고, 마지막 레벨은 왼쪽부터 채워진 경우

tree_complete

Perfect Binary Tree (포화 이진 트리)

마지막 레벨을 제외한 모든 노드가 2개의 자식 노드를가져서 피라미드 모양을 만드는 경우

tree_perfect

Binary Tree Traversal

  • Left Child Node → Right Child Node의 순회 순서는 유지하되, Parent Node를 처음, 중간, 마지막에 순회할 것이냐를 정한다.
  • 재귀 함수로 트리 순회 메서드 구현 가능
  1. 전위 순회 (preorder)

    Root → Left → Right

    void preorder(Node node) {
    	if (node != null) {
    		System.out.println(node.data);
    		preorder(node.left);
    		preorder(node.right);
    	}
    }
  2. 중위 순회 (inorder)

    Left → Root → Right

    void inorder(Node node) {
    	if (node != null) {
    		inorder(node.left);
    		System.out.println(node.data);
    		inorder(node.right);
    	}
    }
  3. 후위 순회 (postorder)

    Left → Right → Root

    void postorder(Node node) {
    	if (node != null) {
    		postorder(node.left);
    		postorder(node.right);
    		System.out.println(node.data);
    	}
    }

0개의 댓글