Byeonguk Kim

안녕하세요. 29살의 조금은 늦은 나이로 새롭게 개발자로 시작하는 신입 개발자입니다. 포트폴리오 [https://deaguowl.github.io]

자료구조 11. Tree

13 Jul 2019 » 자료구조

2019.07.13 Tree

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

트리

스크린샷 2019-07-04 오후 3 16 21

  1. 어떤 노드 간에 경로가 존재해야 한다.( 즉 연결이 되어 있어야 한다) - connected
  2. 단 사이클이 없어야 한다 - acyclic
  3. set안에 tree와 tree가 있으면 forest이다
  4. 루트 노드가 없어지면 각각 분리집합으로 분할 가능

트리 용어

스크린샷 2019-07-04 오후 3 22 11

  • 레벨와 트리의 높이가 같다고 하면 한쪽으로 굉장히 치우진 것과 같다.

스크린샷 2019-07-04 오후 3 22 32

엣지와 노드와의 관계

이진트리

03C0592B-1945-4C29-BBCD-166E54B1B86E

이진트리의 특징

7E694D61-757A-46E8-B196-4A44EC01CEB2

완전 이진 트리

F8B61E1B-FD5A-4DE9-958B-A1D4DC04B71F

추가 공부할 사항

  • 포화 이진 트리
  • 편향 이진 트리

이진트리의 순회

  1. 스텍기반
    1. 전회순회
    2. 중위순회
    3. 후위순회
  2. 큐 기반
    1. 레벨 순회

전위순회(pre order)

8E201DED-3874-4ED4-BBB1-A5EC78ED01DC

class TreeNode:
    def __init__(self, data):
        self.data=data
        self.left=None
        self.right=None

def preorder(node):
    #base case
    if not node:
        return

    #노드를 방문했다고 치고 print로 찍어봄 실제로는 오퍼레이션을 넣고 방문할 떄 마다 실행
    print(node.data, end = "  ")
    # 왼쪽 자식
    preorder(node.left)
    # 오른쪽 자식
    preorder(node.right)

if __name__ == "__main__":
    n1 = TreeNode(1)
    n2 = TreeNode(2)
    n3 = TreeNode(3)
    n4 = TreeNode(4)
    n5 = TreeNode(5)
    n6 = TreeNode(6)
    n7 = TreeNode(7)

    n1.left = n2
    n1.right = n3
    n2.left = n4
    n2.right = n5
    n3.left = n6
    n3.right = n7

    preorder(n1)

중위순회(in order)

스크린샷 2019-07-04 오후 4 00 40


def preorder(node):
    #base case
    if not node:
        return

   
    # 왼쪽 자식
    preorder(node.left)
    
     #노드를 방문했다고 치고 print로 찍어봄 실제로는 오퍼레이션을 		넣고 방문할 떄 마다 실행
    print(node.data, end = "  ")
    
    # 오른쪽 자식
    preorder(node.right)
    

후위순회 (post order)

스크린샷 2019-07-13 오전 9 38 25


def preorder(node):
    #base case
    if not node:
        return

   
    # 왼쪽 자식
    preorder(node.left)
    
    # 오른쪽 자식
    preorder(node.right)
    
     #노드를 방문했다고 치고 print로 찍어봄 실제로는 오퍼레이션을 		넣고 방문할 떄 마다 실행
    print(node.data, end = "  ")