트리(tree)

이동근·2021년 5월 18일
0

자료구조

목록 보기
5/9

tree(트리)

  • 계층형 트리 구조를 시물레이션 하는 추상 자료형 루트 값과, 부모-자식 관계의 서브 트리고 구성되며 서로 연결된 노드의 집합입니다.
  • 우리 주변에서 쉽게 볼 수 있는 위 아래 개념을 컴퓨터에서 표현한 구조
  • 재귀로 정의된 Recursive defined 자료구조

트리의 구성

  • root : 루트 노드라고도 하며, 트리의 시작 노드 이다. 뿌리가 된다고하며 루트라고 한다. 트리를 구성 할때 가장 위에 있는 노드를 놓는 방식으로 나타낸다. - A가 root노드이다.
  • 부모 노드 : 특정 노드의 직속 상위 노드 - D 노드가 H, I노드의 부모노드 이다.
  • 자식 노드 : 특정 노드의 직속 하위 노드 - H, I가 D 노드의 자식 노드 이다.
  • leaf 노드 : 자식 노드를 가지고 잇지 않은 가장 말단에 있는 노드 입니다. 트리의 끝에 있다고 해서 root노드와 반대되는 입장으로 leaf 노드 라고 합니다.
  • 깊이 : 특정 노드가 root노드에서 떨어져 있는 거리를 깊이 라고 합니다. 그림의 level과 같은 개념 입니다.
  • 높이 : 트리에서 가장 깊이 있는 노드의 깊이 있니다. 사진에선 H, I, J가 가장 깊이 있는 노드 이고, 높이는 3입니다.
  • 부분트리 : 현재 트리의 일부분을 이루고 있는 더 작은 트리를 의미, D,H,I 가 트리형태를이루고 있고 sub-tree라고 합니다.

트리의 활용

  • 컴퓨터 과학의 다양한 문제들을 기발하게 해결합니다. 정렬이나 , 압축을
  • 다양한 추상 자료형(데이터를 표율적으로 저장하고, 저장한 데이터를 효율적으로 찾음) - 우선순위 큐, dict, set

트리의 종류

정 이진 트리(full bine tree)

모든 노드가 2개 또는 0개의 자식을 가지는 트리

완전 이진 트리(Complete Binary Tree)

  • 마지막 레벨 직전 까지모든 노드들이 다 채워진 트리 '완전 이진 트리'
  • 마지막 레벨에서는 모든 노드들이 채워지짖는 않더라도 왼쪽 부터는 오른쪽방향으로 노드들이 다 채워져야 합니다.

순회

자료구조에 저장된 모든 데이터를 도는 것 -> 모든 노드들을 출력만 하면 된다.

트리순회

재귀를 사용해서 트리에 있는 노드를 모두 출력해 내는 것

  • pre-order 순회
  • post-order 순회
  • in-order 순회

pre-order 순회


뿌리(Root) 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순으로 출력하는 방법입니다.

  • 현재노드 데이터 출력
  • 재귀적으로 왼쪽 부분 트리 순회
  • 재귀적으로 오른쪽 부분 트리 순회
class Node:
    """이진 트리 노드를 나타내는 클래스"""

    def __init__(self, data):
        """이진 트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다"""
        self.data = data
        self.left_child = None
        self.right_child = None

def traverse_preorder(node):
    """in-order 순회 함수"""
    # 코드를 쓰세요
    if node is None:
        pass
    else:
    	print(node.data)
        traverse_inorder(node.left_child)
        traverse_inorder(node.right_child)

print()로 현재의 노드 데이터를 출력 후 -> 왼쪽 노드 순회 -> 오른쪽 노드 순회

post-order 순회


왼쪽 서브 트리 → 오른쪽 서브 트리 → 뿌리 노드 순으로 순회합니다. 구현 방법은 다음과 같습니다.

  • 재귀적으로 왼쪽 부분 트리 순회
  • 재귀적으로 오른쪽 부분 트리 순회
  • 현재노드 데이터 출력
class Node:
    """이진 트리 노드를 나타내는 클래스"""

    def __init__(self, data):
        """이진 트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다"""
        self.data = data
        self.left_child = None
        self.right_child = None

def traverse_postorder(node):
    """in-order 순회 함수"""
    # 코드를 쓰세요
    if node is None:
        pass
    else:
        traverse_inorder(node.left_child)
        traverse_inorder(node.right_child)
	print(node.data)

inorder 순회


왼쪽 서브트리 → 뿌리(Root) 노드 → 오른쪽 서브트리 순으로 순회합니다.

  • 재귀적으로 왼쪽 부분 트리 순회
  • 현재노드 데이터 출력
  • 재귀적으로 오른쪽 부분 트리 순회
class Node:
    """이진 트리 노드를 나타내는 클래스"""

    def __init__(self, data):
        """이진 트리 노드는 데이터와 두 자식 노드에 대한 레퍼런스를 갖는다"""
        self.data = data
        self.left_child = None
        self.right_child = None

def traverse_inorder(node):
    """in-order 순회 함수"""
    # 코드를 쓰세요
    if node is None:
        pass
    else:
        traverse_inorder(node.left_child)
        print(node.data)
        traverse_inorder(node.right_child)

출처 : https://geonlee.tistory.com/78

profile
하루하루 1cm 자라는 개발자

0개의 댓글