二叉排序树，是一种规整的二叉树。每个节点的左子树都小于他，每个节点的右子树都大于他。

二叉树的遍历：

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 
      
        2 #include 
       
         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     else54         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     }else73         return false;74 }
       
      

运行示例：