자료구조 11. Tree

2019.07.13 Tree

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

# 질문에 답하기

1. 트리

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

트리 용어

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

엣지와 노드와의 관계

• MST : KRUSKAL 알고리즘 -> 도시계획
• CS/binary_tree.pdf at master · ythwork/CS

이진트리

이진트리의 특징

완전 이진 트리

추가 공부할 사항

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

이진트리의 순회

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

전위순회(pre order)

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)

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


    # 왼쪽 자식
    preorder(node.left)

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

    # 오른쪽 자식
    preorder(node.right)

후위순회 (post order)

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


    # 왼쪽 자식
    preorder(node.left)

    # 오른쪽 자식
    preorder(node.right)

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