수퍼리취
30
2022-05-14 15:49:17 작성 2022-05-14 15:50:58 수정됨
0
69

파이썬 txt 파일 입력값으로 받을 때 어려움이 있어 질문드립니다..


안녕하세요 개발자 선배님들 다름아니라 BFS, DFS 문제  관련인데 다른 것은 얼추 구현을 했는데 정작 교수님께서 txt파일로 값들을 주셨는데 이 부분을 어떻게 트리에 삽입을 해야할 지 모르겠습니다... 

txt 파일 예시가 

BFS: 2

15 32  

DFS: 2

5 28 36 -21 -17  

이런 식으로 txt 파일이 주어졌는데  realine()을 사용하기는 했는데  저 값들이 다 str로 나와서 정작 트리에 삽입을 어떻게 해야할 지 모르겠습니다.. 

1. BFS 혹은 DFS 를 선택해서 만약 BFS : 으로 시작한다면 BFS 방식으로 순회 해줘야 하고 DFS: 로 시작하면 DFS 방식으로 순회해준 뒤 저 뒤에 숫자만큼의 인덱스까지의 합을 구하는 것입니다.  이 부분을 풀기 전에 저 순서대로 삽입(insert)이 이루어져야 하는데 삽입을 어떤 식으로 해야할 지 모르겠습니다. 

2. 제가 생각한 방법은 제가 올린 예시 기준 1번째 ,  3번째가 들어갈 값들을 알려주는 것이라 for문으로 홀수 번째만 뽑아서 root.insert(line[홀수번째].split()[] ) 식으로 출력해주는 것이었는데 이 경우 index 가 list 범위 밖에 있다는  indexerror가 발생해서 Try , except로 걸러주려 합니다. 이 부분을 제외하고는 도무지 떠오르지가 않아 진전이 어려운 상태입니다.. 많은 고견 부탁드립니다 ㅜㅜ 

f = open("hw3_input.txt","r") # hw3_input.txt 불러오기 
lst = []
while True:
    line = f.readline().strip()
    if not line: break
    lst.append(line)
out =open("hw3_output.txt","w") # 출력 결과를 output.txt 로 저장하기 위함
f.close()
n = int(lst[0])
class ArrayQueue:

    def __init__(self):
        self.item = []

    def size(self):
        return len(self.item)

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.item.append(item)

    def dequeue(self):
        return self.item.pop(0)

    def peek(self):
        return self.item[0]
class Node:
    
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None

        
class BST:
    
    def __init__(self):
        self.root = None
    
    def insert(self, item):
        new_node = Node(item)
        if self.root is None : 
            self.root = new_node
            return
        current = self.root
        while True:
            parent = current
            if item < current.item : 
                current = current.left
                if current is None:
                    parent.left = new_node
                    break
            else:
                current = current.right
                if current is None:
                    parent.right = new_node
                    break
    def get_min(self):
        while current.left is not None:
            current = current.left
        return current
    def search(self,item):
        current = self.root
        while True:
            if current is None:
                return None
            if current.item > item:
                current = current.left
            elif current.item < item:
                current = current.right
            else:
                return current
    def preorder(self,node):
        if node is not None:
            print(node.item, end=' ')
            self.preorder(node.left)
            self.preorder(node.right)
    def delete(self,item):
        self.root = self.delete_node(self.root,item)
    def delete_node(self,current, item):
        if current is None:
            return None
        if current.item > item:
            current.left = self.delete_node(current.left,item)
            return current
        elif current.item <item:
            current.right = self.delete_node(current.right,item)
            return current
        else:
            if (current.left is None) & (current.right is None):
                return None
            elif current.left is None:
                return current.right
            elif current.right is None:
                return current.left
            else:
                min_node = self.get_min(current.right)
                current.item = min_node.item
                current.right = self.delete_node(current.right,min_node.item)
                return current
    def bfs(self):
        traverse = []
        visitQueue = ArrayQueue()
        if self.root:
            visitQueue.enqueue(self.root)
        while visitQueue.isEmpty()==False:
            node = visitQueue.dequeue()
            traverse.append(node.item)
            
            if node.left:
                visitQueue.enqueue(node.left)
            if node.right:
                visitQueue.enqueue(node.right)
        return traverse무
0
  • 답변 0

  • 로그인을 하시면 답변을 등록할 수 있습니다.