바이너리 검색 트리에서 한 레벨 위로 이동하는 방법은 무엇입니까?

Question

나는 이진 검색 트리를 통해 재귀 적으로 탐색하는 프로그램을 가지고있다. 그러나 특정 노드에 도달하면 부모 노드로 이동하여 두 노드 사이에 노드를 삽입하려고합니다. 그러면 부모 노드에 어떻게 접근합니까?

감사합니다.

편집 : 나는, 배열을 사용하여 트리를 만들어 그래서 예를 들면 :

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으로 계산 될 수 있습니다.