数据结构——查找算法的实现与分析（二叉排序树）
实验目的：
1．掌握二叉排序树的创建及查找算法（递归和非递归均可）。
实验要求：
1、 创建一棵二叉排序树，并实现对该二叉排序树的查找算法。
实验过程：
1、 输入一数据序列，根据输入的数据序列创建一棵二叉排序树（二叉链表）；
2、 在已创建的二叉排序树中查找“37”和“66”两个结点，并给出相应的查询结果。
实验报告中给出创建二叉排序树和二叉排序树的查找算法代码。
实验结果：
1、输入数据序列：45，24，53，12，37，93。
2、输出二叉排序树的中序遍历序列：12，24，37，45，53，93；
3、
输入要查找的数据：37， 输出查找的结果：该结点已找到。
输入要查找的数据：93， 输出查找的结果：该结点未找到。
实验分析：
1.对二叉排序树的查找进行性能分析，计算其ASL；
2.列举调试运行过程中出现的错误并分析原因。
要求：
本人从事在线教育十年工作经验现在精心整理了一套从小白到项目实践开发各种学习资料如果你想学想加入我们请关注我加群775356268就可以领取学习资料！！！
(1)程序要添加适当的注释，程序的书写要采用缩进格式。
(2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。
(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。
#include<bits/stdc++.h>
usingnamespacestd;
#defineKeyType int
#defineInfoType int
#defineENDFLAG 0
typedefstruct{
KeyType key;
InfoType otherinfo;
}ElemType;
typedefstructBSTNode{
ElemType data;
structBSTNode*lchild, *rchild;
}BSTNode, *BSTree;
ElemType e;
BSTree S, T;
BSTreeSearchBST(BSTree T, KeyType key){
if((!T) || key == T->data.key)returnT;
elseif(key < T->data.key)returnSearchBST(T->lchild, key);
elsereturnSearchBST(T->rchild, key);
}
voidInsertBST(BSTree &T, ElemType e){
if(!T){
S =newBSTNode;
S->data = e;
S->lchild = S->rchild =NULL;
T = S;
}
elseif(e.key < T->data.key)
InsertBST(T->lchild,e);
elseif(e.key > T->data.key)
InsertBST(T->rchild,e);
}
voidCreatBST(BSTree &T){
T =NULL;
cin>> e.key;
while(e.key != ENDFLAG){
InsertBST(T, e);
cin>> e.key;
}
}
voidInOrderTraverse(BSTree T){
if(T){
InOrderTraverse(T->lchild);
cout<< T->data.key <<" ";
InOrderTraverse(T->rchild);
}
}
intmain(){
cout<<"请输入关键字"<
CreatBST(T);
cout<<"二叉排序树的中序遍历序列："<
InOrderTraverse(T);
intn;
cout<<"输入要查找的数据："<
while(scanf("%d",&n) != EOF && n){
if(SearchBST(T, n))
cout<<"输出查找的结果：该结点已找到。"<
else
cout<<"输出查找的结果：该结点未找到。"<
}
return0;
}
/*
45 24 53 12 37 93 0
*/
