二叉排序树，是一种规整的二叉树。每个节点的左子树都小于他，每个节点的右子树都大于他。
二叉树的遍历：
void InOrderTree(BTree *b){ if( !b ) return; InOrderTree(b->lchild); printf("%d ",b->data); InOrderTree(b->rchild); }
二叉树的查找：
int searchTree(BTree *b,int key,BTree *f,BTree *&p){ if(!b){ p = f; return 0; } else if( key == b->data){ p = b; return 1; } else if(key > b->data) return searchTree(b->rchild,key,b,p); else return searchTree(b->lchild,key,b,p); }
二叉树的插入：
bool insertTree(BTree *b,int key){ BTree *p,*s; if(!searchTree(b,key,NULL,p)){ s = (BTree *)malloc(sizeof(BTree)); s->data = key; s->lchild = s->rchild = NULL; if(!b){ b = s; } else if(key < p->data){ p->lchild = s; }else{ p->rchild = s; } return true; }else return false; }
全部代码：
1 #include <stdio.h> 2 #include <stdlib.h> 3 typedef struct bTree{ 4 int data; 5 struct bTree *lchild,*rchild; 6 }BTree; 7 8 void initialTree(BTree *b); 9 bool insertTree(BTree *b,int key); 10 int searchTree(BTree *b,int key,BTree *f,BTree *&p); 11 void InOrderTree(BTree *b); 12 13 int main(){ 14 BTree *b = (BTree *)malloc(sizeof(BTree)); 15 b->data = 5; 16 b->lchild = b->rchild = NULL; 17 initialTree(b); 18 InOrderTree(b); 19 getchar(); 20 return 0; 21 } 22 23 void InOrderTree(BTree *b){ 24 if( !b ) 25 return; 26 InOrderTree(b->lchild); 27 printf("%d ",b->data); 28 InOrderTree(b->rchild); 29 } 30 31 void initialTree(BTree *b){ 32 insertTree(b,5); 33 insertTree(b,3); 34 insertTree(b,6); 35 insertTree(b,2); 36 insertTree(b,1); 37 insertTree(b,8); 38 } 39 int searchTree(BTree *b,int key,BTree *f,BTree *&p){ 40 if(!b){ 41 p = f; 42 printf("++%d\n",p->data); 43 return 0; 44 } 45 else if( key == b->data){ 46 p = b; 47 printf("--%d \n",p->data); 48 printf("找到元素key:%d\n",key); 49 return 1; 50 } 51 else if(key > b->data) 52 return searchTree(b->rchild,key,b,p); 53 else 54 return searchTree(b->lchild,key,b,p); 55 } 56 bool insertTree(BTree *b,int key){ 57 BTree *p,*s; 58 if(!searchTree(b,key,NULL,p)){ 59 printf("%d 没有出现在树中，可以插入在%d之后\n",key,p->data); 60 s = (BTree *)malloc(sizeof(BTree)); 61 s->data = key; 62 s->lchild = s->rchild = NULL; 63 if(!b){ 64 b = s; 65 } 66 else if(key < p->data){ 67 p->lchild = s; 68 }else{ 69 p->rchild = s; 70 } 71 return true; 72 }else 73 return false; 74 }
运行示例：
本文转自博客园xingoo的博客，原文链接：二叉排序树1，如需转载请自行联系原博主。
