95.png

    1. /*
    2.     编写一个递归算法，在一棵有n个节点的、随机建立起来的二叉排序树上查找第k小的元素，并返回指向该节点的指针，要求算法的平均
    3.     时间复杂度为O(logn)。二叉排序树的每个节点中除了data、lchild、rchild等数据成员外，增加一个count成员，保存以该节点为根的
    4.     子树的节点个数
    5.     分析：
    6.         这里要求时间复杂度为O(ln)，我们就不能采用常规的方法了，这里我们需要利用递归的思想，将各种情况罗列清楚
    7.         一、t->lchild 为空
    8.         ①如果t->rchild 非空 且 k=1，那么根据二叉排序树的特性 t即为第k小
    9.         ②如果t->rchild 非空 且 k!=1，那么第k小的数肯定在右子树中
    10.         二、如果t->lchild 非空
    11.         ①如果t->lchild->count ==k-1,那么t即为第k小
    12.         ②如果t->lchild->count > k-1,那么第k小在左子树
    13.         ③如果t->lchild->count < k-1,那么第k小在右子树，寻找第k-(t->lchild->count +1)小的元素
    15.         这道题的那点就在于对问题的分析，我们很容易就遗漏某些情况，导致代码逻辑有问题，需要注意
    18. */
    20. typedef struct node {
    21.     int data;
    22.     int count;//子树节点个数
    23.     struct node *left, *right;
    24. }Tree;
    25. #define _CRT_SECURE_NO_WARNINGS
    26. #include <stdio.h>
    27. #include <stdlib.h>
    29. Tree *create(Tree *T) {//先序创建一颗排序二叉树
    30.     int data;
    31.     printf("请输入当前节点值：data=");
    32.     scanf("%d", &data);
    33.     getchar();
    34.     if (data != -1) {
    35.         T = (Tree *)malloc(sizeof(Tree));
    36.         T->data = data;
    37.         T->left = NULL;
    38.         T->right = NULL;
    39.         T->left = create(T->left);
    40.         T->right = create(T->right);
    41.     }
    42.     return T;
    43. }
    44. int getCount(Tree *T) {//统计每个节点的以它为根的子树上的节点个数
    45.     if (!T)return 0;
    46.     int lcount, rcount;
    47.     lcount = getCount(T->left);
    48.     rcount = getCount(T->right);
    49.     T->count = lcount + rcount + 1;
    50.     return lcount + rcount + 1;
    51. }
    52. Tree *findKth(Tree *T, int k) {
    53.     if (k<1 || k>T->count)return NULL;
    54.     if (!T->left) {
    55.         if (k == 1) return T;
    56.         else return findKth(T->right, k - 1);
    58.     }
    59.     else {
    60.         if (T->left->count == k - 1) return T;
    61.         if (T->left->count > k - 1) return findKth(T->left, k);
    63.         if (T->left->count < k - 1) return findKth(T->right, k - (T->left->count + 1));
    64.     }
    65. }
    66. int main() {
    67.     Tree *T = (Tree *)malloc(sizeof(Tree));
    68.     Tree *p;
    69.     int k = 5;
    70.     T = create(T);
    71.     getCount(T);
    72.     p = findKth(T, k);
    73.     if (p) {
    74.         printf("第 %d 小的节点值为 %d",k,p->data);
    75.     }
    76.     return 0;
    77. }