二叉排序树

//以下是头文件BST.hvoid Inorder(BTreeNode* BT)//中序遍历 {     if(BT!=NULL){         Inorder(BT->left);         cout < <'('<<BT- > data.key < <','<<BT- > data.rest < <')'<<',';         Inorder (BT- > right);     } }void PrintBTree(BTreeNode* BT) {     if(BT!=NULL)     {         cout < <BT- > data.key;         if(BT->left!=NULL||BT->right!=NULL)         {             cout < <'(';             PrintBTree (BT- > left);             if(BT->right!=NULL)             cout < <',';             PrintBTree (BT- > right);             cout < <')';         }     } }int  Find(BTreeNode* BST,ElemType& item){    if(BST ==NULL)         return 0;        else{            if(item.key ==BST- > data.key)            {                item=BST->data;                return 1;            }            else if(item.key < BST- > data.key)                return Find(BST->left,item);            else                return Find(BST->right,item);        }}//由于此递归算法中的递归调用属于末尾递归，//所以为了避免无效开销在进出系统栈操作上的时//间和使用系统栈的空间，可以把它改写成非递归算法如下：int Find2(BTreeNode* BST,ElemType& item){    while(BST!=NULL)    {        if(item.key==BST->data.key){            item=BST->data;            return 1;        }            else if(item.key < BST- > data.key)                BST=BST->left;            else                BST=BST->right;    }            return 0;}int Update(BTreeNode* BST,const ElemType& item)//这是我自己写的，书上省略了{    while(BST!=NULL)    {        if(item.key==BST->data.key){            BST->data=item;            return 1;        }            else if(item.key < BST- > data.key)                BST=BST->left;            else                BST=BST->right;    }            return 0;}void Insert(BTreeNode* &BST ,const ElemType& item){    if(BST==NULL)    {        BTreeNode* p=new BTreeNode;        p->data=item;        p->left=p->right=NULL;        BST=p;    }    else if(item.key < BST- > data.key)        Insert(BST->left,item);    else        Insert(BST->right,item);}//此算法也属于末尾递归调用，改为非递归算法如下：void Insert2(BTreeNode* &BST ,const ElemType& item){    BTreeNode* t=BST,*parent=NULL;    while(t!=NULL){        parent=t;        if(item.key < t- > data.key)            t=t->left;        else            t=t->right;    }    BTreeNode* p=new BTreeNode;    p->data=item;    p->left=p->right=NULL;    if(parent==NULL)        BST=p;    else if(item.key < parent- > data.key)        parent->left=p;    else        parent->right=p;}void CreateBSTree(BTreeNode* &BST ,ElemType a[],int n)//利用数组中的元素建立二叉排序树{    BST=NULL;    for(int i=0;i < n ;i++)    Insert(BST,a[i]);}int Delete(BTreeNode*& BST,const ElemType& item){    BTreeNode* t =BST,*s=NULL;         while(t! =NULL)     {        if(item.key ==t- > data.key)            break;        else if(item.key < t- > data.key){            s=t;            t=t->left;        }        else{            s=t;            t=t->right;        }    }    if(t==NULL)return 0;    if(t->left==NULL& &t- >right==NULL)    {        if(t==BST)            BST=NULL;        else if(t==s->left)            s->left=NULL;        else            s->right=NULL;        delete t;    }    else if(t->left==NULL||t->right==NULL)    {        if(t==BST){            if(t->left==NULL)                BST=t->right;            else                BST=t->left;    }    else{        if(t==s->left& &t- >left!=NULL)            s->left=t->left;        else if(t==s->left& &t- >right!=NULL)            s->left=t->right;        else if(t==s->right& &t- >left!=NULL)            s->right=t->left;        else if(t==s->right& &t- >right!=NULL)            s->right=t->right;    }    delete t;    }    else if(t->left!=NULL& &t- >right!=NULL)    {        BTreeNode* p=t,*q=t->left;        while(q->right!=NULL){            p=q;            q=q->right;        }        t->data=q->data;        if(p==t)            t->left=q->left;        else            p->right=q->left;            delete q;    }    return 1;}//以下是源文件BST.cpp#include < iostream .h > #include < stdlib .h > #include < conio .h > struct student{    int key;    int rest;};typedef student ElemType;//不能放在结构体student前面struct BTreeNode{    ElemType data;    BTreeNode* left;    BTreeNode* right;};#include"BST.h"void main(){    ElemType a[8]={{30,50},{20,70},{25,80},{23,40},{28,50},{15,90},{60,12},{48,60}};    BTreeNode* bst=NULL;    ElemType x={28};    ElemType y={20,37};    CreateBSTree(bst,a,8);    PrintBTree(bst);cout < <endl ;    cout<<"中序遍历:"<<endl;    Inorder(bst);    cout<<endl;    if(Find(bst,x))        cout<<"查找成功!得到x为:("<<x.key<<","<<x.rest<<')'<<endl;//注间此行的x.rest    if(Update(bst,y)){        cout<<"更新成功:"<<endl;        Inorder(bst);    }    cout<<endl;    Delete(bst,x);    Delete(bst,y);    cout<<"删除关键字为28和20的元素后的中序遍历为:"<<endl;    Inorder(bst);    cout<<endl;    getch();} /*http://f2.9612.org//vcpp/webinfo/WebInfoBata1.asp QQ群：34409541 讨论网页  34409326 讨论JAVA 已满 34408784 讨论VC++  34409699 讨论VC++  9143041 讨论MFC编程  10614204 讨论C#  10613030 讨论Win32编程  10613067 讨论游戏开发  18779860 讨论JAVA  */