트리구조 -프로그래밍(파이썬) 과제 해결좀해주세요..

preorder / postorder는 간단히 print부와 재귀호출부의 순서를 바꾸는 것으로 구현할 수 있습니다.

remove 메서드 구현의 경우 상당히 복잡하므로 하단의 최종 코드와 제가 추가로 제공한 주석을 참고하시기 바랍니다.

​

#트리는 노드로 이루어진 자료구조 class Node: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def preorder(self): print(self.value, end='\t') if(self.left != None): self.left.inorder() if(self.right != None):self.right.inorder() def inorder(self): if(self.left != None): self.left.inorder() print(self.value, end='\t') if(self.right != None): self.right.inorder() def postorder(self): if(self.left != None): self.left.inorder() if(self.right != None):self.right.inorder() print(self.value, end='\t') def search(self, value): if(self.value == value): return self elif(self.value > value): if(self.left != None): return self.left.search(value) else : if(self.right != None): return self.right.search(value) def add(self, value): if(self.value == value): return if(self.value > value): if(self.left == None): self.left = Node(value) else : self.left.add(value) else: if(self.right == None): self.right = Node(value) else: self.right.add(value) def remove(self, value): if self is None: return # 더 노드가 없으면 None 반환 if self.value < value: # 우로 재귀호출해 탐색 self.right = self.right.remove(value) elif self.value > value: # 좌로 재귀호출해 탐색 self.left = self.left.remove(value) else: # 지울 값과 노드 내 값이 일치하면 # 왼쪽 자식이 비었으면 우측 자식으로 자신을 대체 if self.left is None: temp = self.right self = None return temp # 오른쪽 자식이 비었으면 좌측 자식으로 자신을 대체 elif self.right is None: temp = self.left self = None return temp else: # 오른쪽 subtree 중 가장 작은(왼쪽) 자식으로 자신을 대체 temp = self.right # 대체할 대상 while temp.left: temp = temp.left # value를 대체하고, self.value = temp.value # 오른쪽 subtree에서 해당 값을 없애버리기 (재귀) self.right = self.right.remove(temp.value) return self def build_tree(data): tree = Node(data[0]) for x in data[1:]: tree.add(x) return tree data = [5, 3, 7, 2, 4, 9, 6] tree = build_tree(data) # 트리 순회 print("중위 순회 :", end=' ') tree.inorder() print() print("====================") print("전위 순휘 : ", end=' ') tree.preorder() # 트리 검색 print("검색 :", end=' ') v = 7 result = tree.search(v) if(result == None): print("트리는 ", v, "값을 갖고 있지 않음") else: print("트리는 ", result.value, "값을 갖고 있음")

​