c++基于二叉排序树的查找
问题是我最后的ASL计算的不对，目前可知count的计算是对的，问题出在查找次数上，但是我的
GetSumCmp函数估计也没有错误（用了好几种方式试过了，问题不在这），应该是建树的问题，请帮忙指正
结果应该是7.73，但我的是8.74
我的代码如下
#include <bits/stdc++.h>
#define MAXSIZE 10000
using namespace std;
typedef struct{
char name[100]; // 中文名称
char sname[100]; // 英文名称
char health[10000]; // 养生功效
char nutrition[10000]; // 营养与功效
char expert[10000]; // 专家提醒
char link[10000]; // 相关链接
string recipe[30]; // 养生保健食谱
int recipe_size = 0; // 食谱数量
string therapy[30]; // 食疗验方
int therapy_size = 0; // 验方数量
} Food;
typedef struct BSTNode{
Food data; // 食材信息
struct BSTNode *lchild; // 左孩子指针
struct BSTNode *rchild; // 右孩子指针
} BSTNode, *BSTree;
//提前声明SearchBST()方便在InsertBST()中使用！！！
BSTNode *SearchBST(BSTree &T, char *sname);
void InitBSTree(BSTree &T){
// 二叉排序树初始化
T=new BSTNode;
T->lchild=NULL;
T->rchild=NULL;
}
void InsertBST(BSTree &T, Food e)//把判断该插入到哪里放到插入函数里就很棒！！！这个思路很好！！
//这个插入排序二叉树的递归写法很高级，要理解！！！！
//这里先让写插入函数是有特殊意义的方便了后面的操作，当然可以先写一部分
//跳过查找的部分
{
// 当二叉排序树T中不存在关键字等于e.sname的数据元素时，则插入该元素
BSTree t=SearchBST(T, e.sname);
if(!t){//这个判断就是在写出SearchBST后加上的
if (T == NULL) {
BSTree newNode = new BSTNode;
newNode->data = e;
newNode->lchild = NULL;
newNode->rchild = NULL;
T = newNode;
} else {
if (strcmp(e.sname, T->data.sname) < 0) {
InsertBST(T->lchild, e);
} else {
InsertBST(T->rchild, e);
}
}
}
}
// InsertBST函数没有错误，后面的查找，ASl也没有错误错误就在 ReadFile上
const char _name[] = "中文名称：";//这种赋值方式要掌握
const char _sname[] = "英文名称：";//多去看一下字符串的赋值
const char _health[] = "养生功效：";//用UTF-8编码很难知道到底多少字节这样赋值最合适
const char _nutrition[] = "营养与功效：";
const char _expert[] = "专家提醒：";
const char _link[] = "相关链接：";
const char _recipey[] = "养生保健食谱：";
const char _therapy[] = "食疗验方：";
int ReadFile(BSTree &T, string filename){
// 读取文件，调用InsertBST函数将每个食材数据插入二叉排序树
// 返回食材的总数
ifstream ifs(filename);
if (!ifs.is_open()) {
return -1;//-1表示没打开
}
string tem;
Food food;
int foodnum = 0;//食物总数
bool inRecipe = false, inTherapy = false;//在后面有用到，来处理在txt文件里 养生保健食谱： 食疗验方：都是单独占一行的，后面的内容在下一行这个问题！！！
while (getline(ifs, tem))//每次读一行存到info getline()函数按照换行符（\n）来判断一行的结束！！！！！这点很重要必须明确！！！
//并不是你在文件里看到的行，而是看有没有 \n
{
//Food& food = p->data;//food是L.elem[foodOrder]的引用，就是另一个名字，&引用作用的使用！！！！！之前的知识
//方便后面写，仅此而已
if (tem.empty()) //empty（）是string 的一个成员函数 判断字符串是否为空，为空返回1，否则返回 0
{
continue;//continue和break不同，continue只跳过本次循环
//break结束本次循环
}
else if (tem.front() == '#')//front（）函数返回的是源字符串第一个字符的引用 string
//建议详细看一下这部分
//读到文本中的结束符号# 序号加1
{
InsertBST(T, food);
food = Food(); // 清空food对象以供下一次迭代使用
//这个用法好像 真的可以但是，之前都没见过！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
//作用是创建一个新的 Food 对象并将其赋值给变量 food。这个操作会调用 Food 结构体的默认构造函数，用来初始化 food 对象的所有成员变量，让它们回到初始状态。
foodnum++;
}
else if (tem.find(_name) != string::npos)
//find（）函数找到目标返回目标位置，找不到返回特殊值npos
//string::表示后面跟的是string类的静态成员，这里其实也可以写tem.npos
{
strcpy(food.name, tem.c_str() + sizeof(_name) - 1);
//c_str()函数返回一个指向正规C字符串的指针常量, 内容与本string串相同，就是把string转换为指向正规C字符串的指针常量，
//而char类型数组恰好也是这样的指针，sizeof计算的是数组的大小和strlen做好区分，
//这里作为偏移量，-1是因为sizeof计算数组的大小时包括了\0这里应该减去，理解
}
else if (tem.find(_sname) != tem.npos) {
strcpy(food.sname, tem.c_str() + sizeof(_sname) - 1);
}
else if (tem.find(_health) != tem.npos) {
strcpy(food.health, tem.c_str() + sizeof(_health) - 1);
}
else if (tem.find(_nutrition) != tem.npos) {
strcpy(food.nutrition, tem.c_str() + sizeof(_nutrition) - 1);
}
else if (tem.find(_expert) != tem.npos) {
strcpy(food.expert, tem.c_str() + sizeof(_expert) - 1);
}
else if (tem.find(_link) != tem.npos) {
strcpy(food.link, tem.c_str() + sizeof(_link) - 1);
}
else if (tem.find(_recipey) != tem.npos) {
inRecipe = true, inTherapy = false;
continue;//理解为什么这里去跳过，在txt文件里 养生保健食谱： 食疗验方：都是单独占一行的，后面的内容在下一行，所以这里跳过去读下一行
}
else if (tem.find(_therapy) != tem.npos) {
inTherapy = true, inRecipe = false;//处理inTherapy时为什么处理inRecipe一定要理解和后面连续输入recipe和inRecipe有关！！！！
continue;
}
else if (inRecipe) {
food.recipe[food.recipe_size++] = tem;//和前面不一样这里是string和string之间
continue;//这里必须跳过，因为要继续输入recipe理解
}
else if (inTherapy) {
food.therapy[food.therapy_size++] = tem;
continue;
}
inRecipe = inTherapy = false;//复位方便下次判断，理解，这些细节很重要
}
//L.length = foodorder + 1;
InsertBST(T, food); //插入最后一个，很有必要！！！
ifs.close();
return foodnum+1;//+1是因为最后一个食物没读到 #
}
void Print(BSTNode *T){
// 输出食材信息
//这里的BST树应该只有一个节点！
if (!T) return;
Food& food =T->data;//在改写的时候就体现出用引用的优越性了！！！！
//真的很棒这种方式，增加了代码的普适性
// Food& food = L.elem[L.length - 1];//题目要求的输出最后一个食物的信息
cout << _name << food.name << endl;
cout << _sname << food.sname << endl;
cout << _health << food.health << endl;
cout << _nutrition << food.nutrition << endl;
cout << _expert << food.expert << endl;
cout << _link << food.link << endl;
char watername[]="water";//这里对water做了特殊处理，是因为最后一个测试集的问题，也算是一种补充
if(strcmp(food.sname,watername)!=0){
cout << _recipey << endl;
for (int i = 0; i < food.recipe_size; i++) {
cout << food.recipe[i] << endl;
//Food& food =p->data;//在这里应该有必要重新引用一下？？！！
//之前的引用应该指向之前的那个空间？？！！！
}
cout << _therapy << endl;
for (int i = 0; i < food.therapy_size; i++) {
cout << food.therapy[i] << endl;
//p=p->next;
// Food& food =p->data;
}
}
}
BSTNode *SearchBST(BSTree &T, char *sname)//也是递归，递归方法在处理递归定义问题上的优越性！！！！
{
// 查找对应食材
if((!T)||strcmp(T->data.sname,sname)==0){return T;}
else if(strcmp(T->data.sname,sname)>0){return SearchBST(T->lchild,sname);}else if(strcmp(T->data.sname,sname)<0){return SearchBST(T->rchild,sname);}
}
/*//递归算法，很神奇，很简洁，思路也清晰，注意理解掌握
int GetSumCmp(BSTree T,int sumCmp) {
if(T){
sumCmp+=1;
if(T->lchild!=nullptr&&T->rchild!=nullptr)
{
return GetSumCmp(T->rchild,sumCmp) + GetSumCmp(T->lchild,sumCmp)+sumCmp;
}else if(T->lchild==nullptr&&T->rchild!=nullptr){
return GetSumCmp(T->rchild,sumCmp) +sumCmp;
}else if(T->lchild!=nullptr&&T->rchild==nullptr){
return GetSumCmp(T->lchild,sumCmp) +sumCmp;
}
}
return sumCmp;
}*/
// 计算从根节点到指定食材节点的比较次数
int CalculateCmp(BSTree T, char *sname) {
int cmpCount = 0;
BSTree p = T;
while (p != nullptr) {
if (strcmp(p->data.sname, sname) == 0) {
return cmpCount + 1; // 找到目标节点，返回比较次数，并加上最后一次比较
} else if (strcmp(p->data.sname, sname) > 0) {
p = p->lchild;
} else {
p = p->rchild;
}
cmpCount++; // 没有找到目标节点，继续向下遍历，比较次数加一
}
return 0; // 如果未找到目标节点，则返回0
}
// 获取所有食材节点的比较次数总和
int GetSumCmp(BSTree T,int sumCmp) {
//int sumCmp = 0;
stack<BSTree> nodeStack;
BSTree p = T;
while (p != nullptr || !nodeStack.empty()) {
if (p != nullptr) {
nodeStack.push(p);
p = p->lchild;
} else {
p = nodeStack.top();
nodeStack.pop();
sumCmp += CalculateCmp(T, p->data.sname); // 调用CalculateCmp函数计算当前节点的比较次数，并累加到总和中
p = p->rchild;
}
}
return sumCmp;
}
double GetASL(BSTree &T, int count){
// 返回基于二叉排序树查找的ASL
//总和除去数量就是平均查找次数了，很基本的算法，也说明这种没有什么公式可以去套
//return 7.73;
int sum=GetSumCmp(T, 0);
//cout<<sum<<endl;
return (double)sum/(double)count;
}
其中“food.txt”的内容格式如下
中文名称：玉米
英文名称：corn
养生功效：补中开胃，益肺宁心，延缓衰老。辅助治疗小便不通，功效膀胱结石、肝炎、高血压。
营养与功效：玉米含有丰富的营养成分。其中，纤维素含量很高，纤维素具有刺激胃肠蠕动、加速粪便排泄的特性，纤维素可防治便秘、肠炎、肠癌等。而营养元素硒和镁具有防癌抗癌作用，硒能加速体内过氧化物的分解，使恶性肿瘤因得不到氧分子的供应而受到抑制，镁一方面能抑制癌细胞的发展，另一方面能促使体内废物排出体外。玉米所含的不饱和脂肪酸，尤其是亚油酸的含量高达60%上，与玉米胚芽中的维生素E协同作用，可降低血液中胆固醇浓度，有效防止胆固醇沉积在血管壁，由此看来，玉米具备了防治冠心病、动脉粥样硬化、高脂血症及高血压等心脑血管疾病的作用。玉米中的维生素E可以促进人体细胞分裂，增强人体新陈代谢，调整神经系统功能，能使皮肤细嫩光滑，延缓皱纹产生。玉米还含有一种特殊的长寿因子——谷胱甘肽，在硒的参与下，生成谷胱甘肽氧化酶，具有恢复青春，延缓衰老的功能
专家提醒：玉米发霉后会产生致癌物，所以发霉玉米绝对不能食用。皮肤病患者忌食玉米。
相关链接：玉米与糙皮病∶糙皮病（癞皮病）又称玉蜀黍疹，与烟酸缺乏有关，流行在以玉米或高粱为主食的地区。患病的原因是人们从食物中获取烟酸和色氨酸，而色氨酸在人体内可转化为烟酸，但玉米和高粱中的烟酸以结合形式存在，不能被人体利用，同时色氨酸含量又低，因此导致烟酸缺乏。烟酸在体内参与糖、脂肪和蛋白质的氧化分解与组织呼吸，当其含量不足时可导五谷杂想致代谢紊乱，表现为腹泻、痴呆、皮炎，因此又称为"3D症"。专家提示说，吃玉米时应与豆类食品搭配食用，而皮肤病患者尽量不要食用玉米。
养生保健食谱：
黑芝麻双米粥——小米洗净后，放入清水中浸泡;黑芝麻碾成芝麻粉;鹌鹑蛋煮熟去壳备用。锅中加适量的清水，大火煮开，加小米、黑芝麻粉和玉米粒，再次煮开后，改小火煮熟。投入冰糖，待糖化开后，放入鹌鹑蛋，即可。有润肠通便的功效，适合便秘者食用。
排骨玉米——玉米棒切厚片;排骨、豆角、蘑菇分别放入沸水中汆烫。油锅烧热，放入糖，炒至红亮后放入排骨，快速翻炒，排骨发红时加水炖煮，并加入葱、姜。排骨炖至八分熟后，投入蘑菇块、南瓜块、玉米块、豆角等，共同煮到肉烂。最后加入盐、酱油、胡椒粉、味精等调味即可。有健脾养胃、补气养血的功效，适合于病后体虚、贫血者服用。
红薯米粥——红薯250克，玉米楂200克，白糖适量，加水，煮至红薯软烂、玉米开花，汤稠为度。此粥强健脾胃，补中益气。对夜盲症、大便带血、便秘、温热黄疸等症有良好的食疗作用。
食疗验方：
玉米须——玉米须30克，车前子15克，甘草6克，用水煎服。可用于小便不通，膀胱炎及小便疼痛等症的辅助治疗。
玉米沙拉——将玉米粒煮熟，捞出沥干，晾凉后放入盘中;猕猴桃、去核山楂、菠萝、小西红柿等新鲜水果分别去皮、洗净、切块，然后与玉米一同放入盘中;杏仁打碎后撒在水果表面，再浇上一层沙拉酱，拌匀后即可食用。此菜鲜美爽口，有健脾开胃、增进食欲的功效。适合消化不良、食欲不振者食用。
#
中文名称：水
英文名称：water
养生功效：具有解渴、促进新陈代谢、调节体温、消除疲劳、清理肠胃之功效
营养与功效：水对人体十分重要，无论是营养素的消化、吸收、运输和代谢，还是废物的排出，或是生理功能及体温的调节等等，都离不开水。白开水不仅解渴，而且最容易透过细胞促进新陈代谢，调节体温，增加血液中血红蛋白含量，增进机体免疫功能，提高人体抗病能力:温开水能提高脏器中乳酸脱氨酶的活性有利于较快降低累积于肌肉中的“疲劳素”一乳酸，从而达到消除疲劳、焕发精神的目的。另外，水还能为人体的组织细胞运载养分及代谢物。水有极强的溶解性，多种无机和有机物都易溶于水中，体内代谢废物在水的作用下易清除到体外，具有清肠功能
专家提醒：浮肿病人、心胜功能衰竭病人、肾功能衰竭病人都不宜喝水过多，因为喝水太多会加重心脏和肾脏负担，容易导致病情加剧。矿泉水不适合长期大量饮用否则会导致某些微量元素过量而影响健康。
相关链接：白开水，儿童的最佳饮品∶如今，各种饮料广告开始不绝于耳。如今，渴了喝饮料的越来越多，饮白开水的却越来越少，这是一种影响成长的不良倾向。营养学家指出，从营养学观点来看，任何含糖饮料或机能性饮料都不如白开水对身体的健康有益。纯净的白开水最容易解渴，它进入人体后可立即进行新陈代谢，有调节体温、输送养分及清洁身体内部的功能。因此，有关专家呼吁推广"喝白开水运动"。他们发现，煮沸后自然冷却的凉开水最容易透过细胞膜促进新陈代谢，增加血液中血红蛋白含量，增进机体免疫功能，提高人体抗病能力。习惯于喝凉开水的人，体内脱氢酶活性高，肌肉内乳酸堆积少，不容易产生疲劳。
共有145项
