二叉查找树源码实现-白红宇

二叉查找树源码实现

阅读量：5059 次

发布时间：2019-06-12

本文共 3478 字，大约阅读时间需要 11 分钟。

 1. 二叉查找树的性质
 是一个空树，或者满足：
 1.如果左子树不空，那么左子树所有节点的值都小于根节点的值。
 2.如果右子树不空，那么右子树所有节点的值都大于根节点的值。
 3.它的左右子树也分别是一个二叉查找树。可以看出，二叉查找树是一个递归的定义（树本身就是递归的定义。）
 
 如果中序遍历之，那么得到的一定是一个递增有序的数列
 二叉排序树用于查找，其过程类似于二分查找：先是根节点与待查找的key比较，如果相等，返回根节点。否则根据相应的大小关系递归地在左（右）子树中继续查找，直到查找成功或者查找失败返回。
 2. 节点结构

 typedef struct BSTNode   {       int key;       struct BSTNode *lchild,*rchild;   }BSTNode,*BSTree;

3. 节点插入

//二叉排序树的插入——递归实现 void InsertBST(BSTree &DT,BSTNode *p) {     if(DT==NULL)         DT=p;     else if((DT->key) > (p->key))         InsertBST(DT->lchild,p);     else         InsertBST(DT->rchild,p); }

4. 节点删除

//二叉排序树结点的删除 void DeleteBST(BSTree &DT,BSTNode *p) {
    //要删除结点p，f是p的双亲     BSTNode *f;     BSTNode *q,*fq;     if(!(p->lchild)&&!(p->rchild))//第一种情况：p是叶子结点     {         if(f->lchild==p)//p是左孩子             f->lchild=NULL;         else//p是右孩子             f->rchild=NULL;         q=p;     }     else if(!(p->rchild))//第二种情况：（1）p只有左子树     {         if(f->lchild==p)             f->lchild=p->lchild;         else             f->rchild=p->lchild;         q=p;     }     else if(!(p->lchild))//第二种情况：（2）p只有右子树     {         if(f->lchild==p)             f->lchild=p->rchild;         else             f->rchild=p->rchild;         q=p;     }     else //第三种情况：p既有左子树又有右子树     {
   //用p的中序后继来代替p         fq=p;//fq是q的双亲         q=p->rchild;    //右边最左 或者左边最右

while(q->lchild)         {
    //遍历找到p的中序后继             fq=q;             q=q->lchild;         }         p->key=q->key;         if(fq==p)             fq->rchild=q->rchild;         else             fq->lchild=q->rchild;     }     delete q; }

5. 二叉树构建

//二叉排序树的构造 void CreateBST(BSTree &DT,int n) {     int i,j;     int r[100];     BSTNode *s;     DT=NULL;//这里一定要将DT置空，表示刚开始的时候是空树，不置空的话，编译器分配的DT是非空的     for(j=0;j
     
      >r[j];     for(i=0;i
      
       key=r[i];         s->lchild=NULL;         s->rchild=NULL;         InsertBST(DT,s);     } }

6. 二叉树查找

//二叉排序树的搜索——递归实现 BSTNode * SearchBST(BSTree &DT,int k) {     BSTNode *p;     p=DT;     if(DT==NULL)         return NULL;     else if(p->key==k)         return p;     else if(p->key>k)         return SearchBST(p->lchild,k);     else         return SearchBST(p->rchild,k); }

7. 查找最小值

//查找二叉查找树的最小结点BSTNode * BSTreeMinimum(BSTree &DT){    BSTNode *x = DT;    while(x->lchild != NULL){        x = x->lchild;    }    return x;}

8. 查找最大值

//查找二叉查找树的最大结点BSTNode * BSTreeMaxMum(BSTree &DT){    BSTNode *x = DT;    while(x->rchild != NULL){        x = x->rchild;    }    return x;}

9. 查找前驱结点

节点的前驱：根据定义，前驱节点是中序遍历二叉查找树时位于该节点的正前边的一个节点。

1. 如果节点有左子树。那么前驱一定位于左子树中，且是左子树的最大节点

如图所示（45节点的前驱为左子树的最大值37）：

2. 节点没有左子树。那么节点的前驱应该是中序遍历二叉查找树的直接前驱。

看下图：24号节点的前驱是哪个节点（往前找第一个比24小的节点）？

我们可以这样找，指针不停的向上移动（即node *y = x->parent）,直到x是y的右子树为止（因为如果是左子树，父节点只能位于该节点的后边，不可能是前驱）。

//查找二叉查找树某结点的前驱结点BSTNode *BSTreePrecessor(BSTNode *x){    if(x->lchild != NULL)        return BSTreeMaxMum(x->lchild);    BSTNode *y = x->parent;    while(y != NULL && x == y->lchild){        x = y;        y = y->parent;    }    return y;}

10. 查找后驱节点

节点的后继：根据定义，后继节点是中序遍历二叉查找树时位于该节点的正后边的一个节点。这里有几种情况：

1. 如果节点有右子树。那么后继一定位于右子树中，且是左子树的最小节点

2.如果节点没有右子树。与查找前驱类似。

指针不停的向上移动（即node *y = x->parent）,直到x是y的左子树为止（因为如果是右子树，父节点只能位于该节点的前边，不可能是后继）。

//查找二叉查找树某结点的后继结点BSTNode *BSTreeSuccessor(BSTNode *x){    if(x->rchild != NULL)        return BSTreeMinimum(x->rchild);    Node *y = x->parent;    while(y != NULL && x == y->rchild){        x = y;        y = y->parent;    }    return y;}

转载于:https://www.cnblogs.com/sankuaiqian/archive/2012/10/06/2712906.html

你可能感兴趣的文章