码农每日一题
长按关注置顶
工作日每天推送一个短小精干的技术知识点，让您可以随时查漏补缺。
问：简单说说排序二叉树的插入、删除、查找流程？
答：首先如果普通二叉树每个节点满足左子树所有节点值小于它的根节点值且右子树所有节点值大于它的根节点值，则这样的二叉树就是排序二叉树。
插入操作首先要从根节点开始往下找到自己要插入的位置（即新节点的父节点）；具体流程是新节点与当前节点比较，如果相同则表示已经存在且不能再重复插入；如果小于当前节点，则到左子树中寻找，如果左子树为空则当前节点为要找的父节点，新节点插入到当前节点的左子树即可；如果大于当前节点，则到右子树中寻找，如果右子树为空则当前节点为要找的父节点，新节点插入到当前节点的右子树即可。具体演示如下图：
删除操作主要分为三种情况，即要删除的节点无子节点，要删除的节点只有一个子节点，要删除的节点有两个子节点。
对于要删除的节点无子节点可以直接删除，即让其父节点将该子节点置空即可。
对于要删除的节点只有一个子节点则替换要删除的节点为其子节点。
对于要删除的节点有两个子节点则首先找该节点的替换节点（即右子树中最小的节点），接着替换要删除的节点为替换节点，然后删除替换节点。
具体演示如下：
查找算的主要流程为先和根节点比较，如果相同就返回，如果小于根节点则到左子树中递归查找，如果大于根节点则到右子树中递归查找。因此在排序二叉树中可以很容易获取最大（最右最深子节点）和最小（最左最深子节点）值。
遍历就比较多了，具体可以参考如下链接（算法这种东西就是要看代码理解）：
https://segmentfault.com/a/1190000009817457
https://www.cnblogs.com/gl-developer/p/7259251.html
http://www.cnblogs.com/gl-developer/p/7259365.html
本篇相关历史推送：
《JDK 1.8 中 HashMap 扩容骚操作的变化问题》
《【码农每日一题】Java PriorityQueue 中二叉堆原理相关问题》
放松一下，顺带评论点赞分享一波～
怎么优雅地解释自己胖？ 神回复：因为有许多事放在心里不好瘦。
本文分享自微信公众号 - 码农每日一题（DailyCoder）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
