为了遍历BST:查找 [英] In order BST traversal: find

问题描述

我试图找到二进制搜索树的第k个最小元素，但在使用递归时遇到问题.我了解如何按顺序/后顺序等方式打印树，但无法返回元素的等级.有人可以指出我犯错的地方吗?总的来说，我很难理解树中的递归.

I am trying to find the kth smallest element of binary search tree and I have problems using recursion. I understand how to print the tree inorder/postorder etc. but I fail to return the rank of the element. Can someone point where I am making a mistake? In general, I am having hard time understanding recursion in trees.

这是一个练习，所以我不希望使用内置功能.我有另一种解决方案，当我插入节点时，我跟踪左，右子级的数量，并且该代码运行良好.我想知道是否有可能使用有序遍历进行此操作，因为这似乎是一个更简单的解决方案.

this is an exercise, so I am not looking for using built-in functions. I have another solution where I keep track of number of left and right children as I insert nodes and that code is working fine. I am wondering if it is possible to do this using inorder traversal because it seems to be a simpler solution.

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)

推荐答案

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

You could find the smallets element in the binary search tree first. Then from that element call a method to give you the next element k times.

对于find_smallest_node方法，请注意，您可以按顺序"遍历所有节点，直到达到最小.但是这种方法需要O(n)时间.

For find_smallest_node method, note that you can traverse all the nodes "in-order" until reach to smallest. But that approach takes O(n) time.

但是，您不需要递归即可找到最小的节点，因为在BST中，最小的节点只是最左边的节点，因此您可以遍历这些节点，直到找到没有左子节点的节点，并且花费O(log n)时间:

However, you do not need a recursion to find the smallest node, because in BST smallest node is simply the left most node, so you can traverse the nodes until finding a node that has no left child and it takes O(log n) time:

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):
   ... 

在将节点插入树中时，只需要保留节点的父级即可.

It just requires to keep the parent of the nodes when inserting them to the tree.

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类的实现是此处.上面的文件夹包含它的测试用例，并且可以正常工作.

An implementation of the bst class with the above methods and also def get_next (self, key) function is here. The upper folder contains the test cases for it and it worked.

这篇关于为了遍历BST:查找的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！