X=(BiTree)malloc(sizeof(BiTNode)) f(!Xexit(OVERFLOW) X->data=T->data CopyBiTree(T->lchild, X->lchild) CopyBiTree(T->rchild, X->rchild) Status ExchangeBi Tree(BiTree&T){/将树T各结点的左右孩子互换 BiTree temp if(T)I temp=T->lchild T-Ichild=T->rchild rchild= ExchangeBi Tree(T->lchild) ExchangeBiTree(T->rchild) Status Locate Node(BiTree t, TElemType x, BiTree &p)i //在树T中查找(按先序)第一个结点值等于x的结点,若找到则函数返回TRUE,p带回该结点的地址;若 找不到则函数返回 FALSE,p赋值为NULL if(!T){p=NUL; return False;}//树T为空则p赋空且返回 FALSE else if(T->data=x)p=T: return TRUE: I else if( LocateNode(T-> Child,x,p) return TRUE;/搜索左子树 else if( LocateNode(T- rchild,x,p) return TrUE;//左子树中找不到再搜索右子树 else p=NULL: return FALSE: I Status LocateParent(Bi Tree T, TElemType x, BiTree &parent_p, int &LR) /己知树T中存在某结点值等于x,定位到该结点的双亲结点,若双亲存在(说明x结点非根结点)则 parent p 带回双亲位置,flag为代表是双亲的左孩子,为代表是双亲的右孩子,同时函数返回TRUE:否则函数返回 FALSE if(T->data=x) parent p=NULL; return FAlse;}//值等于x的结点是根结点,无双亲 if(T->lchild! =NULL&&T->Ichild->data==x)parent_p=T: LR=0; return TRUE; else if (T->rchild! =NULL&&T->rchild->data==x)parent_p=T: LR=l: return TRUE: K else f if(T->lchild!=NULL&&LocateParent(T->Child, x, parent p, LR))return TRUE else if(T->rchild! =NULL&&LocateParent(T->rchild, x, parent p, LR))return TRUE else parent_p=NULL; return FALSE; H Status DeleteChild(BiTree &T, TElemType x)I 删除树T中以x为根结点的子树,若存在x结点则删除成功后返回OK,若不存在x结点返回EROR BiTNode p, *parent_ p int LR if( LocateNode(T,x,p){//若树中存在结点x if( LocateParent(T,x, parent_p,LR)/若存在双亲,即x非根结点 if (LR==)DestroyBiTree(parent_p->lchild) else if(LR=1)DestroyBiTree(parent_p->rchild) else Destroy BiTree(T)://若x为根结点,不存在双亲,则删除整颗树,不可直接写T=NULL,为何? return okX=(BiTree)malloc(sizeof(BiTNode)); if(!X)exit(OVERFLOW); X->data=T->data; CopyBiTree(T->lchild,X->lchild); CopyBiTree(T->rchild,X->rchild); } return OK; } Status ExchangeBiTree(BiTree &T){//将树T各结点的左右孩子互换 BiTree temp; if(T){ temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; ExchangeBiTree(T->lchild); ExchangeBiTree(T->rchild); } return OK; } Status LocateNode(BiTree T, TElemType x,BiTree &p){ //在树T中查找(按先序)第一个结点值等于x的结点，若找到则函数返回ＴＲＵＥ,p带回该结点的地址;若 找不到则函数返回ＦＡＬＳＥ ，p赋值为NULL if(!T){ p=NULL;return FALSE;}//树T为空则p赋空且返回FALSE else if(T->data==x){p=T;return TRUE;} else { if(LocateNode(T->lchild,x,p))return TRUE;//搜索左子树 else if(LocateNode(T->rchild,x,p))return TRUE;//左子树中找不到再搜索右子树 else {p=NULL;return FALSE; } } } Status LocateParent(BiTree T,TElemType x,BiTree &parent_p,int &LR){ //已知树T中存在某结点值等于x，定位到该结点的双亲结点,若双亲存在（说明x结点非根结点）则parent_p 带回双亲位置，flag为代表是双亲的左孩子，为代表是双亲的右孩子，同时函数返回ＴＲＵＥ；否则函数返回 FALSE if(T->data==x){parent_p=NULL;return FALSE;}//值等于x的结点是根结点，无双亲 else{ if(T->lchild!=NULL&&T->lchild->data==x){parent_p=T;LR=0;return TRUE;} else if(T->rchild!=NULL&&T->rchild->data==x){parent_p=T;LR=1;return TRUE;} else{ if(T->lchild!=NULL&&LocateParent(T->lchild,x,parent_p,LR))return TRUE; else if(T->rchild!=NULL&&LocateParent(T->rchild,x,parent_p,LR))return TRUE; else {parent_p=NULL;return FALSE;} } } } Status DeleteChild(BiTree &T,TElemType x){ //删除树T中以x为根结点的子树,若存在x结点则删除成功后返回OK，若不存在x结点返回ERROR; BiTNode *p,*parent_p; int LR; if(LocateNode(T,x,p)){//若树中存在结点x if(LocateParent(T,x,parent_p,LR)){//若存在双亲，即x非根结点 if(LR==0)DestroyBiTree(parent_p->lchild); else if(LR==1)DestroyBiTree(parent_p->rchild); } else DestroyBiTree(T);//若x为根结点，不存在双亲,则删除整颗树，不可直接写T=NULL，为何？ return OK; } else