剑指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)操作，然后把这个值的右孩子节点压入栈，这样就可以保证是左 中 右打印值的效果。

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/102473256