——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。
动态查找表
动态查找表：表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其他关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。
二叉排序（查找）树：或者是一棵空树；或者是具有下列性质的二叉树，1）若它的左子树不为空，则左子树上所有结点的关键字均小于它的根结点的关键字；2）若它的右子树不为空，则右子树上所有结点的关键字均大于它的根结点的关键字；3）它的左、右子树也分别为二叉排序树（递归定义）。
二叉排序（查找）树的实质是，一棵中序遍历的关键字序列有序的二叉树。
动态树表：用二叉查找树表示的动态查找表。
动态树表（二叉排序（查找）树）的查找：二叉查找树的查找类似次优查找树的查找。当二叉查找树不空时，首先将给定值和根结点的关键字比较，若相等，则查找成功，否则依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续查找。
二叉查找树的插入
二叉查找树是动态树表，其树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入，新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子（因为只有沿根到叶子结点的路径遍历完该路径上的所有结点之后才能确定是否存在关键字等于给定值的结点，故若不存在，则新结点必为某个叶子结点的孩子而成为一个新的叶子结点）。每次插入新结点时不需要移动其他结点。
从空树出发，经一系列的查找插入操作之后，可生成一棵二叉查找树，但生成的树的结构与查找的顺序有关（即若查找的结点的集合相同，但各个结点的查找次序不同），但中序遍历各生成二叉查找树得到的有序序列相同。n个记录的二叉查找树不唯一（因为查找顺序是不确定的）。
中序遍历二叉排序树可得到一个关键字的有序序列（该性质可由二叉排序树的定义得到）。一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
二叉排序树既具有类似折半查找（只能在顺序存储结构上实现）的特性，又具有采用链表作存储结构的优点。
二叉查找树的删除
普通二叉树删除一个结点无意义（因为普通二叉树中各结点之间只有父子和兄弟关系，没有次序关系，在保持各结点间原有的父子和兄弟关系的前提下，删除一个结点将使以被删除结点为根的子树成为森林，破坏了整棵树的结构）。对于二叉排序树（树中各结点之间具有次序关系），删除一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性（中序遍历有序）即可。
假设二叉排序树上被删结点为*p，其双亲结点为*f，左、右子树分别为PL和PR，且不失一般性，可设*p是*f的左孩子。则
1)若结点*p的左子树PL或右子树PR为空，则直接令PR或PL中的根结点代替结点*p成为结点*f的左孩子；
2)若结点*p的左子树和右子树均不空，则有两种方法：
①选结点*p的直接左（右）孩子结点代替结点*p成为结点*f的左孩子，然后令结点*p的右（左）子树成为结点*p的中序遍历序列的直接前驱（后继）的右（左）子树；或
②选结点*p的中序遍历序列的直接前驱（后继）代替（此处的代替可以为结点内容的代替，即保留原结点*p（结点*p的地址值不变），只是修改结点*P的数据域的内容为要代替它的结点的数据域的内容）结点*p成为结点*f的左孩子，并从*p的左（右）子树中删除*p的中序遍历的直接前驱（后继）（使用①中的方法删除，因为用于替换的结点（即*p的中序遍历的直接前驱（后继））的右（左）子树必为空）。
（方法②相对于方法①，缺点是在删除中再次引入了删除操作；优点是不会引起树的结构的较大改变，且不会增加树的高度。）
文章合集：
点击下方公众号主页，关注以阅读更多文章
——可选择“【右上角···】→【在浏览器中打开】”进行横屏阅读。
