加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

数据结构__二叉搜索树

发布时间:2020-12-15 04:53:04 所属栏目:百科 来源:网络整理
导读:(1)二叉搜索树定义 /**树节点定义**/ typedef struct BitNode { int data; struct BitNode *lChild,*rChild; }BiTNode,*BiTree; /***二叉树的搜索**/ //递归查找二叉树T中的Key是否存在,用指针f指向T的双亲,若查找成功则指针p指向该数据元素节点 //若失败,

(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;

}

}

(编辑:李大同)

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

    推荐文章
      热点阅读