이진 검색 트리에서 가장 낮은 K 값을 인쇄합니다.

Question

이진 검색 트리에서 가장 낮은 k 값을 인쇄하는 방법을 알아 내려고하고 있습니다.

현재

def kthSmallestBST(node,k, count): 
    if node == None or count == k: 
     return 
    else: 
     kthSmallestBST(node.left, k, count) 
     count += 1 
     print node.data 
     kthSmallestBST(node.right, k, count) 
     count += 1 


kthSmallestBST(BST, 3, 0) 

내 출력 단순히 당신이에서 발견 얼마나 많은 요소를 알 수 있도록 조금 상황을 타개 할 필요가

Answer 1

중위 전체 트리를 인쇄 : 나는하는 데 문제가

코드는 방법을 중지 재귀 호출 함수가 추가 된 요소의 수를 반환하도록하십시오. 또한 재귀 호출과 현재 노드의 요소 사이의 수를 확인해야합니다. 같은

뭔가 : count의 값

def kthSmallestBST(node, k, count): 
    if node == None or count == k: 
     return 0 
    else: 
     count += kthSmallestBST(node.left, k, count) 
     if(count == k) 
      return count 
     print node.data 
     count += 1 
     count += kthSmallestBST(node.right, k, count) 
     return count 

Answer 2

변경 호출자까지 다시 전파되지 않습니다.

def kthSmallestBST(node,k, count): 
    if node is None or count >= k: 
     return 0 
    else: 
     count += kthSmallestBST(node.left, k, count) 
     if count < k: 
      print node.data 
      count += 1 
     count += kthSmallestBST(node.right, k, count) 
     return count 

은 또한 당신이 k 및 count 모두 필요하지 않습니다주의 : 당신은 새로운 수를 반환해야합니다. count을 제거하고 count 대신을 감소시키고 k을 0과 비교하십시오 (count 대신). 여기에 당신이 무엇을 얻을 :

def kthSmallestBST(node, k): 
    if node is None or k <= 0: 
     return 0 
    k = kthSmallestBST(node.left, k) 
    if k > 0: 
     print node.data 
     k -= 1 
    k = kthSmallestBST(node.right, k) 
    return k 

Answer 3

그것은 오히려 "함수형 프로그래밍"솔루션,하지만 한 가지 방법이 바로 최초의 K를 취할 itertools를 사용하여 다음 순서로 (느리게) 트리의 노드를 생성하는 것입니다.

def inorder(tree): 
    if not tree: return 
    for node in inorder(tree.left): yield node 
    yield tree 
    for node in inorder(tree.right): yield node 

def least(tree, k): 
    return itertools.islice(inorder(tree), k) 

파이썬 3을 사용하는 경우 "yield from"을 사용하면이 솔루션을 더 짧게 만들 수 있습니다.

Answer 4

import unittest 

class BST(object): 

    def __init__(self, key): 
     self.key = key 
     self.left = None 
     self.right = None 


def get_kth_smallest_keys(node, k): 
    """Return, as a list, `k` smallest keys in a binary search tree rooted at `node`. 

    """ 
    smallest = [] 
    _get_kth_smallest_keys(node, k, smallest) 
    return smallest 

def _get_kth_smallest_keys(node, k, smallest): 
    """A helper function. Appends nodes to the given list, `smallest`, and stop 
    when k reaches 0. 

    Returns the number of nodes appended to said list. 

    """ 
    if node is None or k == 0: 
     return 0 
    # first, recurse left, and we get the number of nodes appended to the list by that call 
    nk = _get_kth_smallest_keys(node.left, k, smallest) 
    # if that number already reduces our counter to zero, we fail fast, returning that same number 
    if k - nk <= 0: 
     return nk 
    # otherwise, we can still append this node's key to the list 
    smallest.append(node.key) 
    # then we recurse right, with a counter that is less 1 (our append) and less nk (appended by the left recurse) 
    nnk = _get_kth_smallest_keys(node.right, k - 1 - nk, smallest) 
    # our return value is the sum of our append (1) and the appends from both recurse calls 
    return nk + 1 + nnk 


class BSTTest(unittest.TestCase): 

    def test_smallest_keys(self): 
     root = BST(10) 
     root.left = BST(6) 
     root.right = BST(15) 
     root.left.right = BST(8) 
     root.right.right = BST(20) 

     self.assertEquals(get_kth_smallest_keys(root, 0), []) 
     self.assertEquals(get_kth_smallest_keys(root, 1), [6]) 
     self.assertEquals(get_kth_smallest_keys(root, 3), [6, 8, 10]) 
     self.assertEquals(get_kth_smallest_keys(root, 5), [6, 8, 10, 15, 20]) 
     self.assertEquals(get_kth_smallest_keys(root, 6), [6, 8, 10, 15, 20]) 


if __name__ == '__main__': 
    unittest.main()