仙人球论坛

注册

 

发新话题 回复该主题

数据结构查找3二叉排序树 [复制链接]

1#
北京哪家医院可以治疗白癜风 http://baidianfeng.39.net/bdfby/yqyy/

一棵二叉排序树应该具备的条件:

①若左子树不为空,则左子树上所有结点都应小于根节点

②若右子树不为空,则右子树上所有结点都应大于根节点

③它的左右子树也分别为二叉排序树

关于树的定义很多时候都是递归定义

何为序?

开始比较后,有四种可能

a.aim==T-data查找到,结束

b.aimT-data小于,进入左子树

c.aimT-data大于,进入右子树

d.T=NULLreturn查找不到

二叉排序树的找查

//二叉排序树查找BiNode*SearchBST(BiNode*T,Keytypekey){//查找成功返回结点指针if(!T

T-data==key)returnT;//返回NULL或目标指针elseif(T-datakey)returnSearchBST(T-lchild,key);//查左elsereturnSearchBST(T-rchild,key);//查右}

二叉排序树的插入和删除

插入问题其实和把大象塞进冰箱里有着一样的逻辑

找到插入位置

打开冰箱门

执行插入操作

塞大象

返回

关上冰箱门

如何找到插入位置?

通过查找算法。

boolInsertBST(BiNode*T,BiNode*New){//当查找不到BiNode时,把new结点插入到最后位置//此处使用SearchBST的改良版,使用引用指针的方式,得到结果是使p停留在最后位置并返回查找成功状态if(!SearchBST(T,key,NULL,p))//null为p前置指针f,初值为NULL,查找不到进入循环{if(!p)T=New;//如果p是null,证明是空树,直接将New赋值给根节点elseif(keyp-data)p-lchild=New;//根据条件判断,选择左孩子或右孩子赋值elseif(keyp-data)p-rchild=New;returntrue;//插入成功}returnfalse;//插入失败,未到插入位置}

插入算法??

删除时,情况较插入更加复杂,需要考虑三种情况。

①待删除结点为叶子结点

②待删除结点为中间结点(只有左或右子树)

③待删除结点为子二叉根结点(同时有左右子树)

对于①,直接删除就好

对于②,将唯一子树首结点连接在待删除结点位置就好

情况③较为复杂。

假如将二叉树中序遍历展开,删除节点后,在中序遍历中其他结点的对应位置关系不应该发生改变。

此处选用替身法。

为何起名替身法?

因为删除的结点其实并未删除,而是删除了它的一个替身

替身为:左子树中的最大值或右子树中的最小值

操作为:将替身的值赋给被删结点的值,然后删除替身。

类递归思想:删除替身,直到替身是①②类型。

boolDelete(BiNode*p){BiNode*q;if(!p-rchild){q=p;p=p-lchild;free(q);}elseif(!p-lchild){q=p;p=p-rchild;free(q);}else{//左右子树均不空q=p;BiNode*s=p-lchild;while(s-rchild){q=s;s=s-rchild;}//往左走一步然后向右到尽头,得到的是被删结点的前驱位置//即替身位置p-data=s-data;//替身值赋值//替身删除Delete(s);}returnture;}

----End---

预览时标签不可点收录于话题#个上一篇下一篇
分享 转发
TOP
发新话题 回复该主题