이진 트리

개념

* 트리 자료구조는 나무를 거꾸로 뒤집어 놓은 형태
Root: 트리의 맨 위 (레벨 0)
Node: 트리에서 각 위치
Edge: 노드를 이어주는 선
Degree: 자식 노드 개수
Leaf: 자식이 없는, 차수가 0인 노드
--> 이진 트리: 모든 노드의 자식이 최대 2개인 트리

종류

포화 이진 트리

--> 모든 노드가 꽉 차 있는 상태의 트리
--> 노드의 갯수: 2 ** 높이+1 - 1

완전 이진 트리

--> 번호를 부여한 순서로 노드가 배치된 트리 (일부가 비어있을 수 있음)

편향 이진 트리

--> 모든 노드가 오른쪽이나 왼쪽으로 연결된 트리

노드 구조

1) 왼쪽 링크
2) 데이터
3) 오른쪽 링크
--> 노드의 링크가 2개이다.

간단 구현

1. 이진 트리의 생성

빈 노드 생성 -> 데이터 삽입 -> 링크 연결

class TreeNode():
    def __init__(self):
        self.left = None
        self.data = None
        self.right = None
node1 = TreeNode()
node1.data = '화사'
node2 = TreeNode()
node2.data = '솔라'
node1.left = node2
node3 = TreeNode()
node3.data = '문별'
node1.right = node3
node4 = TreeNode()
node4.data = '휘인'
node2.left = node4
node5 = TreeNode()
node5.data = '쯔위'
node2.right = node5
node6 = TreeNode()
node6.data = '선미'
node3.left = node6

2. 이진 트리의 순회

순회: 이진 트리의 노드 전체를 한 번씩 방문하는 것

전위 순회: 노드의 데이터를 먼저 처리

1) 현재 노드 데이터 처리
2) 왼쪽 서브 트리로 이동
3) 오른쪽 서브 트리로 이동

중위 순회: 노드의 데이터를 중간에 처리

1) 왼쪽 서브 트리로 이동
2) 현재 노드 데이터 처리
3) 오른쪽 서브 트리로 이동

후위 순회: 노드의 데이터를 마지막에 처리

1) 왼쪽 서브 트리로 이동
2) 오른쪽 서브 트리로 이동
3) 현재 노드 데이터 처리

이진 트리 순회 구현

--> 스택, 재귀함수 이용
--> 재귀함수: 자신을 호출하는 함수

## 전위 순회 ##
def preorder(node):
    if node == None:
        return
    print(node.data, end = '->')
    preorder(node.left)
    prdorder(node.right)
## 중위 순회 ##
def inorder(node):
    if node == None:
        return
    inorder(node.left)
    print(node.data, end = '->')
    inorder(node.right)
## 후위 순회 ##
def postorder(node):
    if node == None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.data, end = '->')

일반 구현

이진 탐색 트리의 특징

1) 왼쪽 서브 트리는 루트 노드보다 모두 작은 값을 가진다.
2) 오른쪽 서브 트리는 루트 노드보다 모두 큰 값을 가진다.
3) 각 서브 트리도 1,2번 특징을 가진다.
4) 모든 노드 값은 중복되지 않는다.

이진 탐색 트리 생성

## 함수 선언 부분 ##
class TreeNode():
    def __init__(self):
        self.left = None
        self.data = None
        self.right = None
## 전역 변수 선언 부분 ##
memory = []
root = None
nameAry = ['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스']
## 메인 코드 부분 ##
# 루트 노드 생성
node = TreeNode()
node.data = nameAry[0]
root = node
memory.append(node)
# 이후 노드 생성
for name in nameAry[1:]:
    node = TreeNode()
    node.data = name
    # 시작점 설정
    current = root
    while True:
        if name < current.data:
            if current.left == None:
                current.left = node # 비어있으면 삽입
                break
            current = current.left # 차있으면 왼쪽으로 이동
        else:
            if current.right == None:
                current.right = node # 비어있으면 삽입
                break
            current = current.right # 차있으면 오른쪽으로 이동
        memory.append(node)
    print('Finished!!')

이진 탐색 트리에서 데이터 검색

findName = '마마무';
current = root
while True:
    if findName == current.data: # 일치하면 끝
        print(findName, '을 찾음.')
        break
    elif findName < current.data: # 작으면
        if current.left == None: # 없으면 트리에 존재 x
            print(findName, '이(가) 트리에 없음')
            break
        current = current.left # 있으면 이동
    else: # 크면
        if current.right == None: # 없으면 트리에 존재 x
            print(findName, '이(가) 트리에 없음')
            break
        current = current.right # 오른쪽으로 이동

이진 탐색 트리에서 데이터 삭제

1) 리프 노드를 삭제하는 경우
--> 부모 노드 링크 None 으로 변경 -> 현재 작업 노드 삭제
2) 자식 노드가 하나인 노드를 삭제하는 경우
--> 부모 노드 링크를 자식 노드의 링크로 변경 -> 현재 작업 노드 삭제
3) 자식 노드가 둘 있는 노드를 삭제하는 경우
--> 재귀 사용

deleteName = '마마무'
current = root
parent = None # 삭제하는 노드의 상위 노드를 저장
while True:
    if deleteName == current.data:
        if current.left == None and current.right == None # 리프 노드
            if parent.left == current:
                parent.left = None
            else:
                parent.right = None
            del(current)
        elif current.left != None and current.right == None:
            if parent.left == current:
                parent.left = current.left
            else:
            parent.right = current.right
            del(current)
        elif current.left == None and current.right != None:
            if parent.left == current:
                parent.left = current.left
            else:
                parent.right = current.right
            del(current)
        print(deleteName, '이(가) 삭제됨.')
        break
    elif deleteName < current.data:
        if current.left == None:
            print(deleteName, '이(가) 트리에 없음')
            break
        parent = current
        current = current.left
    else:
        if current.right == None:
            print(deleteName, '이(가) 트리에 없음')
            break
         parent = current
         current = current.right