算法与数据结构考研试题精析-第９章算法设计题32

在平衡二叉排序树的每个结点中增设一个lsize域，其值为它的左子树的结点数加１.试写一时间复杂度为Ｏ(logn)的算法，确定树中第k个结点的位置。
算法：当前结点的序列位置等于父结点序列位置+lsize值，
算法关键之处是确定父结点的序列位置：往右搜索时，留下当前结点的序列位置作为父结点序列位置

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef int Status;

typedef struct Node
{
    int data;
    int lsize;
    struct Node *llink,*rlink;
}Node,*Tree;

Status SearchBST(Tree T,int key,Tree f,Tree *p);
Status InsertBST(Tree *T,int e);
void Search_kth(Tree T,int k);
int main()
{
    Tree T;
	T=(Tree)malloc(sizeof(Node));
	T=NULL;
    int e;
    printf("What number you want to search--0 to quit:");
    scanf("%d",&e);
    while(e)
    {
        if(InsertBST(&T,e))
            printf("Done!");
        else
            printf("It`s been inserted already.");
        printf("nWhat number you want to search--0 to quit:");
        scanf("%d",&am

最后

以上就是迷你天空为你收集整理的算法与数据结构考研试题精析-第９章算法设计题32的全部内容，希望文章能够帮你解决算法与数据结构考研试题精析-第９章算法设计题32所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。