9.40.c

来自「部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)」· C语言 代码 · 共 29 行

9.40③  在平衡二叉排序树的每个结点中增设一个
lsize域，其值为它的左子树中的结点数加1。试写
一时间复杂度为O(logn)的算法，确定树中第k小的
结点的位置。

实现下列函数：
BiTNode *Ranking(BiTree T, int k)
/* 在含lsize域的平衡二叉排序树T中确定第k小的结点指针 */

二叉树的类型BiTree定义如下：
typedef struct {
    KeyType key;  
    ... ...   // 其他数据域
} ElemType;

typedef struct BiTNode {
    ElemType data;
    BiTNode  *lchild,*rchild;
    int      lsize;
}BiTNode, *BiTree;
BiTNode *Ranking(BiTree T, int k)
/* 在含lsize域的平衡二叉排序树T中确定第k小的结点指针 */
{
 if(!T) return NULL;                             //不存在要求的指针，k小于1或者大于树的总结点数
 if(T->lsize==k) return T;                       //T就是要求结点
 else if(T->lsize>k) return Ranking(T->lchild,k);//在左子树中寻找
 else return Ranking(T->rchild,k-T->lsize);      //在右子树中寻找
}