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
