如何在二叉查找樹中遍歷一個層次？

-1

我有一個程序，我在遞歸遍歷二叉搜索樹。但是，一旦我到達特定的節點，我想要轉到其父節點並在兩者之間插入一個節點。那麼我將如何訪問父節點？如何在二叉查找樹中遍歷一個層次？

謝謝。

編輯：我使用數組，創造了樹，以便例如：

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

來源

2017-02-22 guddu

這取決於您正在使用的「二叉查找樹」的特定實現。有很多可能性。你在使用哪一個？ –

歡迎來到StackOverflow。請閱讀並遵守幫助文檔中的發佈準則。 [最小，完整，可驗證的示例]（http://stackoverflow.com/help/mcve）適用於此處。在發佈您的MCVE代碼並準確描述問題之前，我們無法爲您提供有效的幫助。 StackOverflow不是一個編碼或教程服務。 – Prune

這真的取決於你如何設計你的樹。如果孩子知道他們的父母，那麼它就像node = node.parent一樣簡單。如果節點排列成一個數組（如minheap），則可以計算出父節點的索引爲node = (n - 1) // 2。

來源

2017-02-22 01:34:03

如何在二叉查找樹中遍歷一個層次？

回答

相關問題