数据结构实验报告——二叉查找树

实验六二叉查找树一．问题描述：利用二叉查找树（BST）实现一个动态查找表。二．基本要求(1)使用二叉树（BST）来实现。(2)二叉树使用链式结构（二叉链表）实现。(3)实现BST的构建，查找两个功能。三．实现提示输入：8//BST的节点个数34,76,45,18,26,54,92,65//8个数据45//查找45输出：查找成功3//返回成功和查找时比较的次数34//查找34输出：查找成功1//返回成功和查找时比较的次数100//查找100输出：查找不成功3//返回成功和查找时比较的次数四．源程序：#includeiostreamusingnamespacestd;classNode{public:Node*pLeftChild;Node*pRightChild;intdata;Node(){pLeftChild=NULL;pRightChild=NULL;data=0;}};boolsearchTree(Node*subroot,intdata){if(subroot!=NULL){if(datasubroot-data)returnsearchTree(subroot-pLeftChild,data);elseif(datasubroot-data)returnsearchTree(subroot-pRightChild,data);elseif(data=subroot-data){coutFound!endl;}}else{coutNotFound!endl;returnfalse;}}boolcreatTree(Node**subroot,intdata){if(*subroot!=NULL){if(data(*subroot)-data)creatTree(&((*subroot)-pLeftChild),data);elseif(data(*subroot)-data)creatTree(&((*subroot)-pRightChild),data);}else{*subroot=newNode;(*subroot)-data=data;}returntrue;}voidgoTree(Node*subroot){if(subroot!=NULL){goTree(subroot-pLeftChild);coutsubroot-dataendl;goTree(subroot-pRightChild);}}intmain(){Node*p=newNode;coutPleaseinputendl;intM,N;cinM;inti=0;cinN;p-data=N;while(++iM){cinN;creatTree(&p,N);}goTree(p);return0;}五．测试结果：六．实验心得：1.通过本次试验，我发现自己分析问题不是很全面，忽略掉一些细节。以后分析问题时要仔细考虑，认真分析，避免在细节上犯错误。2.通过这次实验，我发现自己编程能力相当欠缺，尤其是用链表实现。自己以后要勤加练习。