二叉排序树的实现和查找 swustoj

xiaoxiao2021-02-28  14

二叉排序树的实现和查找  1000(ms)  10000(kb)  2257 / 5150 按照给定的关键字集合,建立二叉排序树。在建立的二叉排序树上查找指定的关键字,查找成功,输出找到该关键字比较的次数;查找不成功,输出-1.

输入

关键字个数n; 关键字集合; 要查找的关键字;

输出

查找成功输出比较的次数,否则输出-1。

样例输入

12 25 18 46 2 53 39 32 4 74 67 60 11 74

样例输出

4

提示:二叉排序树根结点大于左结点,小于右结点,这样创建一颗树就好了

        

#include<iostream>

#include<stdlib.h> using namespace std; typedef struct node { int data; struct node *l,*r; }Tree; int flag=0,obj=0;//flag作用判断是否寻找到,obj计算比较次数。 void creat(Tree *&l,int num)//创建二叉搜索树。 { if(l==NULL) { l=(Tree *)malloc(sizeof(Tree)); l->data=num; l->l=l->r=NULL; return ; } if(l->data<num)  creat(l->l,num); else creat(l->r,num); } void fun(Tree *&l,int num) { obj++;//每比较一次计数+1. if(l==NULL) return ; else if(l->data<num) fun(l->l,num); else if(l->data>num) fun(l->r,num); else if(l->data==num) { flag=1; return ; } } int main() { Tree *l; l=(Tree *)malloc(sizeof(Tree)); int n,m; cin>>n; cin>>m; l->data=m; l->l=l->r=NULL; for(int i=1;i<n;i++) { cin>>m; creat(l,m); } cin>>m; fun(l,m); if(flag) cout<<obj; else cout<<"-1"; return 0; }

转载请注明原文地址: https://www.6miu.com/read-2150249.html

最新回复(0)