트리: 계층적인 관계를 가진 자료의 표현애 유용한 자료구조
이진트리의 정의
이진트리 정의
- 공집합이거나
- 루트와 왼쪽 서브트리, 오른쪽 서브 트리로 구성된 노드들의 집합. 이진트리의 서브 트리들은 모두 이진트리이어야 함.
- 포화이진트리 - 각 레벨의 노드가 가득찬 이진트리
- 완전이진트리 - 각층의 노드가 체워져 있다는 점에서 동일하지만 차이점은 마지막 레벨에서 노드들이 오른쪽 부터 테워져야 하고 중간의 노드가 비워져서는 안된다.
이진트리 성질
- 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)의 갯수를 반환하는 함수이다.
def isCompleteBT(root):
# Base Case: An empty tree is complete Binary tree
if root is None:
return True
# 큐 처럼 사용할 리스트를 생성해
queue = []
# 풀노드가 아닌 노드를 만나면 True로 바꿔줄 노드를 플래그를 생성해
flag = False
# 레벨 순회를 사용하기 위해서 리스트에 root를 제일 먼저 넣어줘
queue.append(root)
while (len(queue) > 0):# 데큐해서 리스트가 비지 않을 때까지만 반복해
tempNode = queue.pop(0) # deqeue를해서 tmp에 node를 넣어
# node에 자식이 존재하는지 확인해 파이썬은 None이거나 0이면 False를 반환해 그래서 None이 아닌경우를 확인하니까 왼쪽 자식의 유무가 확인이 되는겨
if (tempNode.left):
# 여기가 중요해 flag는 full node를 만났는지 아닌지 확인하는게 중요해
# 만약에 fullnode가 아닌 노드를 만났다면 False를 True로 바꿔
# flag == True라는건 풀노드가 아닌 node를 만난건데 자식이 있는 if문 내부니까
#바로 이건 완전이진트리가 아닌겨 바로 False를 반환해
if flag == True:
return False
# Enqueue left child
queue.append(tempNode.left)
# If this a non-full node, set the flag as true
else:#왼쪽자식이 존재하지 않는다면 True로 flag를 바꿔서 풀노드가 아닌 노드를 만난걸 표시해줘
flag = True
# Check if right child is present
if (tempNode.right):
# If we have seen a non full node, and we
# see a node with non-empty right child, then
# the given tree is not a complete BT
if flag == True:
return False
# Enqueue right child
queue.append(tempNode.right)
# If this is non-full node, set the flag as True
else:
flag = True
# If we reach here, then the tree is complete BT
return True
진은아 위에 있는게 이진트리가 완전이진트리 인지 확인하는 함수야 그냥 처 외워 알고리즘의 대강의 설명은 다음과 같다
풀노드를 만났는지 안만났는지 표시하는 변수인 flag가 있어
de = 0
def getLevel(root, node, depth):
global de
if node.data == root.data:
de = depth
elif node.data == root.data:
de = depth
if root is not None:
if root.left is not None:
getLevel(root.left, node, depth + 1)
if root.right is not None:
getLevel(root.right, node, depth + 1)트리에서 특정 노드의 깊이를 반환하는 함수 이를 위해서 static de를 선언해서 순환호출에서도 그 값이 유지될 수 있게 만들었다.
코딩