剑指offer之二叉搜索树的第K个节点

1 问题

给定一颗二叉搜索树，请找出其中的第k小的结点。例如， 5  3  7  2  4  6  8 中，按结点数值大小顺序第三个结点的值为4。

 
2 分析

二叉树定义：二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

具体分析：按照定义，我们不难知道二叉查找树如果按照数的中序遍历，我们可以得到单调递增的排列数，我们需要找到第K个节点，也就是中序遍历树的第K个节点。

我们可以通过递归中序遍历求解答，也可以通过通过栈来实现树的中序遍历


 
3 代码实现

    #include <iostream>
    #include <stdlib.h>
    #include <stack>
     
    using namespace std;
     
     
    typedef struct Tree
    {
        int value;
        struct Tree* left;
        struct Tree* right;
    } Tree;
     
     
    Tree* getNode(Tree* node, int k)
    {
        if (k <= 0)
        {
            std::cout << "输入的k值不合法" << std::endl;
            return NULL;
        }
        int count;
        if (node == NULL)
            return NULL;
        
        getNode(node->left, k);
        //std::cout << "value is " << node->value <<std::endl;
        count++;
        if (count == k)
        {
            return node;
        }
        getNode(node->right, k);
        return node;
    }
     
    Tree* getNode1(Tree* node, int k)
    {
        if (k <= 0)
        {
            std::cout << "输入的k值不合法" << std::endl;
            return NULL;
        }
        if (node == NULL)
            return NULL;
        std::stack<Tree *> stack;
        Tree *p = node;
        int count = 0;
        while (p != NULL || !stack.empty())
        {
            if (p != NULL)
            {
                stack.push(p);
                p = p->left;
            }
            else
            {
                Tree *value = stack.top();
                //std::cout << "value is " << value->value << std::endl;
                count++;
                //这里需要pop函数弹出来，不然永远都是二叉树的最左下角的值
                stack.pop();
                if (k == count)
                {
                    return value;
                }
                p = value->right;
            }
        }
        return NULL;
    }
     
     
    int main() {
       /***    
                    4
               2         6
            1     3   5     7     
        **/
     
        Tree *node1 , *node2 , *node3, *node4, *node5, *node6, *node7;
        node1 = (Tree *)malloc(sizeof(Tree));
        node2 = (Tree *)malloc(sizeof(Tree));
        node3 = (Tree *)malloc(sizeof(Tree));
        node4 = (Tree *)malloc(sizeof(Tree));
        node5 = (Tree *)malloc(sizeof(Tree));
        node6 = (Tree *)malloc(sizeof(Tree));
        node7 = (Tree *)malloc(sizeof(Tree));
        
        node1->value = 4;
        node2->value = 2;
        node3->value = 6;
        node4->value = 1;
        node5->value = 3;
        node6->value = 5;
        node7->value = 7;
        
        node1->left = node2;
        node1->right = node3;
        node2->left = node4;
        node2->right = node5;
        node3->left = node6;
        node3->right = node7;
        
        node4->left = NULL;
        node4->right = NULL;
        
        node5->left = NULL;
        node5->right = NULL;
     
        node6->left = NULL;
        node6->right = NULL;
        
        node7->left = NULL;
        node7->right = NULL;
        
        Tree *result = getNode(node1, 4);
        if (result != NULL)
        {
            std::cout << "result is " << result->value << std::endl;
        }
            Tree *result1 = getNode1(node1, 4);
        if (result1 != NULL)
        {
            std::cout << "result1 is " << result1->value << std::endl;
        }
        return 0;
    }


 
4 运行结果

    result is 4
    result1 is 4

 
5 总结

我们用栈(stack)进行中序遍历的时候，我们不应该一开始就把树的顶部节点压入栈，这个时候基本上后面再在while循环里面做top操作基本上无解，然后我们既然是要执行左 中 右效果，我们需要单独定义一个遍历保存第一个节点，然后依次压入左孩子节点，然后如果是空就不压进去，而要执行获取顶部元素，这个就是我们需要的值，然后还有把这个元素进行弹出来(pop)操作，然后把这个值的右孩子节点压入栈，这样就可以保证是左 中 右打印值的效果。




 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)