二叉排序树算法

 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③左、右子树本身又各是一棵二叉排序树。

   上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。

下面就是二叉排序树的插入、删除、查找算法。

#include <iostream>
using namespace std;

typedef struct  {
 unsigned int key1;
 unsigned int key2;
}KeyType;

typedef struct 
{
 // somethings user define ;
 
 
}BSTNode;

typedef struct
{
 KeyType key;
 
 BSTNode node;
 
}BSTree;

int compkey(KeyType x,KeyType y)
{
 int ret ;
 if((x.key1 == y.key1) && (x.ke2 == y.key2))
  ret = 0;
 else
  if((x.key1 > y.key1) || (x.key1 == y.key1) && (x.key2 > y.key2) )
   ret = 1;
  else
   ret =-1;
  
}

void InsertBST(BSTree *Tptr，KeyType key)
{ 
 //若二叉排序树 *Tptr中没有关键字为key，则插入，否则直接返回
 BSTNode *f,*p=*TPtr; //p的初值指向根结点
    while(p)
 { 
  //查找插入位置
  //树中已有key，无须插入
  if(compkey(p->key,key) == 0)return;
  
  f=p; //f保存当前查找的结点
  
  p=(compkey(key,p->key)<0 ? p->lchild:p->rchild; //若key<p->key，则在左子树中查找，否则在右子树中查找
 } //endwhile
 
 //生成新结点
 p=(BSTNode *)malloc(sizeof(BSTNode));
 
 p->key.key1 = key.key1;
 p->key.key2 = key.key2;
 
 p->lchild = p->rchild=NULL;
 
 //原树为空
 if(*TPtr==NULL) 
  *Tptr=p;
 else 
  if(compkey(key,f->key)<0)
   f->lchild=p;
  else f->rchild=p;
} //InsertBST

/**************************************************************************
②删除*p结点的三种情况
(1)*p是叶子(即它的孩子数为0)
    　无须连接*p的子树，只需将*p的双亲*parent中指向*p的指针域置空即可。

(2)*p只有一个孩子*child
    　只需将*child和*p的双亲直接连接后，即可删去*p。
  注意：
    　*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或
 右孩子，故共有4种状态。

(3)*p有两个孩子
    　先令q=p，将被删结点的地址保存在q中；然后找*q的中序后继*p，并在查找过程
 中仍用parent记住*p的双亲位置。*q的中序后继*p一定是 *q的右子树中最左下的结
 点，它无左子树。因此，可以将删去*q的操作转换为删去的*p的操作，即在释放结
 点*p之前将其数据复制到*q中，就相当于删去了*q.
***************************************************************************/

void DelBSTNode(BSTree *Tptr，KeyType key)
{
 //在二叉排序树*Tptr中删去关键字为key的结点
 BSTNode *parent=NULL,*p=*Tptr,*q,*child;
 while(p)
 {
  //从根开始查找关键字为key的待删结点
  if(compkey(p->key,key) == 0) break;//已找到，跳出查找循环
  
  parent=p;  //parent指向*p的双亲
  p=(compkey(key , p->key)<0)? p->lchild:p->rchild;
  //在关p的左或右子树中继续找
 }
 if(!p) return; //找不到被删结点则返回
 
 q=p;  //q记住被删结点*p
 //*q的两个孩子均非空，故找*q的中序后继*p
 if(q->lchild && q->rchild) 
  for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);
  
 //现在情况(3)已被转换为情况(2)，而情况(1)相当于是情况(2)中rchild=NULL的状况
 child=(p->lchild)? p->lchild:p->rchild;
  
 //若是情况(2)，则child非空；否则child为空
 if(!parent) //*p的双亲为空，说明*p为根，删*p后应修改根指针
  *Tptr=child;
 else  //若是情况(1)，则删去*p后，树为空；否则child变为根
 { //*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下
  if(p==parent->lchild) //*p是双亲的左孩子
   parent->lchild=child; 
  else parent->rchild=child; //*child作为*parent的左孩子

  //*child作为 parent的右孩子
  if(p!=q) //是情况(3)，需将*p的数据复制到*q
  {
   q->key.key1=p->key.key1;
   q->key.key2=p->key.key2;
  }
  //若还有其它数据域亦需复制
 } //endif
 free(p); //释放*p占用的空间
} //DelBSTNode

BSTNode *SearchBST(BSTree T,KeyType key)
{ //在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NUll
    if(T==NULL || (compkey(key,T->key)==0)) //递归的终结条件
  return T;//T为空，查找失败；否则成功，返回找到的结点位置
 if(compkey(key,T->key)<0)
  return SearchBST(T->lchild,key);
 else
  return SearchBST(T->rchild,key);//继续在右子树中查找
} //SearchBST 

 

 

 

 

此处有非递归版本

http://www.cnblogs.com/ljphhj/archive/2012/02/25/2367821.html