Data Structure & Algorithm
[자료구조] 이진트리 표현법 (in python)
여뉴누
2023. 6. 18. 21:55
728x90
강의출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님
코드 결과)
https://github.com/nyunu/data_structure/blob/main/%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC.ipynb
GitHub - nyunu/data_structure
Contribute to nyunu/data_structure development by creating an account on GitHub.
github.com
이진트리 표현법
1. 선형리스트 이용 [배열 표현법]
- 루트를 배열의 1번 인덱스에 저장
-> 나머지 노드들도 위치에 따라 번호 부여
-> 배열에 각 노드를 인덱스 번호에 맞게 저장 - 0번 인덱스는 인덱스로 트리의 관계를 나타낼 수 있기 때문에 비워둠
- 완전 이진 트리일 때 유리
-> 한쪽으로 치우친 이진트리이면 공간 낭비 O - i번째 노드에 대해
-> 부모 노드 인덱스 =
-> 왼쪽 자식 노드 인덱스 =
-> 오른쪽 자식 노드 인덱스 =
2. 연결리스트 이용 [링크 표현법]
- 트리의 형태 상관없이 공간 낭비 X
- 노드 삽입, 삭제에 유리한 구조
- 노드를 포인터가 가리키도록
코드 구현
class Node:
def __init__(self, item):
self.data = item
self.rchild = None
self.lchild = None
이진트리 순회
트리순회란 ?
: 트리에 속하는 모든 노드를 한번씩 방문하는 것
트리순회 종류
: 루트 방문 순서에 따라 구분 (중간에, 처음에, 마지막에)
- 중위 순서 순회
- 후위 순서 순회
- 전위 순서 순회
- 레벨 순서 순회
1. 중위 순서 순회
: 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 순회
1) 순회 과정 및 결과
<순회 결과>
<순회 과정>
- (파란색) 처음에는 루트 노드 기준으로 왼쪽 서브트리, 오른쪽 서브트리 구분
- (파란색) 그 중 왼쪽 서브트리부터 순회
- (초록색) 왼쪽 서브트리에서의 루트 노드를 기준으로 왼쪽 서브트리, 오른쪽 서브트리 구분
- (초록색) 동일하게 그 중 왼쪽 서브트리부터 순회
- (보라색) 보라색 서브트리를 보면 루트노드 + 자식노드로만 이루어져 있음. 즉, 자식노드 = 리프노드
-> 왼쪽 자식노드인 A 순회
-> 보라색 서브트리의 루트노드인 * 순회
-> 오른쪽 자식노드인 B 순회 - (초록색) 초록색 서브트리 기준으로 왼쪽 트리 순회가 끝난 것
-> 초록색 서브트리의 루트 노드인 + 순회
-> 초록색 서브트리의 오른쪽 자식노드인 C 순회 - 전체 트리 기준으로 왼쪽 서브트리의 순회가 끝난 것
-> 파란색 전체트리의 루트 노드인 - 순회 - (파란색) 오른쪽 서브트리 순회
- (초록색) 초록색 서브트리의 자식노드 = 리프노드
-> 초록색 서브트리의 왼쪽 자식노드인 D 순회
-> 초록색 서브트리의 루트노드인 / 순회
-> 초록색 서브트리의 오른쪽 자식노드인 E 순회
2) 코드 구현
: 위의 과정을 재귀함수로 표현
(1) 왼쪽 서브노드 방문
(2) 루트 노드 방문
(3) 오른쪽 노드 방문
def inorder(self, ptr):
# 최초의 ptr은 root노드로 주어짐
if ptr:
self.stack.append(ptr.data)
# 루트 노드의 데이터를 스택에 추가
print('', self.stack)
self.inorder(ptr.lchild)
# 루트 노드 기준 왼쪽 서브트리 순회
print(ptr.data, end = '')
self.stack.pop()
# 루트 노드 순회
print(self.stack)
self.inorder(ptr.rchild)
# 루트 노드 기준 오른쪽 서브트리 순회
2. 후위 순서 순회
: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순서로 순회
1) 순회 결과
2) 코드 구현
: 재귀함수로 표현
(1) 왼쪽 서브노드 방문
(2) 오른쪽 노드 방문
(3) 루트 노드 방문
def postorder(self, ptr):
# 최초의 ptr은 root노드로 주어짐
if ptr:
self.stack.append(ptr.data)
# ptr 노드의 값을 stack에 저장
print('', self.stack)
self.postorder(ptr.lchild)
# ptr 노드 기준 왼쪽 서브트리 순회
self.postorder(ptr.rchild)
# ptr 노드 기준 오른쪽 서브트리 순회
print(ptr.data, end = '')
self.stack.pop()
# 왼쪽, 오른쪽 모두 순회한 서브트리의 루트 노드를 pop
print(self.stack)3) 코드 과정
- (파란색) ( - ) ptr로 입력되며 코드 시작
- (초록색) 루트 노드의 왼쪽 서브트리 기준으로 함수 호출 -> (+)가 루트 노드
- (보라색) 초록색 서브트리의 왼쪽 서브트리 기준으로 함수 호출 -> (*)가 루트 노드
- ptr이 (*) 노드인 상황에서 ptr.lchild 호출
-> A가 ptr이 되고
-> A를 스택에 추가
-> ptr(A).lchild 호출
-> if ptr == False 가 되어 그대로 return
-> ptr(A).rchild 호출
-> if ptr == False 가 되어 그대로 return
-> 스택의 가장 마지막 값인 A를 pop
=> 이 과정의 반복
3. 전위 순서 순회
: 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 순회
1) 순회 결과
2) 코드 구현
: 재귀함수로 표현
(1) 루트 노드 방문
(2) 왼쪽 서브노드 방문
(3) 오른쪽 노드 방문
def preorder(self, ptr):
if ptr:
self.stack.append(ptr.data)
print('', self.stack)
print(ptr.data, end = '')
self.stack.pop()
# 지금 함수가 가리키는 ptr의 데이터 값 pop
print(self.stack)
self.preorder(ptr.lchild)
# ptr 노드 기준 왼쪽 서브트리 순회
self.preorder(ptr.rchild)
# ptr 노드 기준 오른쪽 서브트리 순회3) 코드 과정
- (파란색) ( - ) ptr로 입력되며 코드 시작 -> 루트 pop
- (초록색) 루트 노드의 왼쪽 서브트리 기준으로 함수 호출 -> (+)가 루트 노드 -> pop
- (보라색) 초록색 서브트리의 왼쪽 서브트리 기준으로 함수 호출 -> (*)가 루트 노드 -> pop
- ptr이 (*) 노드인 상황에서 ptr.lchild 호출
-> A가 ptr이 되고
-> A를 스택에 추가
-> A를 pop
-> ptr(A).lchild 호출
-> if ptr == False 가 되어 그대로 return
-> ptr(A).rchild 호출
-> if ptr == False 가 되어 그대로 return
=> 위 과정의 반복
4. 레벨 순서 순회
: 루트 노드 -> 리프 노드 (왼 -> 오) 순서로 순회
1) 순회 결과
2) 코드 구현
: queue를 사용하여 구현 (cf. 앞선 전위, 중위, 후위 방식은 stack 사용)
def levelorder(self, node):
if not node : return
# root가 None이면 return
self.queue.append(node)
# queue에 node(root 노드)를 추가
while len(self.queue) > 0:
# queue에 원소가 있는 동안
node = self.queue.pop(0)
# queue의 첫번째 원소를 pop
print(node.data, end = '')
# 위에서 pop한 데이터를 출력
if node.lchild:
# 만약 node의 lchild가 존재하면
self.queue.append(node.lchild)
# node의 lchild를 queue에 추가
if node.rchild:
# 만약 node의 rchild가 존재하면
self.queue.append(node.rchild)
# node의 rchild를 queue에 추가3) 코드 과정
- root 노드로 코드 시작
- queue에 root 노드 값 먼저 넣어준 뒤
- queue에 원소가 있는 동안 while문 실행
- queue 원소 중 가장 먼저 추가된 노드 순회
- queue 원소 중 가장 먼저 추가된 노드의 lchild, rchild를 순서대로 queue에 저장
전체 코드
class Node:
def __init__(self, item):
self.data = item
self.rchild = None
self.lchild = None
class Tree:
def __init__(self):
self.queue = []
self.stack = []
self.output = ''
# 레벨 순서 순회
def levelorder(self, node):
if not node : return
# root가 None이면 return
self.queue.append(node)
# queue에 node(root 노드)를 추가
while len(self.queue) > 0:
# queue에 원소가 있는 동안
node = self.queue.pop(0)
# queue의 첫번째 원소를 pop
print(node.data, end = '')
# 위에서 pop한 데이터를 출력
if node.lchild:
# 만약 node의 lchild가 존재하면
self.queue.append(node.lchild)
# node의 lchild를 queue에 추가
if node.rchild:
# 만약 node의 rchild가 존재하면
self.queue.append(node.rchild)
# node의 rchild를 queue에 추가
# 후위 순서 순회
def postorder(self, ptr):
# 최초의 ptr은 root노드로 주어짐
if ptr:
self.stack.append(ptr.data)
print('', self.stack)
self.postorder(ptr.lchild)
# ptr 노드 기준 왼쪽 서브트리 순회
self.postorder(ptr.rchild)
# ptr 노드 기준 오른쪽 서브트리 순회
print(ptr.data, end = '')
self.stack.pop()
print(self.stack)
def inorder(self, ptr):
# 최초의 ptr은 root노드로 주어짐
if ptr:
self.stack.append(ptr.data)
# 루트 노드의 데이터를 스택에 추가
print('', self.stack)
self.inorder(ptr.lchild)
# 루트 노드 기준 왼쪽 서브트리 순회
print(ptr.data, end = '')
self.output += self.stack.pop()
# 루트 노드 순회
print(self.stack)
self.inorder(ptr.rchild)
# 루트 노드 기준 오른쪽 서브트리 순회
def inorder_view(self):
print(self.output)
def preorder(self, ptr):
if ptr:
self.stack.append(ptr.data)
print('', self.stack)
print(ptr.data, end = '')
self.stack.pop()
# 지금 함수가 가리키는 ptr의 데이터 값 pop
print(self.stack)
self.preorder(ptr.lchild)
# ptr 노드 기준 왼쪽 서브트리 순회
self.preorder(ptr.rchild)
# ptr 노드 기준 오른쪽 서브트리 순회
def viewQueue(self):
print('[', end = '')
for item in self.queue:
print(item.data, end = '')
print(']')728x90