二叉排序樹的插入和刪除

下面的程序實現了二叉排序樹的建立，插入和刪除操作！

#include<iostream>
#include<vector>
using namespace std;
struct LNode{
    int data;
    LNode *lchild;
    LNode *rchild;
};
void buildtree(LNode *root,LNode *q){
    LNode *p=root;
    while(1){
        if(q->data==p->data)
            break;
        else{
            if((q->data)>(p->data)){
                if(p->rchild!=NULL)
                    p=p->rchild;
                else{
                    p->rchild=q;
                    break;
                }
            }
            else{
                if(p->lchild!=NULL)
                    p=p->lchild;
                else{
                    p->lchild=q;
                    break;
                }
            }
        }
    }
}
void del(LNode *root,LNode *q){
    LNode *p=root;
    LNode *r;
    while(1){
        if(p->data==q->data){
            if(p->lchild==NULL&&p->rchild==NULL){
                if(r->lchild==p)
                    r->lchild=NULL;
                else
                    r->rchild=NULL;
                delete p;
                break;
            }
              
              
            if(p->lchild==NULL&&p->rchild!=NULL){
                if(r->lchild==p)
                    r->lchild=p->rchild;
                else
                    r->rchild=p->rchild;
                delete p;
                break;
            }
            if(p->lchild!=NULL&&p->rchild==NULL){
                if(r->lchild==p)
                    r->lchild=p->lchild;
                else
                    r->rchild=p->lchild;
                delete p;
                break;
            }
              
              
            if(p->lchild!=NULL&&p->rchild!=NULL){
                LNode *q;
                if(!p->lchild){
                    q=p->lchild;
                    while(!(q->rchild))
                        q=q->rchild;
                    p->data=q->data;
                    delete q;
                    break;
                }
                else{
                    q=p->rchild;
                    while(!(q->lchild))
                        q=q->lchild;
                    p->data=q->data;
                    delete q;
                    break;
                }
            }
        }
        else{
            if((p->data)>(q->data)){
                r=p;
                p=p->lchild;
            }
            else{
                r=p;
                p=p->rchild;
            }
        }
    }
}
void inorder(LNode *root){
    if(root){
        inorder(root->lchild);
        cout<<root->data<<" ";
        inorder(root->rchild);
    }
}
int main(){
    vector<int> sevc;
    int ch;
    while(cin>>ch&&ch!=0)
        sevc.push_back(ch);
      
    vector<int>::iterator iter;
    iter=sevc.begin();
    LNode *root=new LNode;
    root->data=*iter;
    root->lchild=NULL;
    root->rchild=NULL;
      
    ++iter;
    LNode *p;
    for(;iter!=sevc.end();++iter){
        p=root;
        LNode *q=new LNode;
        q->data=*iter;
        q->lchild=NULL;
        q->rchild=NULL;
        buildtree(p,q);
    }
      
    p=root;
    inorder(p);
    cout<<endl;
      
    cin.ignore();
    p=root;
    cin>>ch;
    LNode *q=new LNode;
    q->data=ch;
    q->lchild=NULL;
    q->rchild=NULL;
    del(p,q);
      
    p=root;
    inorder(p);
    cout<<endl;
      
    delete p;
    delete q;
    delete root;
      
    return 0;
}

本文出自 “菜鳥的進階之路” 博客，請務必保留此出處http://beyond316.blog.51cto.com/7367775/1266364