再帰バイナリ検索ツリーの挿入

Question

ツリーに複数の値を挿入しようとするとエラーが発生します。ツリーのさまざまなレベルで使用可能なリーフの複数を埋めることができるようにしたいと思います。ここに私のコードは次のとおりです。

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 

私はかなり上記のエラーを理解していません。私はツリーキーの値を別の値と比較していると信じていますが、なぜそれが整数を求めているのかわかりません。どんな助けでも大歓迎です。

ありがとうございます！

Answer 1

あなたのベースケースは、kの代わりに{"key" : k, "left" : None, "right" : None}である必要があります。

ツリー内の各ノードを辞書として定義しているので、このデータ構造を常に尊重する必要があります。

最初の挿入後、文字列"hello"はノードになりますが、これはすでに間違っています。次に、2番目の挿入を試みると、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)