首页 > 代码库 > #查找算法#【2】二叉排序树

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

2024-07-13 12:14:14   230人阅读

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

（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 =http://www.mamicode.com/ 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         else29             head = head->right;30     }31 32     if(key < parent->data)33         parent->left = p;34     else35         parent->right = p;36 }37 38 //创建二叉排序树39 void CreateBST(BSTree *t,int data[],int n){40     int i;41 42     t->data = http://www.mamicode.com/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     else65         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("排序前:\n");76     for(i = 0 ; i < ARRAYLEN ; i++)77         printf("%d ",source[i]);78 79     CreateBST(&p,source,ARRAYLEN);    80     printf("\n中序遍历:\n");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\n",p_find);89 }


联系
我们