트리
트리는 순환 경로가 없는 연결그래프로 그래프의 한 종류이다.
아래의 그림과 같이 이루어져 있다.
트리에서 사용되는 용어를 정리해 보자면 다음과 같다.
| 루트 | 트리의 최상위 노드 |
| 자식노드 | 노드 하위에 연결된 노드 |
| 차수 | 자식노드의 수 |
| 부모노드 | 노드의 상위에 연결된 노드 |
| 이파리 | 자식이 없는 노드 |
| 형제노드 | 동일한 부모를 가지는 노드 |
| 조상노드 | 루트까지의 경로상에 있는 모든 노드 집합 |
| 후손노드 | 노드 아래로 매달린 모든 노드 집합 |
| 서브트리 | 노드 자신과 후손노드로 이루어진 트리 |
| 레벨 | 루트가 레벨1에 있고 아래 층으로 1씩 증가 |
| 높이 | 트리의 최대 레벨 |
| 키 | 탐색에 사용되는 노드에 저장된 정보 |
이진트리
이진트리는 각 노드의 자식 노드의 수가 2개 이하인 트리이다. 이진트리는 효율적인 탐색과 삽입을 가능하게 하므로 많이 쓰인다.
아래는 파이썬으로 구현한 이진트리이다.
BTree.py
# node
class node:
def __init__(self, _item, _right = None, _left = None):
self.item = _item
self.right = _right
self.left = _left
class BTree:
def __init__(self):
self.root = None
# 전위 순회
def preOrder(self, n):
if n != None:
print(str(n.item),' ', end='')
if n.left:
self.preOrder(n.left)
if n.right:
self.preOrder(n.right)
# 중위순회
def inOrder(self, n):
if n != None:
if n.left:
self.inOrder(n.left)
print(str(n.item),' ', end='')
if n.right:
self.inOrder(n.right)
#후위순회
def postOrder(self, n):
if n != None:
if n.left:
self.postOrder(n.left)
if n.right:
self.postOrder(n.right)
print(str(n.item),' ', end='')
# 레벨 순회
def levelOrder(self, root):
q = []
q.append(root)
while len(q) != 0:
t = q.pop()
print(str(t.item),' ',end = '')
if t.left != None:
q.append(t.left)
if t.right != None:
q.append(t.right)
# 트리 높이계산
def height(self, root):
if root == None:
return 0
return max(self.height(root.right), self.height(root.left)) + 1main.py
from binaryTree import node, BTree
if __name__ == '__main__':
t = BTree()
n1 = node(100)
n2 = node(200)
n3 = node(120)
n4 = node(234)
n5 = node(345)
n6 = node(455)
n7 = node(435)
n8 = node(789)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7
n4.left = n8
t.root = n1
print('height of tree : ',t.height(t.root))
print('전위순회 보기 : ',end='')
t.preOrder(t.root)
print('\n중위순회 보기 : ',end='')
t.inOrder(t.root)
print('\n후휘순회 보기 : ',end='')
t.postOrder(t.root)
print('\n레벨순회 보기 : ',end='')
t.levelOrder(t.root)실행결과
