# Node구현
class Node:
nodeNext = None
nodePrev = ''
nodeValue = ''
binHead = False
binTail = False
def __init__(self, objvalue='', nodeNext=None, binHead=False, binTail=False):
self.nodeNext = nodeNext
self.objvalue = objvalue
self.binHead = binHead
self.binTail = binTail
def getValue(self):
return self.objvalue
def setValue(self, objvalue):
self.objvalue = objvalue
def getNext(self):
return self.nodeNext
def setNext(self, nodeNext):
self.nodeNext = nodeNext
def isHead(self):
return self.binHead
def isTail(self):
return self.binTail
# SinglyLinkedList구현
class SinglyLinkedList():
nodeHead = ''
nodeTail = ''
size = 0
def __init__(self): # Empty Linked List으로 초기화
self.nodeTail = Node(binTail=True)
self.nodeHead = Node(binHead=True, nodeNext=self.nodeTail)
def insertAt(self, objInsert, idxInsert):
nodeNew = Node(objvalue=objInsert)
nodePrev = self.get(idxInsert - 1)
nodeNext = nodePrev.getNext()
nodePrev.setNext(nodeNew)
nodeNew.setNext(nodeNext)
self.size += 1
def removeAt(self, idxRemove):
nodePrev = self.get(idxRemove - 1)
nodeRemove = nodePrev.getNext()
nodeNext = nodeRemove.getNext()
nodePrev.setNext(nodeNext)
self.size -= 1
return nodeRemove.getValue()
def get(self, idxRetrieve):
nodeReturn = self.nodeHead
for itr in range(idxRetrieve + 1):
nodeReturn = nodeReturn.getNext()
return nodeReturn
def printStatus(self):
nodeCurrent = self.nodeHead
while nodeCurrent.getNext().isTail() == False:
nodeCurrent = nodeCurrent.getNext()
print(nodeCurrent.getValue(), end=" ")
print("")
# Queue의 isEmpty()추가하려고 만든 Memberfunction
def Statue(self):
nodeCurrent = self.nodeHead
temp_list = []
while nodeCurrent.getNext() is not None and nodeCurrent.getNext().isTail() == False:
nodeCurrent = nodeCurrent.getNext()
temp_list.append(nodeCurrent.getValue())
return temp_list
def getSize(self):
return self.size
# Queue 구현
class Queue():
lstInstance = SinglyLinkedList()
def dequeue(self):
return self.lstInstance.removeAt(0)
def enqueue(self, value):
self.lstInstance.insertAt(value, self.lstInstance.getSize())
# isEmpty의 구현을 위해 새로 Memberfunction 생성
def isEmpty(self):
if len(self.lstInstance.Statue()) == 0:
return True
else:
False
# Tree Node구현
class TreeNode:
nodeRHS = None
nodeLHS = None
nodeParent = None
value = None
def __init__(self, value, nodeParent):
self.value = value
self.nodeParent = nodeParent
def getLHS(self):
return self.nodeLHS
def getRHS(self):
return self.nodeRHS
def getValue(self):
return self.value
def getParent(self):
return self.nodeParent
def setLHS(self, LHS):
self.nodeLHS = LHS
def setRHS(self, RHS):
self.nodeRHS = RHS
def setValue(self, value):
self.value = value
def setParent(self, nodeParent):
self.nodeParent = nodeParent
# BST구현..
class BinarySearchTree:
root = None
def __init__(self):
pass
def insert(self, value, node=None):
if node is None:
node = self.root
if self.root is None:
self.root = TreeNode(value, None)
return
if value == node.getValue():
return
if value > node.getValue():
if node.getRHS() is None:
node.setRHS(TreeNode(value, node))
else:
self.insert(value, node.getRHS())
if value < node.getValue():
if node.getLHS() is None:
node.setLHS(TreeNode(value, node))
else:
self.insert(value, node.getLHS())
return
def search(self, value, node=None):
if node is None:
node = self.root
if value == node.getValue():
return True
if value > node.getValue():
if node.getRHS() is None:
return False
else:
return self.search(value, node.getRHS())
if value < node.getValue():
if node.getLHS() is None:
return False
else:
return self.search(value, node.getLHS())
def delete(self, value, node=None):
if node is None:
node = self.root
if node.getValue() < value:
return self.delete(value, node.getRHS())
if node.getValue() > value:
return self.delete(value, node.getLHS())
if node.getValue() == value:
if node.getLHS() is not None and node.getRHS() is not None:
nodeMin = self.findMin(node.getRHS())
node.setValue(nodeMin.getValue())
self.delete(nodeMin.getValue(), node.getRHS())
return
parent = node.getParent()
if node.getLHS() is not None:
if node == self.root:
self.root = node.getLHS()
elif parent.getLHS() == node:
parent.setLHS(node.getLHS())
node.getLHS().setParent(parent)
else:
parent.setRHS(node.getLHS())
node.getLHS().setParent(parent)
if node.getRHS() is not None:
if node == self.root:
self.root = node.getRHS()
elif parent.getLHS() == node:
parent.setLHS(node.getRHS())
node.getRHS().setParent(parent)
else:
parent.setRHS(node.getRHS())
node.getRHS().setParent(parent)
return
if node == self.root:
self.root = None
elif parent.getLHS() == node:
parent.setLHS(None)
else:
parent.setRHS(None)
def findMax(self, node=None):
if node is None:
node = self.root
if node.getRHS() is None:
return node
return self.findMax(node.getRHS())
def findMin(self, node=None):
if node is None:
node = self.root
if node.getLHS() is None:
return node
return self.findMin(node.getLHS())
# Breadth탐색을 위해 Queue에다가 isEmpty함수 추가해서 실행 완료
def traverseLevelOrder(self):
ret = []
Q = Queue()
Q.enqueue(self.root)
while not Q.isEmpty():
node = Q.dequeue()
if node is None:
continue
ret.append(node.getValue())
if node.getLHS() is not None:
Q.enqueue(node.getLHS())
if node.getRHS() is not None:
Q.enqueue(node.getRHS())
return ret
# Depth의 3가지 방법 자체에서 오류 발생
# 오류 종류
# 1) 문자열과 리스트가 더할 수 없다는 오류 - 현재 PreDrder, PostOrder 실행할 때 발견
# 2) 앞서와 같이 Nontype object has no attribute "getLHS"오류 발생. - InOrder실행할 때 발견
def traversePreOrder(self, node=None):
if node is None:
node = self.root
ret = []
ret.append(node.getValue())
if node.getLHS() is not None:
ret = ret + self.traverseInOrder(node.getLHS())
if node.getRHS() is not None:
ret = ret + self.traverseInOrder(node.getRHS())
def traverseInOrder(self, node=""):
if node == "":
node = self.root
ret = []
if node.getLHS() != "":
ret = ret + self.traverseInOrder(node.getLHS())
ret.append(node.getValue())
if node.getRHS() != "":
ret = ret + self.traverseInOrder(node.getRHS())
return ret
def traversePostOrder(self, node=None):
if node is None:
node = self.root
ret = []
if node.getLHS() is not None:
ret = ret + self.traverseInOrder(node.getLHS())
if node.getRHS() is not None:
ret = ret + self.traverseInOrder(node.getRHS())
ret.append(node.getValue())
부분적인 코드만 올리면 실행할 떄 불편하실까봐
제가 한 코드 모두 망라해서 올려드려요
이왕 올린김에 피드백 받을 것 받으며, 제가 안된 부분 해결하고 싶기도 하구요..ㅎ
* 강의 수강 PPT에 있는 것에다가 그대로 치고 구현 안되는 것에 추가적으로 수정하려고 헀습니다.
수정사항1) Breadth 탐색시 오류 해결
Queue에 isEmpty()함수가 실행이 되지 않길래 구현시키기 위해 MemberFuction 만들었습니다.
수정사항2) Depth 탐색 시 오류 해결
PreOrder, InOrder, PostOrder을 실행시킬 때 위의 코드 주석처럼 오류가 납니다.
새로히 짜려고 해보고 있는데,, 이 코드에서 오류를 해결 못하니 찜찜해서요.
# Recursion위해 내부 호출 부른 Self.traverseInOrder(node.LHS())에서 오류가 발생한 것 같은데 이를 해결을 못헀습니다 ㅠㅠ
주소를 참조하면서 동시에 Treenode안에 있는 MemberFunction인 getValue()를 활용하면서 빈 리스트에 추가하려고 했는데 더 복잡해지더라고요..
comment