bst에 대한 삽입 기능이 작동하지 않습니다.

Question

누가 재귀 부분을 도와 드릴까요? 필자는 불필요한 부분을 생략했지만 그 기능이 작동하지 않으면 생략했습니다.

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

def insert(Node,value): 
    if Node is None: 
     Node=node(value) 
    else: 
     if value<Node.data: 
##   if Node.left is None: Node.left=node(value) 
##   else: insert(Node.left,value) 
      insert(Node.left,value) 
     else: 
##   if Node.left is None: Node.left=node(value) 
##   else: insert(Node.left,value) 
      insert(Node.right,value) 

Answer 1

빈 브랜치에 대해 새 node 인스턴스를 만들어야하기 때문에.

In [17]: badTree = node(10) 

In [18]: badTree.data 
Out[18]: 10 

In [20]: badTree.left.data 
---------------------------------------------------------------------- 
AttributeError      Traceback (most recent call last) 
<ipython-input-20-3cb52def2967> in <module>() 
----> 1 badTree.left.data 

AttributeError: 'NoneType' object has no attribute 'data' 

In [21]: badTree.right.data 
---------------------------------------------------------------------- 
AttributeError      Traceback (most recent call last) 
<ipython-input-21-b6f1267c9d29> in <module>() 
----> 1 badTree.right.data 

AttributeError: 'NoneType' object has no attribute 'data' 

이의 우리가 badTree에 요소를 삽입 할 경우 어떻게되는지 보자 다음 REPL에

def insert(Node, value): 
    print(Node) 
    if Node is None: 
    Node=node(value) 
    else: 
    if value<Node.data: 
     insert(Node.left,value) 
    else: 
     insert(Node.right,value) 

:

는의가 Node 매개 변수의 값을 인쇄, 모두 정의를 어떻게되는지 보자 :

In [22]: insert(badTree, 2) 
<__main__.node object at 0x7f706bf34d30> 
None 

In [23]: badTree.left.data 
---------------------------------------------------------------------- 
AttributeError      Traceback (most recent call last) 
<ipython-input-23-3cb52def2967> in <module>() 
----> 1 badTree.left.data 

AttributeError: 'NoneType' object has no attribute 'data' 

그 요소,하지만 왜? badTree에서 left과 right 브랜치는 모두 None (비어 있음)입니다. 즉, Node 주를 참조하지 않으므로 새 값을 재귀 적으로 추가 할 수 없으므로 새 트리를 만들어야합니다. 이것은 우리가 Node.left에 새로운 객체를 할당하기 전에 insert(Node.left, value)를 호출하는 경우, 전화를 해당 될 것입니다 insert(None, value) (이 우리가 badTree에 insert를 호출 할 때 None, 당신은 그것을 볼 수있는 값) insert에 재귀 적으로 호출 None = node(value)를 실행, 어떤 아무것도하지 않을 것이다.

In [25]: newTree = node(4) 

In [26]: insert(newTree, 10) 
<__main__.node object at 0x7f706bf30668> 

In [27]: insert(newTree, 12) 
<__main__.node object at 0x7f706bf30668> 
<__main__.node object at 0x7f706bf30a58> 

이제 우리는 메모리 주소의 추적을 유지하는대로, 더 이상 실패하지 않음을 참조하십시오 REPL에

def insert(Node, value): 
    print(Node) 
    if Node is None: 
    Node = node(value) 
    else: 
    if value < Node.data: 
     if Node.left is None: 
     Node.left = node(value) 
     else: 
     insert(Node.left, value) 
    else: 
     if Node.right is None: 
     Node.right = node(value) 
     else: 
     insert(Node.right, value) 

: 우리는 대신이 정의를 사용하면 어떻게됩니까

따라서 우리는 삽입 (in-place)을 할 수있는 객체 (트리)를 참조 할 수 있습니다.