[자료구조] 트리(Tree)

2023. 7. 19. 11:27·CS 지식/[자료구조]

트리

  • 트리는 값을 가진 노드와 이 노드들을 연결해주는 간선(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
'CS 지식/[자료구조]' 카테고리의 다른 글
  • [자료구조] 해시(Hash)
  • [자료구조] 이진 탐색 트리(Binary Search Tree)
  • [자료구조] 힙(Heap)
  • [자료구조] 스택 & 큐
woojin._.
woojin._.
여러가지 개발을 해보며 발생하는 이야기들에 대한 블로그입니다:)
  • woojin._.
    Jin's Dev Story
    woojin._.
  • 전체
    오늘
    어제
    • 분류 전체보기 (829)
      • Tools (25)
        • eGovFrame (3)
        • GeoServer (3)
        • QGIS (2)
        • LabelImg (2)
        • Git (6)
        • GitHub (1)
        • Eclipse (7)
        • Visual Studio (1)
      • Web & Android (121)
        • SpringBoot (37)
        • Three.js (2)
        • Spring Data JPA (9)
        • 스프링 부트 쇼핑몰 프로젝트 with JPA (25)
        • Thymeleaf (4)
        • Spring Security (15)
        • Flutter (29)
      • Programming Language (61)
        • JAVA (27)
        • JavaScript (14)
        • Dart (2)
        • Python (15)
        • PHP (3)
      • Database (43)
        • PostgreSQL (32)
        • MYSQL (7)
        • Oracle (3)
        • MSSQL (1)
      • SERVER (17)
        • TCP_IP (3)
        • 리눅스 (7)
        • AWS (7)
      • Coding Test (445)
        • 백준[JAVA] (108)
        • 프로그래머스[JAVA] (260)
        • 알고리즘 고득점 Kit[JAVA] (3)
        • SQL 고득점 Kit[ORACLE] (74)
      • CS 지식 (49)
        • [자료구조] (14)
        • [네트워크] (12)
        • [데이터베이스] (10)
        • [알고리즘] (9)
        • [운영체제] (4)
      • 기타 (6)
      • 자격증 & 공부 (62)
        • 정보처리기사 (2)
        • SQLD (6)
        • 네트워크관리사 2급 (5)
        • 리눅스마스터 1급 (44)
        • 리눅스마스터 2급 (1)
        • ISTQB (3)
        • 시스템보안 (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 인기 글

  • 태그

    Spring Security
    리눅스마스터
    플러터
    spring
    CS
    리눅스
    Oracle
    python
    프로그래머스
    리눅스마스터 1급
    스프링부트
    backjoon
    자바
    springboot
    programmers
    baekjoon
    JPA
    백준
    CS지식
    데이터베이스
    데이터
    Java
    스프링
    스프링 부트 쇼핑몰 프로젝트 with JPA
    시큐리티
    pcce 기출문제
    postgresql
    DB
    Flutter
    Linux
  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
woojin._.
[자료구조] 트리(Tree)
상단으로

티스토리툴바