7)查找[2]二叉排序树以及查找

 1 #include "iostream"
 2 #include "iomanip"
 3 #include "time.h"
 4 using namespace std;
 5 
 6 #define num 13
 7 
 8 struct Bnode{
 9     int data;
10     Bnode *lchild;
11     Bnode *rchild;
12 };
13 
14 /*
15 *将指针S所指的结点插入到二叉排序树T中
16 */
17 void insert(Bnode * &Tree,Bnode *S)
18 {
19     if(Tree==NULL)//插入到空树时，插入结点为根结点
20     {
21         Tree = S;
22     }else if(S->data<Tree->data){    
23         insert(Tree->lchild,S);//插入到Tree的左子树中
24     }else {
25         insert(Tree->rchild,S);//插入到Tree的右子树中
26     }
27 }
28 
29 /*
30 *二叉排序树的构造
31 */
32 void create_bst(int A[],int n,Bnode *&Tree)
33 {
34     int i=0;
35     Tree = NULL;
36     while(i<n)
37     {
38         Bnode *u = new Bnode;
39         u->data = A[i];
40         u->lchild = NULL;
41         u->rchild = NULL;
42         insert(Tree,u);
43         i++;
44     }
45 }
46 
47 /*
48 *二叉排序树的查找
49 */
50 Bnode *bst_search(Bnode *T,int x)
51 {
52     if((T==NULL)||(T->data = x))
53     {
54         cout<<"Address:"<<T<<",data:"<<T->data <<endl;
55         return T;
56     }
57     else if(x<T->data){
58         return bst_search(T->lchild,x);
59     }else return bst_search(T->rchild,x);
60 }
61 
62 /*
63 *中序输出
64 */
65 void inorder(Bnode *Tree)
66 {
67     if(Tree!=NULL)
68     {
69         inorder(Tree->lchild);
70         cout<<setw(4)<<Tree->data<<" ";
71         inorder(Tree->rchild);
72     }
73 }
74 
75 int main()
76 {
77     Bnode *Tree =new Bnode;
78     time_t start ,end;
79     int A[]={100,60,40,80,70,90,150,120,180,110,130,160,200};
80     cout<<"initialize Array:"<<endl;
81     for(int i=0;i<num;i++)cout<<setw(5)<<A[i];
82     cout<<endl;
83     create_bst(A,num,Tree);//创建二叉树
84     cout<<"中序输出二叉树Tree:"<<endl;
85     inorder(Tree);
86     cout<<endl;
87     start =clock();
88     bst_search(Tree,A[5]);//二叉树查找
89     end = clock();
90     cout<<"time:"<<(double)(end-start)/1000<<"S"<<endl;
91     return 0;
92 }