为了BST遍历：找到

我想找到二叉搜索树的第k个最小元素，并且使用递归时遇到了问题。我知道如何打印树/订单等，但我无法返回元素的排名。有人能指出我犯了什么错误吗？一般来说，我很难理解树中的递归。为了BST遍历：找到

编辑：这是一个练习，所以我不想使用内置函数。我有另一个解决方案，在我插入节点并且代码工作正常的情况下跟踪左侧和右侧儿童的数量。我想知道是否有可能使用inorder遍历来做到这一点，因为它似乎是一个更简单的解决方案。

class BinaryTreeNode: 
    def __init__(self, data, left=None, right=None): 
     self.data = data 
     self.left = left 
     self.right = right 


def traverseInOrder(root,order): 

    if root == None: 

     return 
    traverseInOrder(root.left,order+1) 
    print root.data, 
    print order 

    traverseInOrder(root.right,order) 


""" 
      a 
     / \ 
      b  c 
     /\ /\ 
     d e f g 
    /\ 
    h i 
""" 
h = BinaryTreeNode("h") 
i = BinaryTreeNode("i") 
d = BinaryTreeNode("d", h, i) 
e = BinaryTreeNode("e") 
f = BinaryTreeNode("f") 
g = BinaryTreeNode("g") 
b = BinaryTreeNode("b", d, e) 
c = BinaryTreeNode("c", f, g) 
a = BinaryTreeNode("a", b, c) 

print traverseInOrder(a,0)

来源

2014-01-26 Anastasia

如果这是一个学术活动，使traverseInOrder（或量身定做的目的类似的方法）返回其参观的儿童人数。从那里事情变得更简单。

如果这不是学术问题，请看http://stromberg.dnsalias.org/~dstromberg/datastructures/ - 类似字典的对象都是树，并且支持迭代器 - 所以找到第n个是zip（tree，range（n））的问题。

来源

2014-01-26 05:09:37 dstromberg

嗨，是的，我已经做了另一个练习。我只是想知道是否可以使用inorder遍历来完成它。我实现的另一个解决方案是在插入节点时跟踪左侧和右侧儿童的数量。 – Anastasia

我想知道是否有可能使用中序遍历的简单计数器，并在计数器击中数字k时退出。例如，h会返回1，d会返回2，我会返回3等。所以如果我想要第三小，我会停止当我打印我 – Anastasia

您可以先在二叉查找树中找到smallets元素。然后从该元素调用一个方法给你下一个元素k次。

对于find_smallest_node方法，请注意，您可以遍历所有节点“按顺序”，直到达到最小。但是这种方法需要O（n）次。

但是，您不需要递归来找到最小的节点，因为在BST中最小的节点只是最左边的节点，所以您可以遍历节点，直到找到没有离开子节点的节点，并且它需要O（日志n）时间：

class BST(object): 

    def find_smallest_node(self): 
    if self.root == None: 
     return 
    walking_node = self.root 
    smallest_node = self.root 
    while walking_node != None: 
     if walking_node.data <= smallest_node.data: 
     smallest_node = walking_node 
     if walking_node.left != None: 
     walking_node = walking_node.left 
     elif walking_node.left == None: 
     walking_node = None 
    return smallest_node 


    def find_k_smallest(self, k): 
    k_smallest_node = self.find_smallest_node() 
    if k_smallest_node == None: 
     return 
    else: 
     k_smallest_data = k_smallest_node.data 
    count = 1 
    while count < k: 
     k_smallest_data = self.get_next(k_smallest_data) 
     count += 1 
    return k_smallest_data 


    def get_next (self, key): 
    ...

它只需要在将节点的父节点插入树时保留其父节点。

class Node(object): 
    def __init__(self, data, left=None, right=None, parent=None): 
    self.data = data 
    self.right = right 
    self.left = left 
    self.parent = parent

与上述方法中的BST类的实现，并且还def get_next (self, key)功能是here。上面的文件夹包含它的测试用例，它工作。

来源

2014-06-04 06:06:40

为了BST遍历：找到

回答

相关问题