빅데이터 자료구조 10-2주차

전위순회의 코드구현

1. 전위 순회할 이진 트리 생성

2. 루트 노드 print 후 왼쪽 노드로 이동

3. 루트의 왼쪽 노드 print후 다시 왼쪽 자식 노드로 이동

4. 다시 왼쪽 자식 노드가 있는지 확인.  -> None 확인 후 오른쪽 노드 확인  -> None 확인하기

5. 리프 노드임을 확인 후 다시 올라가서 오른쪽 서브트리로 이동

6. 오른쪽도 마찬가지로 리프 노드까지 왼 / 오 순서로 None확인

7.  반복

 

단순하게.......

1. 루트 출력

2. 왼쪽으로 이동

여기서부터 아래 과정 반복(왼쪽 서브트리 방문)

3. 해당 노드 출력

4. 왼쪽 노드 확인 후 있으면 출력, 없으면 오른쪽 확인

5. 오른쪽 확인 후 있으면 출력, 없으면 위로 올라감

6. 올라온 노드는 이미 처리된 노드

7. 루트까지 올라가기

여기서부터 아래 과정 반복(오른쪽 서브트리 방문)

8. 왼쪽 서브트리와 같음

9. 마지막 오른쪽 자식노드의 None 확인 후 종료.

 

# 전위 순회

'''

1. 노드가 비었으면 return,

2. 아니면 출력

3. 왼쪽 순회

4. 오른쪽 순회

'''

def preorder(node):

  if node == None:

    return

  print(node.data, end='->')

  preorder(node.left)

  preorder(node.right)

 

 

중위순회의 코드구현

#중위 순회

'''

1. 노드가 비었으면 return

2. 왼쪽 서브트리로 더 파고들기

3. 더 이상 왼쪽 노드가 없으면 출력

4. 출력이 끝나면 오른쪽으로 이동

'''

def inorder(node):

  if node == None:

    return

  inorder(node.left)

  print(node.data, end='->')

  inorder(node.right)

 

후위순회의 코드구현

#후위 순회

'''

1. 노드가 비었으면 return

2. 왼쪽 서브트리 끝까지 가보기

3. 오른쪽 서브트리 끝까지 가보기

4. 끝나면 시작점이었던 자기 자신 출력

'''

def postorder(node):

  if node == None:

    return

  postorder(node.left)

  postorder(node.right)

  print(node.data, end='->')

 

 

 

이진 탐색 트리 (Binary Search Tree)

- 노드 값에 중복을 허용하지 않으며, 값을 찾는 것에 특화된 자료구조

- RULE : Left는 Parent보다 작고, Right는 Parent보다 크다

 

# 코드로 이진탐색트리 구성하기(BST 생성)

- 이진트리 생성 과정과 같으나....
1) 루트 노드의 생성
: 노드의 데이터를 입력하는 과정은 array에서 가져온다
그리고 마지막에 메모리에 해당 노드를 저장해야함...

2) 루트 노드 이후의 생성
: 배열 안에 있는 모든 인덱스 값을 트리로 만들기 위해 반복문 생성
 ㄴ 노드 만들고 데이터 삽입
 ㄴ BST는 루트 노드가 기준이기 때문에 현재 작업 노드를 루트 노드로 설정
 ㄴ 노드의 위치를 정할 때까지 반복하기 위해 무한루프 생성
    ㄴ 만약 대소비교 : (왼쪽 서브트리 탐색)

        ㄴ 만약 누울 자리 보고:

          ㄴ 데이터 자리 여기로 눕히기

          ㄴ break

        ㄴ 아니라면 다른 자리로 이동

    ㄴ else:

        ㄴ 누울 자리 확인:

          ㄴ 데이터 자리 여기로 눕히기          

          ㄴ break

        ㄴ 아니라면 다른 자리 알아보기

 : 마지막에는 메모리에 해당 노드 append

 

BST에서 데이터 탐색

- 기본 이론

  : 현재 노드의 데이터와 찾는 값이 일치한지 확인, 아니면 왼쪽 서브트리 탐색, 아니면 오른쪽 서브트리 탐색

 

#코드로 데이터 탐색하기

1. 찾는 데이터값 정의

2. 현재 작업 노드를 루트로 설정

3. 트리 내 모든 노드를 돌기 위해 무한루프 실행

4. if 찾는 값 = 현재 값 - 탈출

5. elif 찾는 값 < 현재 값:

   ㄴ 왼쪽이 비었나? - 비었으면 탈출

6. 아니면 왼쪽으로 이동

7. else

   ㄴ 8. 오른쪽 비었나? 비었으면 탈출

9. 아니면 오른쪽으로 이동

 

BST에서 데이터 삭제

# 코드로 데이터 삭제

1. 삭제할 값 정의

2. 현재작업노드를 루트로 

3. 부모를 None으로 설정

4. 무한 루프 시작

   ㄴ 5. 현재 노드가 리프노드라면, 현재가 부모의 왼쪽인지 오른쪽인지 확인하고, None 대입, del(current)

   ㄴ 6. 현재가 리프는 아닌데 왼쪽 아래 존재 : 현재가 부모의 왼쪽인지 오른쪽인지 확인하고, 왼쪽 아래와 부모 링크 연결

   ㄴ 7. 현재가 리프는 아닌데 오른쪽 아래 존재: 현재가 부모의 왼쪽인지 오른쪽인지 확인하고, 오른쪽 아래와 부모 링크 연결

   ㄴ 8. del(current)

4-1: 삭제 완료 출력 및 탈출

5. 왼쪽 탐색 블럭 만들기

   : 존재여부 확인 후, 없으면 탈출, 아니면 왼쪽 아래로 이동

6. 오른쪽 탐색 블럭 만들기