[Algorithm] Tree, Map 자료구조

1. Tree란?

가계도와 같은 계층적은 구조를 표현할 때 사용할 수 있는 자료구조이다. 

용어 정리)

루트 노드: 부모가 없는 최상위 노드

단말 노드: 자식이 없는 노드

크기: 트리에 포함된 모든 노드의 개수

깊이: 루트 노드부터의 거리

높이: 깊이 중 최댓값

차수: 각 노드의 간선 개수 (자식이 몇개인지) 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개이다.

 

구현) 파이썬 코드

 

class Node:
        def __init__(self, data, left_node, right_node):
                self.data=data
                self.left_node=left_node
                self.right_node=right_node
                
 
 
n = int(input())
tree = {}
for i in range(10):
        data, left_node, right_node = input().split()
        if left_node == "None":
                left_node = None
        if right_node == "None":
                right_node = None
        tree[data] = Node(data, left_node, right_node)

 

 

 

2. 이진탐색트리 (Binary Search Tree)란?

이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종이며,  값이 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 를 가진다.  (기술 면접 단골 문제라고 하니 .. 꼭 구현해보자)

 

ex. 

 

 

1. 루트부터 아래쪽 레벨로 노드가 가득 차 있고,
2. 마지막 레벨에서 왼쪽부터 오른쪽으로 노드가 채워져 있는

이진트리를 '완전 이진트리' 라고 한다.

 

이진 트리에 노드 추가 구현) 

def add(self,key,value)->bool:
    # 노드 추가하는 내부 함수
    def add_node(node, key,value)->None:
        # 탐색하고 적절한 자리에 삽입
        if key == node.key: #이미 삽입하려는 키가 있으면 false 처리
            return False
        # 삽입하려는 키가 현재 탐색 노드의 키보다 작다면
        elif key < node.key:
            # 그 탐색 노드의 왼쪽 자식이 없다면 바로 그 자리에 삽입
            if node.left is None:
                node.left = Node(key,value,None,None)
            else:
            # 자식이 있으면 재귀함수 호출로 한번 더 들어감
                add_node(node.left,key,value)
        # 삽입하려는 키가 현재 탐색 노드의 키보다 크거나 같다면
        else:
            # 그 탐색 노드의 오른쪽 자식이 없다면 바로 그 자리에 삽입
            if node.right is None:
                node.right = Node(key,value,None,None)
            else:
            # 자식이 있으면 재귀함수 호출로 한번 더 들어감
                add_node(node.right,key,value)
        return True
    # 루트가 있는 경우
    if self.root is None:
        self.root = Node(key,value,None,None)
        return True
    # 루트가 없는 경우
    else: #리턴값은 내부함수 리턴 값
        return add_node(self.root,key,value)

 

참고 사이트)  다른 연산들 참고. 

https://velog.io/@seanlion/bstimplementation

 

3. 순회

트리 자료구조에 포함된 노드를 특정한 방법으로 한번씩 방문하는 방법을 의미한다. 

- 전위 순회: 루트를 먼저 방문한다.

- 중위 순회: 왼쪽 자식을 방문한 뒤에 루트를 방문한다.

- 후위 순회: 오른쪽 자식을 방문한 뒤에 루트를 방문한다.

 

ex.

전위 순회: A  B  D  E  C  F  G

중위 순회: D  B  E  A  F  C  G

후위 순회: D  E  B  F  G  C  A

 

4. 파이썬으로 트리, 순회 구현하기

 

class Node:
        def __init__(self, data, left_node, right_node):
                self.data=data
                self.left_node=left_node
                self.right_node=right_node

# 전위 순회
def pre_order(node):
        print(node.data, end='')
        if node.left_node!= None:
                pre_order(tree[node.left_node])

        if node.right_node!= None:
                pre_order(tree[node.right_node])

# 중위 순회
def in_order(node):
        if node.left_node != None:
                in_order(tree[node.left_node])
        print(node.data, end='')
        if node.right_node != None:
                in_order(tree[node.right_node])

# 후위 순회
def post_order(node):
        if node.left_node != None:
                post_order(tree[node.left_node])
        if node.right_node != None:
                post_order(tree[node.right_node])
        print(node.data, end='')

n = int(input())
tree = {}

for i in range(n):
        data, left_node, right_node = input().split()
        if left_node == "None":
                left_node = None
        if right_node == "None":
                right_node = None
        tree[data] = Node(data, left_node, right_node)


pre_order(tree['A'])
print()

in_order(tree['A'])
print()

post_order(tree['A'])

 

 

 

5. MAP이란? 

key와 value로 이루어진 자료구조이다. ex. name - 'kyuri' / age - '25' / studentId - '2019125007'

key는 map 자료구조에서 대응하는 값을 찾기위한 요소로 중복을 허용해서는 안된다. 

 

참고) 이것이 코딩테스트다.