포인터가없는 파이썬으로 이진 검색 트리를 만드는 방법은 무엇입니까?

Question

"이진 트리를 만드는 방법"에 대한 답변을 보았지만 관련 답변이 효과가없는 것 같습니다 !! 이들은 다소 다음과 같은 알고리즘을 기반으로합니다 :

def insert(item, tree): 
    if (item < tree.entry): 
     if (tree.left != None): 
      insert(item, tree.left) 
     else: 
      tree.left = Tree(item) 
    else: 
     if (tree.right != None): 
      insert(item, tree.right) 
     else: 
      tree.right = Tree(item) 

앞에서 언급 한 코드는 Isaac1000에 의해 작성되었지만 다른 것들은 매우 유사합니다. 코드를 작성

insert(item, tree.left) 
insert(item, tree.right) 

사람이 기준을 통과 생각, 대신 사본의 : 문제는 tree.right 또는 tree.left가 함수에 전달 될 때 다음과 같은 통화에서 "삽입"이다 tree.left 또는 tree.right는 실제로 변경되지 않습니다. 마지막으로, 그 기능이나 유사점은 트리의 첫 번째 또는 영 레벨에서만 작동하지만 트리의 n 레벨에서는 작동하지 않습니다. 그렇다면 포인터없이 이진 검색 트리를 만드는 방법은 무엇입니까?

P. 은 내가 파이썬 포인터를 가지고하지 않았 음을 알고 있지만 내가 틀렸다면 알려주세요해서 "포인터없이"라고

@qfiard

"당신이하는 방법으로 변경 가능한 객체를 전달하면, 이 메소드는 동일한 객체에 대한 참조를 가져오고 마음의 즐거움으로 변경시킬 수 있지만 메소드에서 참조를 리바 인하면 바깥 범위는 아무 것도 알지 못하며 완료 후에는 외부 참조가 여전히 유효합니다 원래 대상을 가리 킵니다. "(Blay Conrad)

그 연설로 저를 완전히 분명하게 보았습니다. 내가 트리를 리바 인딩하는 데 익숙해 졌기 때문에 내 코드가 아무런 의미가 없다는 것을 이해했습니다. 왼쪽. 마지막으로

def insert(self, data): 
     if self is None: 
      self = Tree(data) 
     else: 
      if data < self.data: 
       Link.insert(self.left, data) 
      else: 
       Link.insert(self.right, data) 

, 내가 self = Tree(data) 내가 객체를 리 바인드하려고했다 및 외부 범위는 그것에 대해 아무것도 몰라하지 않았다 쓴 : 다음 코드는 지금까지 사용 된 코드이다. 대신 self.right 또는 self.left를 사용할 때 게시 한 절차를 사용하여 리바 인딩하지 않고 개체를 수정하려고하므로 외부 범위가 내 변경 사항을 기억합니다.

Answer 1

파이썬의 인수는 변경 가능한 형식 (목록, 개체 등)에 대한 참조로 인수를 전달하는 것과 비슷한 할당에 의해 전달됩니다. 제목에 대한 자세한 내용은이 stackoverflow 대답을 참조하십시오 : https://stackoverflow.com/a/986145/2887956.

개체를 사용하여 나무를 표현하면 코드가 완벽하게 작동합니다. 다음 코드는 출력

<<None, 0, None>, 1, <None, 2, None>>

class Tree(object): 

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

    def __str__(self): 
     return '<%s, %d, %s>' % (self.left, self.entry, self.right) 

def insert(item, tree): 
    if item < tree.entry: 
     if tree.left is not None: 
      insert(item, tree.left) 
     else: 
      tree.left = Tree(item) 
    else: 
     if tree.right is not None: 
      insert(item, tree.right) 
     else: 
      tree.right = Tree(item) 

root = Tree(1) 
insert(0, root) 
insert(2, root) 
print root 

당신이 당신의 나무를 표현하기 위해 목록을 사용하는 경우 실질적으로 수정할 필요가 있지만 귀하의 알고리즘도 작동합니다.