再帰バイナリツリー検索は、ノードが見つかったときにTrueを返しません。

Question

myTreeは、バイナリツリーを表すリストのリストです。リスト内の各リストについて、要素0は左の子へのポインタを表し、要素1はノードの値を表し、要素2は右の子へのポインタを表す。

myTree = [[1,50,2],[3,27,4],[9,62,10],[5,12,6],[7,35,8],[-1,9,-1],[-1,14,-1],[-1,28,-1],[-1,41,-1],[11,59,12],[13,71,-1],[-1,52,-1],[-1,60,-1],[-1,68,-1]] 


def findNode(item,comparingNode): 
    #print (comparingNode) 
    comparingNode = myTree[comparingNode] 
    if item == comparingNode[1]: 
     print(comparingNode[1]) 
     return True #This is where it is supposed to return True 

    elif item > comparingNode[1]: 
     if comparingNode[2] != -1: 
      print(comparingNode[0],comparingNode[1],comparingNode[2],"comp1") 
      return findNode(item,comparingNode[2]) 
     else: 
      return False 

    else: 
     if comparingNode[0] != -1: 
      print(comparingNode[0],comparingNode[1],comparingNode[2],"comp2") 
      findNode(item,comparingNode[0]) 
     else: 
      return False 


    #print(comparingNode[1]) 




if findNode(9,0) == True: 
    print("found") 

実行すると、それはエラーメッセージを生成せず、プログラムが完了します。検索を実行すると、最後に9が出力されるため、ノード9が明らかに見つかりました。ただし、関数は、デバッガがソース行（9行目）にアクセスしたとしてもTrueを返しません。

Answer 1

あなたはelseパスで返品を忘れました。これは動作します：

def findNode(item,comparingNode): 
    #print (comparingNode) 
    comparingNode = myTree[comparingNode] 
    if item == comparingNode[1]: 
     print(comparingNode[1]) 
     return True #This is where it is supposed to return True 

    elif item > comparingNode[1]: 
     if comparingNode[2] != -1: 
      print(comparingNode[0],comparingNode[1],comparingNode[2],"comp1") 
      return findNode(item,comparingNode[2]) 
     else: 
      return False 

    else: 
     if comparingNode[0] != -1: 
      print(comparingNode[0],comparingNode[1],comparingNode[2],"comp2") 
      return findNode(item,comparingNode[0]) 
     else: 
      return False 

Answer 2

ウィレムは、上記のコメントでラインを示唆したように：

をするように変更する必要があり

findNode(item,comparingNode[0]) 

：

return findNode(item,comparingNode[0]) 

出力は次のようになります。

1 50 2 comp2 
3 27 4 comp2 
5 12 6 comp2 
9 
found 

Answer 3

あなたはちょうどを忘れました210：

if comparingNode[0] != -1: 
    print(comparingNode[0],comparingNode[1],comparingNode[2],"comp2") 
    **** findNode(item,comparingNode[0]) 
else: 
    return False 

別のノート：あなたは== Trueを行うことなくテストすることができます。

if findNode(9,0): 
    print("found")