剑指offer之二叉搜索树的第K个节点
【摘要】 1 问题
给定一颗二叉搜索树，请找出其中的第k小的结点。例如， 5 3 7 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
2 分析
二叉树定义：二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵...
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
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）