Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- Oracle
- Java
- DB
- 파이썬
- 플러터
- 자바
- 스프링 부트 쇼핑몰 프로젝트 with JPA
- CS지식
- 데이터
- javascript
- baekjoon
- 자바스크립트
- 시큐리티
- spring
- CS
- python
- 자료구조
- 스프링
- 데이터베이스
- 프로그래머스
- Spring Security
- springboot
- Flutter
- postgresql
- 네트워크
- JPA
- 리눅스
- 백준
- backjoon
- 스프링부트
Archives
- Today
- Total
Jin's Dev Story
[자료구조] 트리(Tree) 본문
트리
- 트리는 값을 가진 노드와 이 노드들을 연결해주는 간선(Edge)으로 이루어져있음
- 그림 상 데이터 1을 가진 노드가 루트(Root) 노드
- 모든 노드들은 0개 이상의 자식(Child) 노드를 갖고 있으며 보통 부모-자식 관계로 부름
트리의 특징
- 트리에는 사이클이 존재할 수 없음 (만약 사이클이 만들어진다면, 그것은 트리가 아니고 그래프)
- 모든 노드는 자료형으로 표현이 가능
- 루트에서 한 노드로 가는 경로는 유일한 경로 뿐
- 노드의 개수가 N개면, 간선은 N-1개를 가짐
트리 순회 방식
1. 전위 순회(pre-order)
- 각 루트(Root)를 순차적으로 먼저 방문하는 방식
- (Root → 왼쪽 자식 → 오른쪽 자식)1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14
2. 중위 순회(in-order)
- 왼쪽 하위 트리를 방문 후 루트(Root)를 방문하는 방식
- (왼쪽 자식 → Root → 오른쪽 자식)8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 → 14 → 7
3. 후위 순회(post-order)
- 왼쪽 하위 트리부터 하위를 모두 방문 후 루트(Root)를 방문하는 방식
- (왼쪽 자식 → 오른쪽 자식 → Root)8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1
4. 레벨 순회(level-order)
- 루트(Root)부터 계층 별로 방문하는 방식1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14
public class Tree<T> {
private Node<T> root;
public Tree(T rootData) {
root = new Node<T>();
root.data = rootData;
root.children = new ArrayList<Node<T>>();
}
public static class Node<T> {
private T data;
private Node<T> parent;
private List<Node<T>> children;
}
}
'CS 지식 > [자료구조]' 카테고리의 다른 글
[자료구조] 해시(Hash) (0) | 2023.07.19 |
---|---|
[자료구조] 이진 탐색 트리(Binary Search Tree) (0) | 2023.07.19 |
[자료구조] 힙(Heap) (0) | 2023.07.19 |
[자료구조] 스택 & 큐 (0) | 2023.07.19 |
[자료구조] Array vs ArrayList vs LinkedList (0) | 2023.07.19 |