# 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()를 활용하면서 빈 리스트에 추가하려고 했는데 더 복잡해지더라고요..