0

I'm currently using the follow code to perform in inorder traversal of a BST. My problem is getting all calculations to stop once the kth smallest is reached.

http://codepad.viper-7.com/XMGcxz

My problem is with the following function

public function _kthSmallest($node, $k){        

    if($node->left != NULL){
        $this->_kthSmallest($node->left, $k);
    }        
    echo $node->data . ' ';
    self::$counter++;
    echo self::$counter . "<br/>";

    /*
    if(self::$counter >= $k){
        return $node->data;
    }        
    */    

    if($node->right != NULL){

        $this->_kthSmallest($node->right, $k);
    }        
}

If I uncomment this code I run into problems because the root node always gets printed.

/*
if(self::$counter >= $k){
    return $node->data;
}        
*/

Any ideas of how can stop after I reach the kth smallest? Currently the function continues through the entire BST.

4

1 に答える 1

1

の場合に戻りますself::$counter > $k。

実際には、その状態になるべきではありません。

関数はノードを返すことを意図しているように見えるので、カウントが小さい場合は NULL を返します。

カウントが等しい場合は、現在のノードを返します。また、再帰が NULL 以外を返した場合は、すぐに同じ値を返します。

于 2013-01-21T02:21:34.773 に答える