Wie durchläuft man eine Ebene in einem binären Suchbaum?

Question

Ich habe ein Programm, in dem ich einen binären Suchbaum rekursiv durchquere. Aber sobald ich zu einem bestimmten Knoten komme, möchte ich zu seinem Elternknoten gehen und einen Knoten zwischen den beiden einfügen. Wie würde ich also auf den Elternknoten zugreifen?

Vielen Dank.

Edit: ich einen Baum erstellt ein Array verwendet wird, so zum Beispiel:

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']]] 

Mein Code durch den Baum zum Verfahren:

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

Es hängt wirklich davon ab, wie Sie Ihren Baum entworfen . Wenn Kinder ihre Eltern kennen, dann ist es so einfach wie node = node.parent. Wenn die Knoten in einem Array (wie einer Minheap) angeordnet sind, kann der Index des übergeordneten Elements als node = (n - 1) // 2 berechnet werden.