实验题目:
二叉查找树
[实验目的]
验证二叉查找树相关算法。二叉查找树是一棵可为空的二叉树,若非空则其所有结点之关键 词互异,且中根遍历形成按关键词递增序排列的结点序列。二叉查找树中的任一结点P,它的 左子树中结点的关键词都小于P的关键词,而右子树中结点的关键词都大于P的关键词,并且 结点P的左右子树也都是二叉查找树。
[实验内容及要求]
1. 依次输入int型数数值序列,每输入一给定数值K ,如果K不在二叉查找树中,则在树的 适当位置插入包含K的一个新结点,并输出此二叉查找树的中根遍历序列。
2. 如果K在二叉查找树中,则输出其所在层数,以及此二叉查找树的中根遍历序列。
函数部分:
typedef struct bstree{ int data; struct bstree* left; struct bstree* right; }bst,*pbst; int str2int(string str){ int data_int=0; if(str[0]=='-'){ for(int i=1;i<str.length();i++) { data_int*=10; data_int+=(int(str[i])-48);//string 转 int } return -data_int; }else{ for(int i=0;i<str.length();i++) { data_int*=10; data_int+=(int(str[i])-48);//string 转 int } } return data_int; } void Root_traversal(pbst head){ //中根遍历
if(head==NULL) return; Root_traversal(head->left); cout<<head->data<<' '; Root_traversal(head->right); } pbst Insert(pbst t,int data,int &stage){ //插入节点 if (t == NULL) { t = (pbst)malloc(sizeof(bst)); t->left = t->right = NULL; t->data = data; return t; } if (data < t->data){ stage++; t->left = Insert(t->left, data,stage); } else if(data > t->data){ stage++; t->right = Insert(t->right, data,stage); } cout<<"element "<<data<<" is in stage "<<stage<<endl; return t; } pbst Createbstree(vector<int>data){ //创建树 int stage=0; pbst head=NULL; for (int i = 0; i < data.size(); i++){ stage=0; head = Insert(head, data[i],stage); Root_traversal(head); cout<<endl; } return head; }
调用部分:
string d; vector<int>data; cout<<"please input data(to stop input *):"; cin>>d; while(d[0]!='*'){ data.push_back(str2int(d)); cout<<"please input data(to stop input *):"; cin>>d; } pbst head=Createbstree(data); Root_traversal(head);