1 #include "stdafx.h" 2 #include 
     
       3 #include 
      
        4 #include
       
         5 using namespace std; 6  7  8 /* 9 二叉排序树:又称为二叉查找树，它或者是一棵空树，或者具有如下性质:10 1.若他的左子树不空,则左子树上所有结点的值均小于它的根结点的值.11 2.若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值.12 3.它的左右子树也分别为二叉排序树.13 如中序遍历,则可获得有序序列.14 */15 16 typedef struct BiTNode17 {18     int data;19     struct BiTNode *lchild,*rchild;20 }BiTNode,*BiTree;21 22 //二叉排序树的查找23 //指针f指向T的双亲，其初始调用值为NULL24 //若查找成功,则指针P指向该数据元素结点，并返回1;25 //否者指针p指向查找路径上访问的最后一个结点并返回0;26 int SearchBST(BiTree T,int key,BiTree f,BiTree *p)27 {28     if(!T)29     {30         *p = f;31         return 0;32     }33     else if(key==T->data)34     {35         *p = T;36         return 1;37     }38     else if(key
        
         data)39     {40         return SearchBST(T->lchild,key,T,p);41     }42     else43         return SearchBST(T->rchild,key,T,p);44 45 }46 //二叉排序树的插入47 //当二叉排序树T中不存在关键字等于key的数据元素时48 //插入key并且返回1,否者返回0;49 int InsertBST(BiTree *T,int key)50 {51     BiTree p,s;52     if(!SearchBST(*T,key,NULL,&p))//如果没有找到该key53     {54         s=(BiTree)malloc(sizeof(BiTNode));55         s->data = key;56         s->lchild = s->rchild = NULL;57         if(!p)58             *T=s;59         else if(key
         
          data)60             p->lchild=s;61         else 62             p->rchild=s;63         return 1;64     }65     else66         return 0;67 }68 69 int _tmain(int argc, _TCHAR* argv[])70 { 71     72 73     return 0 ;74 }