如何在二叉查找树中遍历一个层次？

-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

如何在二叉查找树中遍历一个层次？

回答

相关问题