假设一棵带索引的二叉搜索树，root指向其根结点树中每个结点具有如下形式:
Lsize left data right
其中，Lsize域的值为该结点左子树中的结点个数加1；left，light分别指向该结点的左、右子树，且假设data域和Lsize域为int型。
已给出结点和树的类定义如下：
struct BinaryNode
{……
int Lsize;
int data;
BinaryNode *left;
BinaryNode *right;
BinayNode(int d, int s=1,BinaryNode*L=NULL,BinaryNode*R=NULL） {data=d;Lsize=s;left=L;right=R}//构造函数
～BinayNode(){} //析构函数
}
class BinarySearchTree
{BinarySearchTree(){root=null;}
BinaryNode*FindK(int K,BinaryNode ptr); //查找第K小的关键字的结点
bool insert_NewNode(int X); //插入一个新结点
bool remove_Node(intX); //删除一个结点
private: BinaryNode*root;
}
1)试用C或C++语言写一个在该结构下进行插入一个值为X的新结点的操作
Insert_NewNode。 (4分)
2)写一个 Search函数，搜索这棵带索引的二叉搜索树中第K个小的关键码结点并返回其结点指针。(8分)
3)分析你给出的算法的平均情况下和最坏情况下的渐进时间复杂度(用大O表示法)。(3分)
查看答案和解析【26考研辅导课程推荐】：26考研集训课程,VIP领学计划,26考研VIP全科定制套餐（公共课VIP＋专业课1对1） , 这些课程中都会配有内部讲义以及辅导书和资料，同时会有教研教辅双师模式对大家进行教学以及督学，并配有24小时答疑和模拟测试等，可直接咨询在线客服老师领取大额优惠券。
启航教育热门私房课
MORE小班面授 名额有限 抢先体验
为你推荐
编辑推荐
最新内容
姓名
手机号
