[Algorithm] 이진트리 2

출처

• 본 내용은 알고리즘 공부 내용이며 책과 강의 를 정리한 내용입니다

| 이번 강의 목표

• 이진 탐색 트리 순회 배우기

| 트레버스 종류는 세 가지

PRE ORDER TRAVERSE
IN ORDER TRAVERSE
POST ORDER TRAVERSE

부모가 어디 있느냐에 따라 PRE IN POST 이렇게되는 거임
PRE이면 부모가 젤 처음 : 부 왼 오
IN 이면 부모가 중간 : 왼 부 오
POST 이면 부모가 젤 마지막 : 왼 오 부

class Node:
  def __init__(self,item):
    self.val = item
    self.left = None
    self.right = None

| PRE ORDER TRAVERSE 부모 왼 오

1. 부모 루트를 방문
2. 왼쪽 서브트리 방문
3. 오른쪽 서브트리 방문

          5
         /  \
       3    7
      / \
     1   4   

방문 순서 : 5 3 1 4 7 5방문 (1)
5의 왼쪽 자식 3방문(2)
3의 왼쪽 자식 1방문(2)
1은 자식이 없음 다시 위쪽으로 올라감
3의 오른쪽 자식 4방문(3)
4는 자식이 없음 다시 위쪽으로 올라감
3은 할거 다했음 다시 위쪽으로 올라감
5의 오른쪽 자식 7방문(3)

[PRE ORDER 언제 쓰는가 ? 왜 쓰는가 ?]
한 서버의 구조를 그대로 다른 서버에 보내고 싶을 떄
방문순서  5 3 1 4 7 을 그대로 전송하면
트리 모양이 그대로 복원이 된다

def preorder_traverse(self):
    if self.head is not None:
        self.__preorder(self.head)

def __preorder(self, cur):
    self.preorder_list.append(cur.val)
    print(cur.val)
    if cur.left is not None:
        self.__preorder(cur.left)
    if cur.right is not None:
        self.__preorder(cur.right)

| IN ORDER TRAVERSE 왼 부 오

1. 왼쪽 노드 방문
2. 부모 노드 방문
3. 오른쪽 노드 방문

          5
         /  \
       3    7
      / \
     1   4   

방문 순서 1 3 4 5 7 가장 작은 값부터 정렬이됨

[IN ORDER TRAVERSE 언제 왜 쓰냐?!]
정렬을 해야할떄 
O(N)의 시간 복잡도를 가진다 

def inorder_traverse(self):
  if self.head is not None:
    self.__inorder(self.head)
    
def __inorder(self, cur):
  if cur.left is not None:
    self.__inorder(cur.left)
    
  self.inorder_list.append(cur.val)
  print(cur.val)
    
  if cur.right is not None:
    self.__inorder(cur.right)

| POST ORDER TRAVERSE 오 왼 부

1. 오른쪽 노드 방문
2. 왼쪽노드 방문
3. 부모 노드 방문

          5
         /  \
       3    7
      / \
     1   4   

방문 순서 1 4 3 7 5

def postorder_traverse(self):
    if self.head is not None:
      self.__postorder(self.head)

def __postorder(self, cur):
    if cur.left is not None:
        self.__postorder(cur.left)

    if cur.right is not None:
        self.__postorder(cur.right)

    self.postorder_list.append(cur.val)
    print(cur.val)

| 소감

재귀함수가 특징인거같다

자세한 코드 출처