题目描述
求二叉搜索树的第k大节点？
算法分析
二叉搜索（排序，查找）树，左子树<根<右子树。那么中序遍历二叉搜索树则为从小到大的序列。
中序遍历一遍二叉搜索树，得到节点个数n，然后第k大节点就是第n-k+1小的节点.
完整代码
#include "二叉排序树.h"//统计树的节点个数
int CountNode(BSTree T)
{if (T == NULL)return 0;return CountNode(T->lchild) + 1 + CountNode(T->rchild);
}//利用中序遍历算法找第i个节点
BSTNode* IthNode(BSTree T, int *pi)
{BSTNode* target = NULL;if (T->lchild != NULL) //处理左子树target = IthNode(T->lchild,pi);if (target == NULL) //处理根节点{if (*pi == 1)//就是当前的根target = T;--*pi;}if (target==NULL && T->rchild != NULL) //处理右子树target = IthNode(T->rchild, pi);return target;
}//得到二叉排序树第k大的节点（需要转为第n-k+1小的节点）
BSTNode* KthNode(BSTree T, unsigned int k)
{//通过中序遍历算法，计算节点个数int n = CountNode(T);if (k <= 0 || k > (unsigned int)n)//参数非法return NULL;int i = n - k + 1;//把第k大转为第i小return IthNode(T,&i);
}int main()
{BSTree T;printf("请输入插入的数据序列,-1表示结束:");CreateBST(&T);树1:45 24 53 12 37 93 -1 树2:12 24 37 45 53 93 24 -1printf("中序遍历这棵二叉排序树(有序):"); InOrder(T); printf("\n"); int k = 1; //int k = 3; BSTNode* p = KthNode(T,k); if (p == NULL) printf("没有找到\n"); else printf("第%d大的数字为:%d\n",k,p->data.key); return 0;
}
本篇完！
