首页 文章

按顺序进行BST遍历：查找

提问于
浏览 次
1

我试图找到二元搜索树的第k个最小元素，我在使用递归时遇到了问题 . 我理解如何打印顺序/后序等树，但我没有返回元素的等级 . 有人能指出我犯错的地方吗？一般来说，我很难理解树中的递归 .

编辑：这是一个练习，所以我不是在寻找使用内置函数 . 我有另一个解决方案，我在插入节点时跟踪左右儿童的数量，并且该代码工作正常 . 我想知道是否可以使用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)
python binary-search-tree

2 回答

  • 0

    如果这是一个学术练习，请使用traverseInOrder（或为此目的定制的类似方法）返回它访问过的子项数 . 从那里事情变得更简单 .

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

    回复于
  • 0

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

    对于 find_smallest_node 方法，请注意您可以遍历所有节点"in-order"，直到达到最小值 . 但这种方法需要O（n）时间 .

    但是，您不需要递归来查找最小的节点，因为在BST中，最小节点只是最左边的节点，因此您可以遍历节点，直到找到没有左子节点的节点，并且需要O（log 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

    使用上述方法和 def get_next (self, key) 函数的bst类的实现是here . 上层文件夹包含它的测试用例并且它可以工作 .

    回复于

相关问题