트리: 계층적인 관계를 가진 자료의 표현애 유용한 자료구조
이진트리의 정의
이진트리 정의
- 공집합이거나
- 루트와 왼쪽 서브트리, 오른쪽 서브 트리로 구성된 노드들의 집합. 이진트리의 서브 트리들은 모두 이진트리이어야 함.
- 포화이진트리 - 각 레벨의 노드가 가득찬 이진트리
- 완전이진트리 - 각층의 노드가 체워져 있다는 점에서 동일하지만 차이점은 마지막 레벨에서 노드들이 오른쪽 부터 테워져야 하고 중간의 노드가 비워져서는 안된다.
이진트리 성질
- n개의 노드를 가지 트리는 n-1개의 간선을 가진다.
- 높이가 h인 이진트리는 h개이상 2의 h제곱 -1 개 이하의 노드를 가진다.
- n개의 노드를 가지는 이진트리의 높이는 [log2(n+1)]이상이고 n이하이다.
배열로 트리를 표현한경우
배열로 트리를 표현한경우에는 완전트리나 포화트리는 효휼적으로 나타낼 수 있지만 경사트리나 트리의 경사가 심한경에는 메모리 공간의 낭비가 발생한다.
- 트리에서 인덱스를 이용해서 다른 노드를 찾는 방법
- 노드 i 의 부모 노드 인덱스 = i//2(파이썬의 경우에는 정수 나누셈을 하기 위해서 //연산자를 사용해야함.
- 노드 i의 왼쪽 자식 노드의 인덱스 = i*2
- 노드 i의 오른쪽 자식 노드의 인덱스 = i* 2 + 1
Tnode
class Tnode:
def __init__(self, data, left, right):
self.data = data
self.left = left # 왼쪽 자식의 포인터
self.right = right # 오른쪽 자식의 포인터
- 전위순회(preorder traversal): VLR - 부모노드 - 왼쪽서브노드 - 오른쪽 서브노드 순서대로 방문하는 것을 의미한다.
- 중위순회(inorder traversal): LVR - 왼쪽 서브노드 - 부모노드 - 오른쪽 서브노드
- 후위순회(postorder traversal): LRV - 왼쪽서브 - 오른쪽 서브- 부모노드
- 자식 노드의 정보 혹은 데이터를 참조하고 부모 노드에 적용하느 과정에서 사용한다. 유일하게 자식 노드를 먼저 방문하는 알고리즘 - 주로 파일용량 환산하는데 사용한다.
from 자료구조.bninarytree.Tnode import treeNode
from 자료구조.bninarytree.circlequeue import circleQueue
H = treeNode(None, None, 'h')
I = treeNode(None, None, 'i')
J = treeNode(None, None, 'j')
K = treeNode(None, None, 'k')
D = treeNode(H, I, 'd')
E = treeNode(None, None, 'e')
B = treeNode(D, E, 'b')
G = treeNode(J, K, 'g')
F = treeNode(None, None, 'f')
C = treeNode(F, G, 'c')
A = treeNode(B, C, 'a')
def preorder(node): # VLR
if node is not None:
print(node.data, end=' ')#현재 가운데 노드의 데이터를먼저 출력한다.
preorder(node.left)#노드의 왼쪽 자식으로 순회함
preorder(node.right)#노드의 오른쪽 자시긍로 순회함
def postorder(node): # LRV
if node is not None:
postorder(node.left)#노드의 왼쪽자식을 우선적으로 순회함
postorder(node.right)#노드의 오른쪽 자식을 순회함.
print(node.data, end=" ")#현재 가운데 노드의 데이터를 출력한다.
def inorder(node): # LVR
if node is not None:
inorder(node.left)#왼쪽 노드를 우선을 순회함.
print(node.data, end=" ")#현재 노드를 순횐함
inorder(node.right)#오른쩍 노드를 순회함.
def leveorder(node):#원형 큐를 이용해서
c = circleQueue()#원형 큐 객체를 생성한다.
c.enquene(node)#root를 먼저 큐에 삽입한다.
while not c.isEmpty():#원형큐가 빌때까지 반복한다.
n = c.dequene()#제일 처음에 삽입햇던 루트 노드를반환한다.
if n is not None:
print(n.data, end=" ")#가장먼저 들어간 노드의 출력
c.enquene(n.left)#노드의 왼쪽 자식 삽입
c.enquene(n.right)#노드의 오른쩍 자식 십입
def count_node(node):#노드의 갯수를 반환하는 함수
if node is None:
return 0
else:
return 1 + count_node(node.left) + count_node(node.right)#노드를 하나 지날 때 마다 +1 이된다 근데 이때 반환하는 값이
#다른 왼쪽 자식을 을 먼저 순회하고 그 다음에 오른쪽 자신을 순횐한다.
def count_terminalNode(node):#말단 노드의 갯수를 반환하는 함수
if node is None:#현재 대상노드가 none이면 0을 반환한다. 빈트리를 새지 않는다
return 0
elif node.left is None and node.right is None:#현재 자기 자신 주위의 자식노드들이 하나도 없으면 말단 노드 이므로 하나를 추가한다.
return 1
else:
return count_terminalNode(node.left) + count_terminalNode(node.right)#둘다 아니고 말단노드가 아니라면 양쪽노드로 순횐한다.
print("preorder", end=" ")
preorder(A)
print()
print("inorder", end=" ")
inorder(A)
print()
print("posterorder", end=" ")
postorder(A)
print("levelorder ", end=" ")
leveorder(A)
print()
print("number of node in tree", count_node(A))
print("number of terminal node", count_terminalNode(A))
위에서 부터 전위순위 중위순위 후위순위로 코드를 구현한 것이다 레벨순위는 원형 큐를 이용해서 구현했다.
def count_terminalNode(node):
if node is None:
return 0
elif node.left is None and node.right is None:
return 1
else:
return count_terminalNode(node.left) + count_terminalNode(node.right)트리의 말단 노드 즉 (terminal node)의 갯수를 반환하는 함수이다.
코딩