2017-10-28 6 views
2

트리에 여러 값을 삽입하려고 할 때 오류가 발생합니다. 트리의 다양한 레벨에서 사용할 수있는 리프를 여러 개 채울 수 있기를 바랍니다. 이 같은재귀 바이너리 검색 트리 삽입

tree = { 
    'key' : 'root', 
    'left': { 
     'key': 'something', 
     'left': None, 
     'right': { 
      'key': 'something', 
      'left': { 
       'key': 'somthing', 
       'left': None, 
       'right': None 
      }, 'right': { 
       'key': 'something', 
       'left': None, 
       'right': None 
      } 
     } 
    }, 'right': { 
     'key': 'something', 
     'left': { 
      'key': 'Something', 
      'left': 
      { 
       'key': 'something', 
       'left': None, 
       'right': None 
      }, 'right': None 
     }, 'right': { 
      'key': 'something', 
      'left': None, 
      'right': None 
     } 
    } 
} 

def insert(tree, k): 
    if tree['key'] == None: 
     tree['key'] = k 
    else: 
     if tree['key'] > k: 
      if tree['left'] == None: 
       tree['left'] = k 
      else: 
       insert(tree['left'], k) 

     if tree['key'] < k: 
      if tree['right'] == None: 
       tree['right'] = k 
      else: 
       insert(tree['right'], k) 

insert(tree, "hello") 
insert(tree, "data science") 

오류 내가 갖는 같습니다 : 나는 확실히 위의 오류를 이해하지 못하는

--------------------------------------------------------------------------- 
TypeError         Traceback (most recent call last) 
<ipython-input-114-d826085e4673> in <module>() 
    71 
    72 insert(tree, "hello") 
---> 73 insert(tree, "data science") 
    74 #insert(tree, "jerry") 
    75 #insert(tree, "apple") 

<ipython-input-114-d826085e4673> in insert(tree, k) 
    59     tree['left'] = k 
    60    else: 
---> 61     insert(tree['left'], k) 
    62 
    63   if tree['key'] < k: 

<ipython-input-114-d826085e4673> in insert(tree, k) 
    59     tree['left'] = k 
    60    else: 
---> 61     insert(tree['left'], k) 
    62 
    63   if tree['key'] < k: 

<ipython-input-114-d826085e4673> in insert(tree, k) 
    52 
    53 def insert(tree, k): 
---> 54  if tree['key'] == None: 
    55   tree['key'] = k 
    56  else: 

TypeError: string indices must be integers 

여기 내 코드입니다. 저는 트리 키의 값을 다른 값과 비교하고 있다고 믿지만, 왜 정수를 요구하는지 모르겠습니다. 어떤 도움이라도 대단히 감사 할 것입니다.

감사합니다.

+0

BTW, 그것은'오히려 =='보다는'is'와'None' 테스트를 수행하는 것이 일반적이다. 'None' 객체가 하나뿐이기 때문에 이와 같은 ID 테스트를 사용하는 것이 안전합니다. –

답변

1

기본 케이스는 k 대신 {"key" : k, "left" : None, "right" : None}이어야합니다.

트리의 각 노드를 사전으로 정의 했으므로이 데이터 구조를 항상 존중해야합니다.

첫 번째 삽입 후 "hello" 문자열이 이미 잘못되었습니다. 그런 다음 두 번째 삽입을 시도하면 insert 함수가 실제로 "문자열"인 "노드"에서 호출됩니다.


def insert(tree, k): 
    if tree['key'] == None: 
     tree['key'] = {"key":k, "left":None, "right":None } 
    else: 
     # should insert on left 
     if tree['key'] > k: 
      if tree['left'] == None: 
       tree['left'] = {"key":k, "left":None, "right":None } 
      else: 
       insert(tree['left'], k) 
     # should insert on right 
     if tree['key'] < k: 
      if tree['right'] == None: 
       tree['right'] = {"key":k, "left":None, "right":None } 
      else: 
       insert(tree['right'], k)