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

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

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

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

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

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

何为序?

开始比较后，有四种可能

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