一棵二叉排序树应该具备的条件：
①若左子树不为空，则左子树上所有结点都应小于根节点
②若右子树不为空，则右子树上所有结点都应大于根节点
③它的左右子树也分别为二叉排序树
关于树的定义很多时候都是递归定义
何为序?
开始比较后，有四种可能
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---
预览时标签不可点收录于话题#个上一篇下一篇