バイナリ検索ツリーで1レベル上をトラバースする方法は？

Question

私はバイナリ検索ツリーを再帰的に横断しているプログラムを持っています。しかし、いったん特定のノードに到達すると、その親に行き、その2つのノードの間にノードを挿入したいと考えています。だから私はどのように親ノードにアクセスするだろうか？

ありがとうございます。

編集：私は、配列を使用してツリーを作成し ので、例えば：

tree = ['D', 'Does it have 4 legs?', 
     ['D', 'Can you ride it?', ['I','horse'], ['I', 'dog']], 
     ['D', 'Does it have hands?', ['I', 'monkey'],['I', 'bird']]] 

ツリーを横断するため私のコード：

def identify_thing(tree): 
    node_type = tree[0] 
    if node_type == "D": 
    (question, yes_tree, no_tree) = tree[1:] 
    yes_answer = get_yes_no(question) 
    if yes_answer: 
     identify_thing(yes_tree) 
    else: 
     identify_thing(no_tree) 
    elif node_type == "I": 
    name = tree[1] 
    question = "Is it a {}?".format(name) 
    yes_answer = get_yes_no(question) 
    if yes_answer: 
     print("{} Identified!".format(name)) 
    else: 
     print("I don't know what it is.") 
     new_name = get_nonblank_str("What is it?") 
     new_question = get_nonblank_str("Give me a question where yes means 
        a '{}'" " and no means a '{}'".format(new_name, name)) 
    # this is where I am trying to insert the code for updating the tree 

Answer 1

それは本当にあなたがあなたのツリーをデザインする方法に依存します。子供が両親を知っている場合、それはnode = node.parentのように簡単です。ノードが配列に配列されている場合（minheapのように）、親のインデックスはnode = (n - 1) // 2と計算されます。