首页 > 代码库 > #查找算法#【2】二叉排序树
#查找算法#【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 =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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。