1 //二叉排序树  2 #include
     
        3 using namespace std;  4   5 typedef struct BiTNode  6 {  7     int data;  //结点数据  8     BiTNode *lchild, *rchild; //左右孩子指针  9 }*BiTree; 10  11 //递归查找二叉排序树T中是否存在key 12 //指针f指向T的双亲，初始值为NULL 13 //若查找成功，指针p指向该数据元素结点并返回true 14 //否则指针p指向查找路径上访问的最后一个结点并返回false 15 bool SearchBT(BiTree T, int key, BiTree f, BiTree *p) 16 { 17     if(!T) 18     { 19         *p = f; 20         return false; 21     } 22  23     if(key==T->data) 24     { 25         *p = T; 26         return true; 27     } 28     else if(key
      
       data) 29     { 30         return SearchBT(T->lchild, key, T, p); 31     } 32     else 33     { 34         return SearchBT(T->rchild, key, T, p); 35     } 36 } 37  38 //当二叉排序树T中不存在关键字等于key的数据元素时 39 //插入key并返回true，否则返回false 40 bool InsertBST(BiTree *T, int key) 41 { 42     BiTree p, s; 43     if(SearchBT(*T,key,NULL,&p)) 44         return false; 45     else 46     { 47         s = new BiTNode; 48         s->data = key; 49         s->lchild = s->rchild = NULL; 50         if(!p) 51             *T = s;  //插入s为新的根结点 52         else if(key
       
        data) 53             p->lchild = s; //插入s为左孩子 54         else 55             p->rchild = s; //插入为s的右孩子 56         return true; 57     } 58 } 59  60 //从二叉排序树中删除结点p，并重接它的左右子树 61 bool Delete(BiTree *p) 62 { 63     BiTree q, s; 64     if((*p)->rchild==NULL) //若右子树为空 65     { 66         q = *p; 67         *p = (*p)->lchild; 68         delete q; 69     } 70     else if((*p)->lchild==NULL) //若左子树为空 71     { 72         q = *p; 73         *p = (*p)->rchild; 74         delete q; 75     } 76     else //左右子树均不为空 77     { 78         q = *p; 79         s = (*p)->lchild; 80         while(s->rchild) 81         { 82             q = s; 83             s = s->rchild; 84         } 85         (*p)->data = s->data; 86         if(q!=*p) 87             q->rchild = s->lchild; 88         else 89             q->lchild = s->lchild; 90         delete s; 91     } 92     return true; 93 } 94  95 //若二叉排序树T存在关键字等于key的数据元素时，删除该结点 96 bool DeleteBST(BiTree *T, int key) 97 { 98     if(!*T) 99         return false;100     else101     {102         if(key==(*T)->data)103             return Delete(T);104         else if(key<(*T)->data)105             return DeleteBST(&(*T)->lchild, key);106         else107             return DeleteBST(&(*T)->rchild,key);108     }109 }110 111 void PreOrderPrint(BiTree T)112 {113     if(T==NULL)114         return; 115     cout<
        
         data<<" ";116     PreOrderPrint(T->lchild);117     PreOrderPrint(T->rchild);118 }119 120 int main()121 {122     int a[10] = {
   62,88,58,47,35,73,51,99,37,93};123     BiTree T = NULL;124 125     for(int i=0;i<10;i++)126         InsertBST(&T,a[i]);127     PreOrderPrint(T);128     cout<