二杈排序树 所谓二杈排序树，指的是一棵空二杈树，或者是一棵具有如下特性的非空二杈树： 1。若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 2。若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 3。左，右子树本身又各是一棵二杈排序树。        二杈排序树的基本操作包括二杈排序树的查找，生成（插入）和删除。        二杈排序树的查找：        在二杈排序树b中查找x的过程为： 1。若b是空树，则搜索失败，否则 2。若x等于b的根结点的数据域之值，则查找成功；否则 3。若x小于b的根结点的数据域之值，则搜索左子树；否则       4。搜索右子树 btree* search(btree *b, ElemType x) {        if(b == NULL)               return NULL;        if(b->data == x)               return b;        if(b->data > x)               return search(b->lchild);        else              return search(b->rchild); } 二杈排序树的生成（插入）        先讨论向一个二杈排序树b中插入一个结点s的算法： 1。若b是空树，则将s所指结点作为根结点插入，否则 2。若s->data等于b的根结点的数据域之值，则什么也不做，或者在结构中增添一个标记，表示该结点 数据出现的次数；否则 3。若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中；否则       4。把s所指结点插入到右子树中 void insert(btree **b, btree *s) {        if(*b == NULL)               *b = s;        else if((*b)->data == s->data)//不做任何插入操作               ;        else if((*b)->data > s->data)//把s所指结点插入到左子树中          insert(&((*b)->lchild), s);        else               //把s所指结点插入到右子树中          insert(&((*b)->rchild), s);    }       生成二杈排序树的过程是先有一个空树b，然后向该空树插入一个个结点实现的，因此， 根据用户输入的一系列正整数（以-1为结束标志）生成一棵二杈排序树的函数如下： void Creat(btree *b) {        ElemType x;        btree *s;               b = NULL;        do        {               scanf("%d", &x);               s = (btree*)malloc(sizeof(btree));               if(s == NULL)               {                      puts("wrong");                      exit(1);               }               s->data = x;               s->lchild = s->rchild = NULL;               insert(&b, s);  //插入一个结点s        } while(x != -1); }   或者直接一个函数搞定： btree* insert(btree *b, char x) {        if(b == NULL)        {               b = (btree*)malloc(sizeof(btree));               if(b == NULL)               {                      puts("wrong");                      exit(1);               }               b->data = x;   //putchar(x);               b->lchild = b->rchild = NULL;        }        else if(b->data == x)//不做任何插入操作               ;        else if(b->data > x)//把s所指结点插入到左子树中           b->lchild = insert(b->lchild, x);        else               //把s所指结点插入到右子树中           b->rchild = insert(b->rchild, x);        return b;   }          二杈排序树的删除：        删除二杈排序树b中一个数据域为x的结点的方法有两种。        第一种过程如下： 1。首先查找到数据域为x的结点p。 2。若p有左子树，找到其左子树的最右边的叶子结点r，用该叶子结点r来替代p，把r的左孩子 作为r的父亲的右孩子。 3。若p没有左子树，直接用p的右孩子取代它。   第二种过程如下： 1。首先查找到数据域为x的结点p。 2。若p有左子树，用p的左孩子取代它；找到其左子树的最右边的叶子结点r，把p的右子树作为r 的右子树。 3。若p没有左子树，直接用p的右孩子取代它。        两种方法各有优劣，第二种操作简单一点点，但均衡性不如第一种，因为它将结点p的右子树 全部移到左边来了。下面将以第一种思路编写代码。 void delnode(btree *b, ElemType x) {        btree *p, *prep, *r, *prer; //p和r指向待比较的结点，prep和prer分别指向它们的前驱结点               p = b;        prer = prep = NULL;        while(p != NULL && p->data != x)//查找数据域为x的结点p        {               if(x < p->data)               {                      prep = p;                      p = p->lchild;               }               else               {                      prep = p;                      p = p->rchild;               }        }        if(p == NULL)               printf("No find!\n");        else if(p->lchild != NULL) //被删结点有左子树        {               r = p->lchild;   //r指向其左子树               while(r->rchild != NULL)//搜索左子树的最右边的叶子结点r               {                      prer = r;                      r = r->rchild;               }               if(prer != NULL)//若r不是p的左孩子，把r的左孩子作为r的父亲的右孩子                      prer->rchild = r->lchild;               r->rchild = p->rchild; //被删结点p的右子树作为r的右子树               if(prep == NULL) //若p为根结点，直接删除根结点               {                      b = r;                      free(p);               }               esle if(p == prep->lchild)//若p为prep的左孩子，把r作为prep的左孩子               {                      prep->lchild = r;                      free(p);               }                   esle   //若p为prep的右孩子，把r作为prep的右孩子               {                      prep->rchild = r;                      free(p);               }            }        else        {               if(prep == NULL)               {                      b = p->rchild;                      free(p);               }               esle if(p == prep->lchild)               {                      prep->lchild = p->rchild;                      free(p);               }                   esle               {                      prep->rchild = p->rchild;                      free(p);               }            } } 

评论