함수에서 호출 된 방문 노드는 어떻게 찾을 수 있습니까?

Question

여기에 이진 검색 트리 프로그램이 있습니다. 모든 기능이 마지막 시스템을 제외한 시스템 업로드에서 작동하고 있습니다. 이전 기능을 호출 할 때 방문한 노드를 어떻게 든 찾아야합니다. 어떤 아이디어?

class Node: 

    def __init__(self, value): 
     self.left = None 
     self.right = None 
     self.data = value 

    class BinarySearchTree: 
     def __init__(self): 
      self.root = None 

     def insert(self, value): 
      if self.root is None: 
       self.root = Node(value) 
      else: 
       self._insert(value, self.root) 

     def _insert(self, value, curNode): 
      if value < curNode.data: 
       if curNode.left is None: 
        curNode.left = Node(value) 
       else: 
        self._insert(value, curNode.left) 
      else: 
       if curNode.right is None: 
        curNode.right = Node(value) 
       else: 
        self._insert(value, curNode.right) 

     def fromArray(self, array): 
      for i in range(len(array)-1): 
       value = array[i] 
       self.insert(value) 
       i += 1 


     def search(self, value): 
      if self.root is not None: 
       return self._search(value, self.root) 
      else: 
       return False 

     def _search(self, value, curNode): 
      if value == curNode.data: 
       return True 
      elif value < curNode.data and curNode.left is not None: 
       self._search(value, curNode.left) 
      elif value > curNode.data and curNode.right is not None: 
       self._search(value, curNode.right) 
      else: 
       return False 

     def min(self): 
      curNode = self.root 
      while curNode.left is not None: 
       curNode = curNode.left 
      return curNode 

     def max(self): 
      curNode = self.root 
      while curNode.right is not None: 
       curNode = curNode.right 
      return curNode 

     def visitedNodes(self): 
      pass 

그리고 목록의 노드 값을 반환해야합니다. 당신은 현재의 코드를 수정하지 않으려면

Answer 1

직진 대답은 명시 적으로 각각의 기능에 이성을 상실하고, 각 노드에 visited 플래그를 추가하는 것입니다

def _search(self, value, curNode): 
    curNode.visited = True 
    if value == curNode.data: 
     return True 
    # etc., unchanged 

min 및 max과 동일하고 마지막으로 :

def visitedNodes(self, current=self.root, accumulator=[]): 
    if current == None: 
     return 
    if current == self.root: 
     accumulator = [] 
    if current.visited: 
     accumulator.append(current) 
    visitedNodes(current.left) 
    visitedNodes(current.right) 
    return accumulator 

이것은 단지 하나의 구현이며이를 수행하는 다른 많은 방법이 있습니다. 또한 전체 트리를 가로 지르는이 함수는 이 아니라이 visited 플래그로 설정되어야한다고 가정합니다.

Answer 2

것은, 어쩌면이 당신을 도울 수 있습니다

이

class Node: 
    def __init__(self, value): 
     self.left = None 
     self.right = None 
     self._data = value 
     self.visited = False 
    @property 
    def data(self): 
     self.visited = True 
     return self._data 
    @data.setter 
    def data(self, value): 
     self.visited = False 
     self._data = value 
n = Node(3) 
print(n.visited) 
print(n.data) 
print(n.visited) 

출력 :

False 
3 
True 

이 그런 다음 visitedNodes 방법에 당신이보고해야 할 것 모든 노드의 visited 속성. (느려질 것입니다)

다른 방법은 BinarySearchTree에 새로운 set 속성을 추가하고 노드를 볼 때마다 add 노드를 수동으로 수정하면 코드가 수정됩니다. 다음

class Node: 

    def __init__(self, value): 
     self.left = None 
     self.right = None 
     self.data = value 
     self.visited = False 

과 :하십시오 Node 방문 때