사담 공간
여태껏 배웠던 자료구조 중에 가장 어려운 파트다!
알고리즘도 그렇고 자료구조도 그렇고 비선형 다루는게 참 어렵더라..
그래도 구현하다보면 나름 뿌듯함(?)을 느낄 수 있을 것이다 화이팅..!!
키워드
#트리 #이진트리 #이진트리탐색 #전위순회 #중위순회 #후위순회 #오일러순회 #레벨순회
1. 트리 개념
우선 자료구조 트리의 정의부터 알아보자.
트리는 계층적 관계를 표현하는 비선형 자료구조이자 그래프의 일종으로, 순환이 없는 연결 그래프이다.
정의가 굉장히... 길다. 하나씩 용어를 뜯어서 살펴보자.
계층적 관계(Hierarchical Relationship)
주로 피라미드형의 계단적 조직구조를 가리킨다. 기업의 조직도, 집안의 족보등이 그 예시가 된다.
출처 : http://news.heraldcorp.com/view.php?ud=20210219000046
그래프 (Graph)
출처 : https://news.seoul.go.kr/traffic/archives/1551
지하철 노선도와 같이 정점 (Vertex) 과 간선 (Edge) 로 이루어진 자료구조이다.
트리 또한 정점과 간선으로 이루어져 있으므로 그래프의 일종이라고 볼 수 있다.
그래프의 구현과 활용에 대해서는 이후 알고리즘 포스팅에서 좀 더 자세히 다루도록 하겠다!
순환 연결 그래프 (Cyclic Graph) VS 비순환 연결 그래프 (Acyclic Graph)
순환 그래프는 그림 3과 같이 경로의 첫번째 정점이 마지막 정점에 해당하도록 경로를 형성할 수 있는 그래프를 의미하고, 비순환 그래프는 그렇지 않은 경우의 그래프를 의미한다.
쉽게 생각해서, 환형 연결고리가 생기면 순환 그래프 / 아닐 경우 비순환 그래프이다.
무향 / 유향그래프? (Undirected / Directed Graph)
그래프가 방향성을 가지고 있는지에 따른 그래프 분류 방법으로, 방향이 있을 경우 (유향그래프일 경우) 정해진 특정 방향으로만 노드 순회가 가능하다.
트리에서는 순환이 존재하지 않으므로 비순환 연결그래프에 해당한다.
비선형(Non-linear) 자료구조 VS 선형(linear) 자료구조
앞에서 배웠던 자료구조들 (연결리스트, 스택, 큐) 은 하나의 자료 뒤에 바로 하나의 자료가 존재하는 형태로,
자료들이 1:1의 선형관계를 이룬다.
반면 이번에 배울 자료구조인 트리와 그래프는 하나의 자료 뒤에 여러 개의 자료가 연결되어 있을 수 있으므로, 자료들이 1:N 의 비선형관계를 이룰 수 있다.
트리의 개념에 대해서는 어느 정도 감이 잡힌 것 같다.
본격적인 구현에 앞서 트리를 구성하는 요소들에 대해서 자세히 알아보자!
<트리의 구성요소>
- 노드 (Node) : 트리의 구성요소이자 데이터를 저장하는 부분
- 간선 (Edge) : 노드와 노드 사이를 연결하는 선
- 루트 노드 (Root Node) : 트리 구조에서 최상위에 존재하는 노드 (부모 노드가 존재하지 않는 노드)
- 내부 노드 (Internal Node) : 단말 노드를 제외한 모든 노드
- 단말 노드 (Terminal Node, Leaf node, External Node) : 최하위 노드 (자식 노드가 존재하지 않는 노드)
단말 노드를 부르는 명칭은 리프 노드, 외부 노드와 같이 여러가지가 존재하지만 통일성을 위해 본 포스팅에서는 '단말 노드'로 명칭을 고정하겠다.
역시 그림으로 다시 한 번 이해해보도록 하겠다.
<트리 노드 간의 관계>
- 부모 노드 (parent node) : 자식 노드보다 상위 계층에 존재하며 자식 노드와 간선으로 연결된 노드
- 자식 노드 (child node) : 부모 노드보다 하위 계층에 존재하며 부모 노드와 간선으로 연결된 노드
- 형제/자매 노드 (sibling node) : 부모 노드가 동일한 노드
<서브 트리 & 경로>
- 서브 트리 (Sub-Tree) : 큰 트리의 구성 요소인 작은 트리
- 경로 (Path) : 부모 - 자식 노드를 따라서 이어진 노드 시퀀스
- 경로 길이 (Path Length) : 경로 내 간선의 수
- 노드의 깊이 (Depth) : 루트 노드로부터 해당 노드에 이르는 유일한 경로의 길이
- 노드의 높이 (Height) : 노드로부터 외부 노드에 이르는 가장 긴 경로의 길이
- 트리의 높이 : 루트 노드의 높이
2. 트리 ADT
트리 메서드 ADT
일반 메서드
- boolean isEmpty() : 트리가 비어있는지 여부를 반환
- integer size() : 트리에 저장되어 있는 노드의 개수 반환
- integer depth(v) : 노드 v의 깊이 반환
- [base] v가 루트일 경우 v의 깊이는 0
- [recursive] 그렇지 않을 경우 v 깊이는 v.parent.depth + 1
- -> 재귀적 구현이 가능
Alg depth(v)
if (isRoot(v))
return 0
else
return 1 + depth(parent(v))
- integer height(v) : 노드 v의 높이 반환
- [base] v가 외부노드일 경우 v의 높이는 0
- [recursive] 그렇지 않을 경우 v 높이는 v의 자식들 중 최대 높이 + 1
Alg height(v)
if (isExternal(v))
return 0
else
h = 0
for each w <- children(r)
h <- max(h, height(w))
return 1+h
접근 메서드
- node root() : 트리의 루트노드 반환
- node parent(v) : 노드 v의 부모 노드 반환
- node children(v) : 노드 v의 자식 노드 반환
- element element(v) : 노드 v에 저장되어 있는 데이터 반환
질의 메서드
- boolean isInternal(v) : 노드 v가 내부 노드인지 여부 반환
- boolean isExternal(v) : 노드 v가 단말 노드인지 여부 반환
- boolean isRoot(v) : 노드 v가 루트 노드인지 여부 반환
갱신 메서드
- swapElements(v, w) : 노드 v와 노드 w의 데이터 바꾸기
- element setElement(v, e) : 노드 v에 원소 e 저장
순회 메서드
트리 순회 (Tree traversal)
트리 구조에서 각각의 노드를 정확히 한번만, 체계적인 방식으로 방문하는 것을 말한다.
앞에서 배웠던 선형 자료구조들과는 다르게 비선형 자료구조에는 여러 가지 논리적인 순회 방법이 존재한다.
- 선위순회 (Pre-Order)
= 깊이 우선순회 (Depth-First Traversal)
→ 트리를 완전히 복사해서 만들 때 새로운 트리에 값을 집어넣는 동안 사용 (자식 노드가 부모 노드보다 먼저 생성되어야 하기 때문)
- 중위순회 (In-Order)
= 대칭 순회 (symmetric)
→ 이진 트리 탐색에 사용, 오름차순 또는 내림차순으로 값을 가져올 때 사용한다.
중위순회의 자세한 개념과 구현은 하단의 이진트리 개념을 알아보며 의사코드를 살펴보자.
- 후위순회 (Post-Order)
루트 노드가 그의 자손들보다 나중에 방문됨
→ 트리 삭제에 사용됨 (부모 노드 삭제 전에 자식 노드를 삭제해야 하기 때문)
- 레벨 순회 (Level-Order)
= 너비 우선 순회 (Breadth-First Traversal)
모든 노드를 낮은 레벨부터 차례대로 순회한다.
- 큐에 루트노드 삽입
- 큐에서 노드를 하나씩 빼며 (dequeue) 방문하고 노드의 왼쪽 -> 오른쪽까지 자식 노드의 유무를 확인한다.
- 자식 노드가 존재할 경우 자식 노드를 큐에 넣는다.
- 큐가 빌 때까지 2-3을 반복한다.
- preOrder(v) : 노드 v가 그의 자손들보다 앞서 방문되는 선위순회
Alg preOrder(v)
visit(v)
for each w <- children(v)
preOrder(w)
- postOrder(v) : 노드 v가 그의 자손들보다 나중에 방문되는 후위순회
Alg postOrder(v)
for each w <- children(v)
postOrder(w)
visit(v)
- levelOrder(v) : 큐를 이용해 깊이 d의 모든 노드들이 깊이 d+1의 노드들에 앞서 방문됨
- 레벨 d : 트리의 같은 깊이 d에 존재하는 모든 노드들의 집합을 나타냄
Alg levelOrder(v)
Q <- empty queue
Q.enqueue(v)
while (!Q.isEmpty())
v <- Q.dequeue()
visit(v)
for each w <- children(V)
Q.enqueue(w)
return
예외
- invalidNodeException() : 접근 불가능한 노드 접근 시 발령
3. 이진트리 개념
이진트리(Binary Tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 구조
- 루트 노드를 중심으로 두 개의 서브트리로 나눠진다
- 나눠진 두 서브트리도 모두 이진트리여야 한다
이진트리의 개념 자체가 재귀적이기에 정의를 설명할 때 이진트리 자체가 나올 수 밖에 없다...
트리의 내부 노드가 가지는 최대 두 개의 자식은 각각 왼쪽 자식 노드 / 오른쪽 자식 노드로 지칭한다.
<포화, 완전 이진 트리>
- 포화이진트리 : 모든 레벨에 노드가 가득 차있는 상태의 트리
- 완전이진트리 : 노드가 위->아래, 왼쪽 -> 오른쪽의 형태로 완전히 채워져있는 트리 (빈틈이 없음)
이진트리의 성질
- n = 노드 수
- e = 단말노드 수
- i = 내부노드 수
- h = 트리 높이
- e = i + 1
- n = i + e = 2e - 1
- h <= i
- h <= (n-1) / 2
- e <= 2^h
- h >= log_2(e)
- h >= log_2(n+1) - 1
4. 이진트리 ADT & 구현
이진트리 메서드 ADT
이진트리는 트리 ADT의 확장이므로 트리 ADT의 모든 메서드를 상속한다.
일반 메서드
- boolean isEmpty() : 트리가 비어있는지 여부를 반환
- integer size() : 트리에 저장되어 있는 노드의 개수 반환
- integer depth(v) : 노드 v의 깊이 반환
- [base] v가 루트일 경우 v의 깊이는 0
- [recursive] 그렇지 않을 경우 v 깊이는 v.parent.depth + 1
- -> 재귀적 구현이 가능
Alg depth(v)
if (isRoot(v))
return 0
else
return 1 + depth(parent(v))
- integer height(v) : 노드 v의 높이 반환
- [base] v가 외부노드일 경우 v의 높이는 0
- [recursive] 그렇지 않을 경우 v 높이는 v의 자식들 중 최대 높이 + 1
Alg height(v)
if (isExternal(v))
return 0
else
h = 0
for each w <- children(r)
h <- max(h, height(w))
return 1+h
접근 메서드
- node root() : 트리의 루트노드 반환
- node parent(v) : 노드 v의 부모 노드 반환
- node children(v) : 노드 v의 자식 노드 반환
- element element(v) : 노드 v에 저장되어 있는 데이터 반환
질의 메서드
- boolean isInternal(v) : 노드 v가 내부 노드인지 여부 반환
- boolean isExternal(v) : 노드 v가 단말 노드인지 여부 반환
- boolean isRoot(v) : 노드 v가 루트 노드인지 여부 반환
갱신 메서드
- swapElements(v, w) : 노드 v와 노드 w의 데이터 바꾸기
- element setElement(v, e) : 노드 v에 원소 e 저장
순회 메서드
- 선위순회 (Pre-Order)
= 깊이 우선순회 (Depth-First Traversal)
- 노드 방문
- 왼쪽 서브트리 선위 순회
- 오른쪽 서브트리 선위 순회
Alg binaryPreOrder(v)
visit(v)
if(isInternal(v))
binaryPreOrder(leftChild(v))
binaryPreOrder(rightChild(v))
- 중위순회 (In-Order)
= 대칭 순회 (symmetric)
- 왼쪽 서브트리 중위순회
- 노드 방문
- 오른쪽 서브트리 중위순회
Alg binaryInOrder(v)
if (leftChild(v) != NULL)
binaryInOrder(leftChild(v))
visit(v)
if (rightChild(v) != NULL)
binaryInOrder(rightChild(v))
- 후위순회 (Post-Order)
- 왼쪽 서브트리 후위순회
- 오른쪽 서브트리 후위순회
- 노드 방문
Alg binaryPostOrder(v)
if(isInternal(v))
binaryPostOrder(leftChild(v))
binaryPostOrder(rightChild(v))
visit(v)
- 오일러 투어 순회 (Euler Tour) : 이진트리에 대한 일반순회
- 오일러 경로(한붓그리기) : 그래프의 정점은 여러 번 지날 수 있지만, 모든 연결선을 단 한번씩만 통과하는 순회
왼쪽 자식 방향으로 루트를 출발하여, 트리의 간선들을 항상 왼쪽 벽으로 두면서 트리 주위를 걷는다
각 노드를 세 번씩 방문 (노드의 L, B, R에서 각각 한 번씩 방문)
=> 따라서 선위, 중위, 후위 순회를 모두 포함한다.
Alg eulerTour(v)
visitLeft(v) // preorder
if (isInternal(v))
eulerTour(leftChild(v))
visitBelow(v) // inorder
if (isInternal(v))
eulerTour(rightChild(v))
visitRight(v) // postorder
추가 메서드
- node leftChild(v) : 노드 v의 왼쪽 자식 노드 반환
- node rightChild(v) : 노드 v의 오른쪽 자식 노드 반환
- node sibling(v) : 노드 v의 형제 노드 반환
이진트리 구현
배열에 기초한 이진트리
1D 배열을 이용해서 이진트리를 표현한다.
- 랭크 i의 노드에 대해
- 왼쪽 자식의 위치 : 순위 2i
- 오른쪽 자식의 위치 : 순위 2i + 1
- 부모의 위치 : 순위 [i/2]
- 순위 0의 셀은 사용하지 않는다!
- 노드 간 링크 저장은 불필요하며 오로지 순위 인덱스로만 자식, 부모 노드를 판단한다.
- 혼동 방지를 위해 사용하지 않는 셀에는 '#'을 저장한다.
-> 밑의 그림 예시를 보면 더 잘 이해될 것이다!
<배열 노드 삽입 과정>
더보기
노드 번호 순서대로 삽입되었다고 할 때,
1. A (root) 가 순위 1에 삽입
2. A의 left child인 B가 2*1 = 2에 삽입
3. A의 right child인 C가 2*1 + 1 = 3에 삽입
4. B의 left child인 D가 2*2 = 4 에 삽입
5. B의 right child인 E가 2*2 + 1 = 5에 삽입
....
8. 포화이진트리 아니기 때문에 8번 노드가 없음. 비워두는 대신 특수 기호 (여기서는 '#' 사용) 사용해서 빈 공간을 채운다.
9. 8번과 마찬가지
10. E의 left child인 'H'가 5*2 = 10에 삽입
...
과정을 보면 파악할 수 있듯이,
- 최선의 경우는 '#'이 쓰이지 않는 완전이진트리 (배열이 빈 공간 없이 가득 차있으니 당연하다)
- 최악의 경우는 right child에만 노드가 존재하는 경우이다.
최악의 경우는 아래 그림을 통해 다시 살펴보자.
배열 크기가 N, 트리에 존재하는 노드 개수가 n이라고 할 때
- 최선의 경우 N = n
- 최악의 경우 N = 2^n - 1
이 된다.
Alg element(v)
return T[v]
Alg root()
return 1
Alg isRoot(v)
return v = 1
Alg parent(v)
return [v/2]
Alg leftChild(v)
return 2v
Alg rightChild(v)
return 2v + 1
Alg sibling(v)
if (even(v))
return v + 1
else
return v - 1
Alg isInternal(v)
return (2v < N) & (T[2v] != null)
Alg isExternal(v)
return (2v >= N) | (T[2v] = null)
Alg setElement(v, e)
T[v] <- e
return e
Alg swapElements(v, w)
tmp <- T[v]
T[v] <- T[w]
T[w] <- tmp
return
<파이썬 구현 - 트리 생성>
더보기
[그림 29] 코드로 작성한 트리
[그림 30] 실행 결과
# tree_array.py
class tree:
def __init__(self, N):
# '#' 으로 초기화해서 별도로 특수문자 초기화하는 과정 없앰
self.arr = ['#'] * N
self.N = N # 최대 할당된 길이
self.n = 0 # 혀냊 노드 수
# 순위 넣으면 해당 노드 데이터 반환
def element(self, rank):
return self.arr[rank]
# 루트 노드 데이터 반환
def root(self):
return self.arr[1]
# 루트 노드인지 판단
def isRoot(self, rank):
return rank == 1
# 부모노드 값 반환
def parent(self, rank):
return self.arr[int(rank/2)]
# 왼쪽 자식노드 값 반환
def leftChild(self, rank):
return self.arr[(rank * 2)]
# 오른쪽 자식노드 값 반환
def rightChild(self, rank):
return self.arr[(rank * 2) + 1]
# 형제노드 값 반환
def sibling(self, rank):
if rank % 2 == 0:
return self.arr[rank + 1]
else:
return self.arr[rank - 1]
# 내부 노드 true/false
def isInternal(self, rank):
return (rank * 2 < self.N) and (self.arr[2*rank] != '#')
# 단말 노드 true/false
def isExternal(self, rank):
return (rank * 2 >= self.N) or (self.arr[2*rank] == '#')
# element 삽입
def setElement(self, rank, elem):
self.arr[rank] = elem
self.n += 1
return elem
# element 교환
def swapElements(self, rank1, rank2):
tmp = self.arr[rank1]
self.arr[rank1] = self.arr[rank2]
self.arr[rank2] = tmp
return
# tree.py
from tree_array import tree
T = tree(16)
print("#" * 4, "A~I 삽입", "#" * 4)
T.setElement(1, 'A')
T.setElement(2, 'B')
T.setElement(3, 'C')
T.setElement(4, 'D')
T.setElement(5, 'E')
T.setElement(6, 'F')
T.setElement(7, 'G')
T.setElement(10, 'H')
T.setElement(11, 'I')
print("현재 저장된 노드 개수 :", T.n)
print("루트 노드 데이터 :", T.root())
print("6번째 순위에 저장된 노드 데이터 :", T.element(6))
print("E의 parent 노드 데이터 :", T.parent(5))
print("C의 left child 노드 데이터 :", T.leftChild(3))
print("B의 right child 노드 데이터 :", T.rightChild(2))
print("F의 sibling 노드 데이터 :", T.sibling(6))
print("D는 내부 노드인가? :", T.isInternal(4))
print("C는 내부 노드인가? :", T.isInternal(3))
print("D는 단말 노드인가? :", T.isExternal(4))
print("C는 단말 노드인가? :", T.isExternal(3))
print("E, I 노드 데이터 교환", T.swapElements(5, 11))
print("E의 parent 노드", T.parent(11), "I의 right child 노드", T.rightChild(5))
<실행 과정>
<실행 결과>
<파이썬 구현 - 트리 순회>
더보기
[그림 31] 배열 트리 순회 과정 - 1
[그림 32] 배열 트리 순회 과정 - 1
[그림 33] 실행 결과
위에서 생성한 이진트리를 바탕으로 다음과 같은 5개의 순회 방법을 메서드로 구현한다.
- 전위순회 (binaryPreOrder)
- 중위순회 (binaryInOrder)
- 후위순회 (binaryPostOrder)
- 레벨순회 (binaryLevelOrder)
- 오일러순회 (binaryEulerTour)
기본 메서드는 <파이썬 구현 - 트리 생성> 에서와 동일하므로 생략하고, 순회 메서드만 보도록 하겠다.
# tree_array.py
# 사용한 큐는 이전 큐 포스팅 구현 방법 참고
from queue_arr import queue
class tree:
def __init__(self, N):
# '#' 으로 초기화해서 별도로 특수문자 초기화하는 과정 없앰
self.arr = ['#'] * N
self.N = N # 최대 할당된 길이
self.n = 0 # 혀냊 노드 수
# 순위 넣으면 해당 노드 데이터 반환
def element(self, rank):
...
...
# 전위 순회
def binaryPreOrder(self, rank):
print("Visit Node :", self.element(rank), end=' ')
if(self.isInternal(rank)):
self.binaryPreOrder(self.leftChild(rank))
self.binaryPreOrder(self.rightChild(rank))
return
# 중위 순회
def binaryInOrder(self, rank):
if (self.leftChild(rank) < self.N) and (self.element(self.leftChild(rank)) != '#'):
self.binaryInOrder(self.leftChild(rank))
print("Visit Node :", self.element(rank), end=' ')
if (self.rightChild(rank) < self.N) and (self.element(self.rightChild(rank)) != '#'):
self.binaryInOrder(self.rightChild(rank))
return
# 후위 순회
def binaryPostOrder(self, rank):
if self.isInternal(rank):
self.binaryPostOrder(self.leftChild(rank))
self.binaryPostOrder(self.rightChild(rank))
print("Visit Node :", self.element(rank), end=' ')
return
# 오일러 순회
def binaryEulerTour(self, rank):
print("Visit Node :", self.element(rank), end=' ')
if self.isInternal(rank):
self.binaryEulerTour(self.leftChild(rank))
print("Visit Node :", self.element(rank), end=' ')
if self.isInternal(rank):
self.binaryEulerTour(self.rightChild(rank))
print("Visit Node :", self.element(rank), end=' ')
return
# 레벨 순회
def binaryLevelOrder(self, rank):
# 큐 사용
q = queue(self.N)
# 인덱스 랭크를 큐에 삽입
q.enqueue(rank)
while not q.isEmpty():
node_rank = q.dequeue()
print("Visit Node :", self.element(node_rank), end=' ')
if (self.leftChild(node_rank) < self.N) and (self.element(self.leftChild(node_rank)) != '#'):
q.enqueue(self.leftChild(node_rank))
if (self.rightChild(node_rank) < self.N) and (self.element(self.rightChild(node_rank)) != '#'):
q.enqueue(self.rightChild(node_rank))
return
# tree.py
from tree_array import tree
T = tree(16)
print("#" * 4, "A~I 삽입", "#" * 4)
T.setElement(1, 'A')
T.setElement(2, 'B')
T.setElement(3, 'C')
T.setElement(4, 'D')
T.setElement(5, 'E')
T.setElement(6, 'F')
T.setElement(7, 'G')
T.setElement(10, 'H')
T.setElement(11, 'I')
# print("현재 저장된 노드 개수 :", T.n)
# print("루트 노드 데이터 :", T.element(T.root()))
# print("6번째 순위에 저장된 노드 데이터 :", T.element(6))
# print("E의 parent 노드 데이터 :", T.element(T.parent(5)))
# print("C의 left child 노드 데이터 :", T.element(T.leftChild(3)))
# print("B의 right child 노드 데이터 :", T.element(T.rightChild(2)))
# print("F의 sibling 노드 데이터 :", T.element(T.sibling(6)))
# print("D는 내부 노드인가? :", T.isInternal(4))
# print("C는 내부 노드인가? :", T.isInternal(3))
# print("D는 단말 노드인가? :", T.isExternal(4))
# print("C는 단말 노드인가? :", T.isExternal(3))
# print("## E, I 노드 데이터 교환 ##")
# T.swapElements(5, 11)
# print("E의 parent 노드", T.parent(11), "I의 right child 노드", T.rightChild(5))
print("### PreOrder ###")
T.binaryPreOrder(T.root())
print()
print('### InOrder ###')
T.binaryInOrder(T.root())
print()
print('### PostOrder ###')
T.binaryPostOrder(T.root())
print()
print('### EulerTour ###')
T.binaryEulerTour(T.root())
print()
print('### LevelOrder ###')
T.binaryLevelOrder(T.root())
print()
<실행 과정>
<실행 결과>
연결리스트에 기초한 이진트리
Alg element(v)
return v.elem
Alg root()
return root
Alg isRoot(v)
return v = root
Alg parent(v)
return v.parent
Alg leftChild(v)
return v.left
Alg rightChild(v)
return v.right
Alg sibling(v)
p <- v.parent
if (p.left = v)
return p.right
else
return p.left
Alg isInternal(v)
return (v.left != null) & (v.right != null)
Alg isExternal(v)
return (v.left = null) & (v.right = null)
Alg setElement(v, e)
v.elem <- e
return e
Alg swapElements(v, w)
tmp <- v.elem
v.elem <- w.elem
w.elem <- tmp
return
<파이썬 구현 - 트리 생성>
더보기
[그림 36] 코드로 작성한 트리
[그림 37] 실행 결과
# tree_linked.py
from asyncio.windows_events import NULL
class node:
def __init__(self, elem, parent=NULL, lc=NULL, rc=NULL):
self.elem = elem
self.lc = lc
self.rc = rc
self.parent = parent
self.n = 0
class tree:
def __init__(self, root_elem):
self.root = node(root_elem)
self.n = 1
return
def root(self):
return self.root
def element(self, v):
return v.elem
def isRoot(self, v):
return v == self.root
def parent(self, v):
return v.parent
def leftChild(self, v):
return v.lc
def rightChild(self, v):
return v.rc
def sibling(self, v):
p = v.parent
if p.lc == v:
return p.rc
else:
return p.lc
def isInternal(self, v):
return (v.lc != NULL) and (v.rc != NULL)
def isExternal(self, v):
return (v.lc == NULL) and (v.rc == NULL)
# 해당 노드 (v) 에서 lc, rc 중 골라서 추가
def setElement(self, v, e, cmd):
p = node(e, v)
if cmd == 'lc':
v.lc = p
self.n += 1
elif cmd == 'rc':
v.rc = p
self.n += 1
else:
print("CommandExceptionError")
return v # 새 노드가 추가된 노드 반환
# element swap
def swapElements(self, v, w):
tmp = v.elem
v.elem = w.elem
w.elem = tmp
return
# tree.py
from tree_array import tree
T = tree(16)
print("#" * 4, "A~I 삽입", "#" * 4)
T.setElement(1, 'A')
T.setElement(2, 'B')
T.setElement(3, 'C')
T.setElement(4, 'D')
T.setElement(5, 'E')
T.setElement(6, 'F')
T.setElement(7, 'G')
T.setElement(10, 'H')
T.setElement(11, 'I')
# print("현재 저장된 노드 개수 :", T.n)
# print("루트 노드 데이터 :", T.element(T.root()))
# print("6번째 순위에 저장된 노드 데이터 :", T.element(6))
# print("E의 parent 노드 데이터 :", T.element(T.parent(5)))
# print("C의 left child 노드 데이터 :", T.element(T.leftChild(3)))
# print("B의 right child 노드 데이터 :", T.element(T.rightChild(2)))
# print("F의 sibling 노드 데이터 :", T.element(T.sibling(6)))
# print("D는 내부 노드인가? :", T.isInternal(4))
# print("C는 내부 노드인가? :", T.isInternal(3))
# print("D는 단말 노드인가? :", T.isExternal(4))
# print("C는 단말 노드인가? :", T.isExternal(3))
# print("## E, I 노드 데이터 교환 ##")
# T.swapElements(5, 11)
# print("E의 parent 노드", T.parent(11), "I의 right child 노드", T.rightChild(5))
print("### PreOrder ###")
T.binaryPreOrder(T.root())
print()
print('### InOrder ###')
T.binaryInOrder(T.root())
print()
print('### PostOrder ###')
T.binaryPostOrder(T.root())
print()
print('### LevelOrder ###')
T.binaryLevelOrder(T.root())
print()
print('### EulerTour ###')
T.binaryEulerTour(T.root())
print()
<실행 과정>
<실행 결과>
<파이썬 구현 - 트리 순회>
더보기
[그림 38] 트리 순회 과정
[그림 39] 실행 결과
위에서 생성한 이진트리를 바탕으로 다음과 같은 5개의 순회 방법을 메서드로 구현한다.
- 전위순회 (binaryPreOrder)
- 중위순회 (binaryInOrder)
- 후위순회 (binaryPostOrder)
- 레벨순회 (binaryLevelOrder)
- 오일러순회 (binaryEulerTour)
기본 메서드는 <파이썬 구현 - 트리 생성> 에서와 동일하므로 생략하고, 순회 메서드만 보도록 하겠다.
# tree_linked.py
from asyncio.windows_events import NULL
from queue_linked_list import queue
class node:
def __init__(self, elem, parent=NULL, lc=NULL, rc=NULL):
self.elem = elem
self.lc = lc
self.rc = rc
self.parent = parent
self.n = 0
class tree:
def __init__(self, root_elem):
self.root = node(root_elem)
self.n = 1
return
...
# 전위 순회
def binaryPreOrder(self, v):
print("Visit Node :", self.element(v), end=' ')
if(self.isInternal(v)):
self.binaryPreOrder(self.leftChild(v))
self.binaryPreOrder(self.rightChild(v))
# 중위 순회
def binaryInOrder(self, v):
if self.leftChild(v) != NULL:
self.binaryInOrder(self.leftChild(v))
print("Visit Node :", self.element(v), end=' ')
if self.rightChild(v) != NULL:
self.binaryInOrder(self.rightChild(v))
# 후위 순회
def binaryPostOrder(self, v):
if self.isInternal(v):
self.binaryPostOrder(self.leftChild(v))
self.binaryPostOrder(self.rightChild(v))
print("Visit Node :", self.element(v), end=' ')
# 오일러 순회
def binaryEulerTour(self, v):
print("Visit Node :", self.element(v), end=' ')
if self.isInternal(v):
self.binaryEulerTour(self.leftChild(v))
print("Visit Node :", self.element(v), end=' ')
if self.isInternal(v):
self.binaryEulerTour(self.rightChild(v))
print("Visit Node :", self.element(v), end=' ')
# 레벨 순회
def binaryLevelOrder(self, v):
# 큐 사용
q = queue()
# 인덱스 랭크를 큐에 삽입
q.enqueue(v)
while not q.isEmpty():
node = q.dequeue()
print("Visit Node :", self.element(node), end=' ')
if self.leftChild(node) != NULL:
q.enqueue(self.leftChild(node))
if self.rightChild(node) != NULL:
q.enqueue(self.rightChild(node))
return
# tree_2.py
from tree_linked import tree
T = tree('B')
root = T.root
print('#' * 4, "A, D 추가", '#' *4)
T.setElement(root, 'A', 'lc')
T.setElement(root, 'D', 'rc')
print('#' * 4, "C, E 추가", '#' *4)
T.setElement(root.rc, 'C', 'lc')
T.setElement(root.rc, 'E', 'rc')
# print("현재 저장된 노드 개수 :", T.n)
# print("루트 노드 체크 :", T.isRoot(root))
# print("루트 노드 데이터 :", root.elem)
# print("루트 노드 - left child 노드 :", T.leftChild(root).elem)
# print("루트 노드 - right child 노드 :", T.rightChild(root).elem)
# print("루트 노드 - right child - left child :", T.leftChild(root.rc).elem)
# print("루트 노드 - right child - right child :", T.rightChild(root.rc).elem)
# print("C의 sibling 노드 데이터 :", T.sibling(root.rc.lc).elem)
# print("E의 sibling 노드 데이터 :", T.sibling(T.rightChild(root.rc)).elem)
# print("노드 A는 내부 노드인가? ", T.isInternal(root.lc))
# print("노드 B는 내부 노드인가? ", T.isInternal(root))
# print("노드 A는 단말 노드인가? ", T.isExternal(root.lc))
# print("노드 B는 단말 노드인가? ", T.isExternal(root))
# print('#' * 4, "root - root.lc data swap", '#' * 4)
# print('#' * 4, "변경 전", '#' * 4)
# print("루트 노드 데이터 :", root.elem)
# print("루트 노드 - left child 노드 :", T.leftChild(root).elem)
# T.swapElements(root, root.lc)
# print('#' * 4, "변경 후", '#' * 4)
# print("루트 노드 데이터 :", root.elem)
# print("루트 노드 - left child 노드 :", T.leftChild(root).elem)
print("### PreOrder ###")
T.binaryPreOrder(root)
print()
print('### InOrder ###')
T.binaryInOrder(root)
print()
print('### PostOrder ###')
T.binaryPostOrder(root)
print()
print('### LevelOrder ###')
T.binaryLevelOrder(root)
print()
print('### EulerTour ###')
T.binaryEulerTour(root)
<실행 과정>
<실행 결과>
'알고리즘 > 자료구조_알고리즘' 카테고리의 다른 글
| [알고리즘] 00. 자료구조 리마인드 (0) | 2023.09.11 |
|---|---|
| [자료구조] 09. 그래프 - 개념과 표현방식 (0) | 2023.01.03 |
| [자료구조] 07. 큐 (Queue) & 덱 (Dequeue) (0) | 2022.08.29 |
| [자료구조] 06. 스택 (Stack) (0) | 2022.08.25 |
| [자료구조] 05. 집합 (0) | 2022.08.25 |
