数据结构__二叉搜索树

(1)二叉搜索树定义

/**树节点定义**/

typedef struct BitNode

{

int data;

struct BitNode *lChild,*rChild;

}BiTNode,*BiTree;

/***二叉树的搜索**/

//递归查找二叉树T中的Key是否存在,用指针f指向T的双亲，若查找成功则指针p指向该数据元素节点

//若失败，则指针指向路径上访问的最后一个节点，并返回false,也就是插入数据的位置

bool searchBST(BiTree T,int Key,BiTree f,BiTree *p)

{

if(!T)

{

*p = f;

return false;

}

else if(Key== T->data)

{

*p = T;

return true;

}

else

{

return searchBST(Keydata?T->lChild:T->rChild,Key,T,p);

}

}

/* 插入节点 */

bool insertBST(BiTree *T,int Key)

{

BiTree p,s;

if(!searchBST(*T,NULL,&p))//找插入位置p

{

s = (BiTree) new BiTNode;

s->data = Key;

s->lChild = s->rChild = NULL;

if(!p)//如果插入的事第一个节点

*T = s;

else if(Key< p->data)

p->lChild =s;

else

p->rChild =s;

return true;

}

else

return false;

}

//查找删除节点的位置

bool deleteBST(BiTree *T,int Key)

{

if(!*T)

return false;

else

{

if（Key==(*T)->data）

return Delete(T);

else if(Key<(*T)->data)

return DeleteBST(&(*T)->lChild,Key);

else

return DeleteBST(&(*T)->rChild,Key);

}

}

//具体删除节点操作

//分两种情况考虑，一种情况，就是删除的节点 只有左子树或者右子树，或者啥都没有 这种操作是一样的

//另外一种情况是左右子树都有，当我们找到删除节点的时候，要从其右子树找到一个值最小的节点和当前节点的值交换，然后再删除这个节点 因为这样可以满足删除该节点的二叉树依然是二叉排序树

bool Delete（BiTree * p）

{

BiTree q,s;

if(（*p）->rChild==NULL)

{

q = *p;

p = (*p)->lChild;

delete q;

}

else if((*p)->lChild==NULL)

{

q = *p;

p = (*p)->lChild ;

delete q;

}

else

{

q=*p;

s = p->rChild;

while(s->lChild)

{

q= s;

s = s->lChild;

}

(*p)->data = s->data;//值的替换

if(q!=*p)

q->rChild = s->lChild;

else

q->lChild =s->lChild;

delete s;

}

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!