Powerful Tree Structure on Python
파이썬의 트리 자료구조에 대해서 학습해보도록 하겠습니다. 보통 트리 자료 구조라 함은 나무의 형태를 떠올리는데 아주 정확합니다. 마치 데이터가 나무가 가지 치듯 뻗어 나간 듯한 형태라 하여 트리 자료 구조라 합니다. 자료구조 수업을 들으신 분이라면 아마 어느 정도 구현하실 수 있겠지만, 솔직히 인간의 기억력은 한계가 존재하잖아요^^; 대충만 훑으셔도 될 것 같으며, 처음 보시는 분들은 면밀하게 하나하나 따라오시다 보면 시간은 좀 걸리시겠지만 학습하실 수 있습니다. 트리 자료구조는 많은 추상적인 사고력을 요합니다. 물론 다른 자료구조도 마찬가지만, 비선형 자료구조이기 때문에 일반적인 형태를 떠올려선 안됩니다!! 그렇다면 구현을 해보도록 하겠습니다.
Implemented Node
class Node:
def __init__(self, value = None, lvalue = None, rvalue = None):
self.value = value
self.left = lvalue
self.right = rvalue
우선 트리자료구조에 들어갈 하나의 노드를 선언하도록 하겠습니다. 이 노드는 트리 자료구조를 이루는 하나의 알갱이가 될 것이며, 자기 자신이 부모 노드가 되어 자식 노드 2개를 거느릴 수 있습니다. 본 블로그는 이진트리를 중심으로 실습하기 때문에 왼쪽과 오른쪽 자식 노드만을 가집니다!
그러니까 위 그림과 같이 하나의 노드는 부모노드가 될 수 있으며, 동시에 자식 노드가 될 수 있어야만 합니다. 그리고 무조건 자식 노드 두 명까지만 가질 수 있기 때문에 좌, 우로 자식 노드가 존재하는 것입니다!!
Implemented Tree
현 시점부터 아래로 내려가는 코드 블록들은 모두 트리 클래스 내부의 멤버 함수입니다. 외부에 선언하거나 노드의 함수로 선언하는 일 없이, 트리 클래스 내부에 작성해주셔야 정상적으로 작동함을 알려드립니다!
class Tree:
def __init__(self, root = None):
self.root = root
우선 트리 클래스를 선언해주는데 초기화 멤버 변수로 최상위 부모 노드인 root만을 가지고 갑니다. 이해가 안 될 때는 그림과 함께 코드를 봐주시면 더욱 이해에 도움이 되리라 생각합니다!
Push
def push(self, value):
node = Node(value = value)
tempNode = self.root
if self.root is None:
self.root = node
return
else:
ptrNode = self.root
while ptrNode is not None:
tempNode = ptrNode
if node.value < ptrNode.value:
ptrNode = ptrNode.left
else:
ptrNode = ptrNode.right
if node.value < tempNode.value:
tempNode.left = node
else:
tempNode.right = node
코드의 양이 많기는 하나, 우선 보게 되면 첫줄에 새로운 노드를 함수의 인자로 받아온 값으로 노드를 하나 생성합니다. 그리고 root노드의 복사 값을 하나 생성해줍니다. 만약 root의 값이 None일 경우에는 새로 생성한 노드를 루트에 대입하고 프로그램을 종료하면 되나, 아닐 경우에는 비교하고자 하는 노드의 값보다 작으면 왼쪽으로 순회해 값을 추가하고, 크다면 오른쪽으로 순회해 값을 추가하는 것으로 동작을 마무리합니다
Pop
def removeNode(self, value):
temp = self.root
self.pop(temp, value)
def pop(self, node, value):
if node is None:
return -1
elif node.value > value:
node.left = self.pop(node.left, value)
elif node.value < value:
node.right = self.pop(node.right, value)
else:
temp = node
if node.right is None and node.left is None:
del node
node = None
elif node.right is None:
node = node.left
del temp
elif node.left is None:
node = node.right
del temp
else:
temp = self.searchMaxNode(node.left)
node.value = temp.value
node.left = self.pop(node.left, temp.value)
return node
트리 자료구조에서 데이터를 제거하는 일은 쉬운 일이 아닙니다. 최악의 경우에는 모든 노드를 순회해서 값을 찾아내 제거해야 할 수 도 있지만, 선형 자료구조에 비해서는 탐색의 비용이 매우 적게 드는 편이기 때문에 이 또한 빠르다고 볼 수 있습니다. 구현하는 게 조금 어려워서 그렇죠..ㅎ 우선 self.removeNode에 제거하고자 하는 값을 대입해 root의 복사 값 노드와 함께 pop함수를 호출합니다. 제가 위에서 값의 대소에 따라서 노드를 추가해준 것을 모두 알고 계실 겁니다. 그렇기 때문에 값의 대소에 따라서 왼쪽 노드로 이동하고, 오른쪽 노드로 이동해서 값을 찾아 제거합니다. 다만 코드의 아랫부분에 self.searchMaxNode가 보이는 것을 알 수 있습니다. 루트 노드를 기준으로 왼쪽 노드에서 최댓값을 찾아 반환하도록 하는 부분입니다. 현재는 없는 값을 함수의 인자로 넘겼을 때는 오류가 발생합니다. 그도 그럴 것이 예외처리를 해주지 않았으니까요!! 원하시면 해드리겠으나, 여러분들이 한번 추가해보는 것도 재밌을 것 같아 남겨두었습니다. 귀찮아서 그런 거 절대 아닙니다!!!!^^
Search Node
def searchMaxNode(self):
if self.root is None:
return
else:
temp = self.root
maxVal = 0
while temp is not None:
maxVal = temp.value
temp = temp.right
print("Max Value : ", maxVal)
return 0
def searchNode(self, value):
temp = self.root
tempRoot = Node()
while temp is not None:
if temp.value == value:
print("Find Value")
return True
elif temp.value > value:
temp = temp.left
else:
temp = temp.right
print("Value Not Found")
return False
트리를 탐색하는 코드입니다. 위의 searchMaxNode는 기준 노드의 레벨 아래에 구현되어 있는 데이터 중 최댓값을 찾아 반환하는 함수인데, 이 코드 또한 여러분들이 일반적으로 동작시킬 때는 아마 잘 동작 하나, 아마 어느 부분에서 오류가 발생할 것입니다. 일반적인 상황에서 발생하지 않으나, 한번 고쳐보시면서 코드를 정상 동작시켜보세요! 코드를 보수하는 것만큼 실력이 느는 게 없습니다. 특히 남의 코드를 수정하는 것은 더욱 어려운 일이지요! 아래 searchNode는 함수의 인자로 들어온 값을 왼쪽과 오른쪽으로 순회하며 찾아서 반환하는 값이나 없면 거짓을 반환하며 동작을 종료합니다!!
Tree Order
트리 자료구조의 중요한 부분인 순회입니다. 사실 탐색이랑 별 다를 바 없습니다. 대표적으로 사용하는 순회는 전위 순회, 중위 순회, 후위 순회가 있습니다 , 코드를 보여드리기 전에 간략히 말씀드리면, 전위 순회는, 부모 노드에서 시작해서 왼쪽 노드를 모두 순회하고 부모의 오른쪽 노드로 순회하는 코드이며, 중위 순회는 왼쪽 최하위 자식 노드로 시작해서 오른쪽 최하위 자식 노드로 순회하는 코드입니다. 후위 순회는 왼쪽 최하위 자식 노드 -> 오른쪽 최하위 자식노드 -> 부모 노드로 순회하는 방식입니다. 이 과정은 한 번에 이해가 가지 않을 겁니다. 어떤 레퍼런스를 따라가보더라도 한번에 이해하기엔 힘드니, 계속해서 코드를 작성해가며 이해하는 방법밖엔 없습니다.
def show(self):
temp = self.root
print("What kind of Traverse(1.inorder, 2.preodrer, 3.postorder")
a = int(input())
if a == 1:
self.inOrder(temp)
elif a == 2:
self.preOrder(temp)
elif a == 3:
self.postOrder(temp)
else:
return -1
def inOrder(self, node):
if node is not None:
self.inOrder(node.left)
print(node.value)
self.inOrder(node.right)
def preOrder(self, node):
if node is not None:
print(node.value)
self.preOrder(node.left)
self.preOrder(node.right)
def postOrder(self, node):
if node is not None:
self.postOrder(node.left)
self.postOrder(node.right)
print(node.value)
__name__
현재 자료구조는 모두 구현되었습니다!! 그렇다면 코드를 테스트해봐야겠죠? 아래 코드를 기입합니다.
if __name__ == "__main__":
tree = Tree()
tree.push(100)
tree.push(40)
tree.push(50)
tree.push(10)
tree.push(15)
tree.push(30)
tree.push(20)
tree.push(50)
tree.push(40)
tree.show()
tree.searchMaxNode()
제가 말씀드린 코드는 한번 보수를 직접 해보시는 것을 추천드립니다. 물론 그냥 궁금해 검색해 들어오신 분들도 직접 타이핑할 수 없다면 머릿속으로나마 이렇게 하면 될 것 같은데 한번 생각해보시길...
글 잘 읽으셨다면 공감 하트 한 번씩 눌러주시면 감사하겠습니다😁😁😁
댓글로 문의, 피드백, 질문 모두 받습니다!!
감사합니다🥰🥰🥰🥰🥰🥰
'Python' 카테고리의 다른 글
| [Python 자료구조] list_map, filter 등 리스트 응용! (0) | 2021.01.28 |
|---|---|
| [Python 자료구조] 연결리스트_implemented Linked List@_탐색, 순회, 추가 및 삭제 (0) | 2021.01.06 |
| [Python활용]파이썬 제너레이터를 이용한 파일 읽기 및 쓰기!! (1) | 2020.12.14 |
| [Python] map과 zip 내장함수 사용하기!! (0) | 2020.12.12 |
| [Python] DefaultDict 다루기!!! (0) | 2020.12.10 |
댓글