#查找算法#【2】二叉排序树

二叉排序数或者是一棵空树，或者是一棵具有以下性质的二叉树：

（1）若它有左子树，则左子树上所有结点的数据均小于根结点的数据。

（2）若它有右子树，则右子树上所有结点的数据均大于根结点的数据。

（3）左、右子树本身又各是一棵二叉排序树。

这样，在查找的时候，从根节点开始，若查找的元素小于根节点则查找其左子树，否则查找右子树。

例如数据：

代码如下：

 1 #include <stdio.h>
 2 #define ARRAYLEN 10
 3 int source[] = {10,25,4,63,5,8,74,6,24,92};
 4 typedef struct bst
 5 {
 6     int data;
 7     struct bst *left;
 8     struct bst *right;
 9 }BSTree;
10 
11 //向二叉排序树中插入节点
12 void InsertBST(BSTree *t,int key){
13     BSTree *p,*parent,*head;
14 
15     if(!(p=(BSTree *)malloc(sizeof(BSTree *)))){
16         printf("Error:malloc error");
17         exit(0);
18     }
19 
20     p->data = key;
21     p->left = p->right = NULL;
22     
23     head = t;
24     while(head){
25         parent = head;
26         if(key < head->data)
27             head = head->left;
28         else
29             head = head->right;
30     }
31 
32     if(key < parent->data)
33         parent->left = p;
34     else
35         parent->right = p;
36 }
37 
38 //创建二叉排序树
39 void CreateBST(BSTree *t,int data[],int n){
40     int i;
41 
42     t->data = data[0];
43     t->left = t->right = NULL;
44 
45     for(i = 1; i < n ; i++)
46         InsertBST(t,data[i]);
47 }
48 
49 //中序遍历排序二叉树
50 void BST_LDR(BSTree *t){
51     if(t){
52         BST_LDR(t->left);
53         printf("%d ",t->data);
54         BST_LDR(t->right);
55     }
56 }
57 
58 //根据关键字查找元素
59 BSTree *FindKey(BSTree *t,int key){
60     if(!t || key==t->data)
61         return t;
62     if(key<t->data)
63         return FindKey(t->left,key);
64     else
65         return FindKey(t->right,key);
66 }
67 
68 //主函数
69 int main(){
70     int i;
71     BSTree p;
72     int key;    //查找的关键字
73     BSTree *p_find;    
74 
75     printf("排序前:
");
76     for(i = 0 ; i < ARRAYLEN ; i++)
77         printf("%d ",source[i]);
78 
79     CreateBST(&p,source,ARRAYLEN);    
80     printf("
中序遍历:
");
81     BST_LDR(&p);
82 
83     printf("请输入要查找的关键字:");
84     scanf("%d",&key);
85     p_find = FindKey(&p,key);
86     
87     if(p_find)
88         printf("要找到的元素地址为：%x
",p_find);
89 }