二叉搜索树，提供了可以快速查询、添加和删除某些结点，比如找到某个数在一个有序数据集合中的位置等。
我们在想要寻找一个元素，或者想找到一个位置来插入元素的时候，我们是从根开始比较的，该元素与根的比较结果，就可以让我们确定一个是从根结点的左子树还是右子树继续查找的方向，在这个阶段，我们已经省去了所有元素一半的比较，这种查找方式的速度有时显而易见，当然，如果单从查找的角度来说，哈希表（HashTable）会更快。
当我们有一个值为7的元素，想要插入到这个搜索树中，那么它的查找和最终的插入流程是（颜色渐深，表示查找顺序）：
我们已经熟悉了基本的流程，下面我们开始用伪代码的形式来实现各个功能，首先就是插入（本期文章的内容参考了github上一个开源的代码库，它的相对实现非常的规范，就不自己造轮子了）：insert(value)ifroot=null/*node(value)代表示例化一个node结点*//*value就是这个结点的值*/root-node(value)else/*如果根不是空,则要先查找到合适位置,再插入*/insertNode(root,value)endifendinsert
/*current代表要插入到那个树(子树)的当前根结点*/insertNode(current,value)/*如果值比当前结点值小*/ifvaluecurrent.value/*并且它的左子树为空,则直接插入*/ifcurrent.left=nullcurrent.left-node(value)/*如果它的左子树不为空,则递归调用自身,*以目前的左子树为current继续查找*/elseInsertNode(current.left,value)endif/*如果值大于等于当前值*/else/*并且它的右子树为空*/ifcurrent.right=nullcurrent.right-node(value)/*否则同上述方式,递归调用本身*/elseInsertNode(current.right,value)endifendifendinsertNode
我们已经实现了基础的插入，核心处理的问题就是递归调用。
下面我们来看搜索（不是查找具体位置，而是是否包含。英文命名的话是Searching，函数名叫contains，应该是包含的意思）：
contains(root,value)ifroot=nullreturnfalseendififroot.value=valuereturntrueelseifvalueroot.valuereturncontains(root.left,value)elsereturncontains(root.right,value)endifendcontains
那接下来，一起来看我们熟悉的查找（Find）：
//查找目标结点的父结点findParent(value,root)//如果值等于根结点,则他没有父结点.返回空ifvalue=root.valuereturnnullendififvalueroot.valueifroot.left=nullreturnnullelseifroot.left.value=valuereturnrootelsereturnfindParent(value,root.left)endifelseifroot.right=nullreturnnullelseifroot.right.value=valuereturnrootelsereturnfindParent(value,root.right)endifendifendfindParent
上述的核心逻辑就是查找的时候，可能存在为空的情况，做好处理即可。
//查找结点的思路跟查找父结点类似findNode(root,value)ifroot=nullreturnnullendififroot.value=valuereturnrootelseifvalueroot.valuereturnfindNode(root.left,value)elsereturnfindNode(root.right,value)endifendfindNode
//还有就是查找最大最小值//利用有序的特性,//最小值一定在根结点左子树上findMin(root)ifroot.left=nullreturnroot.valueendiffindMin(root.left)endfindMin//最大值一定在根结点右子树上findMax(root)ifroot.right=nullreturnroot.valueendiffindMax(root.right)endfindMax
然后，我们顺便复习一下昨天说过的前序、中序、后序遍历：
inorder(root)ifroot=nullinorder(root.left)yieldroot.valueinorder(root.right)endifendinorder
preorder(root)ifroot=nullyieldroot.valuepreorder(root.left)preorder(root.right)endifendpreorder
postorder(root)ifroot=nullpostorder(root.left)postorder(root.right)yieldroot.valueendifendpostorder
最后，我们来看一个比较复杂的删除操作，他的核心难点是，要保证他没有子结点的情况下才能删除当前结点：
remove(value)//先通过查找确定位置nodeToRemove-findNode(value)//如果没找到,直接返回失败ifnodeToRemove=nullreturnfalseendif//看一下value的父结点parent-findParent(value)//count代表树的结点数ifcount=1root-null//如果要删除的节点是叶子结点(没有子结点)elseifnodeToRemove.left=nullandnodeToRemove.right=null//如果要删除结点小于父结点,则就是把父节点的左子树值为空ifnodeToRemove.valueparent.valueparent.left-nodeToRemove.right//反之同理elseparent.right-nodeToRemove.rightendif//如果左右节点都不为空elseifnodeToRemove.left!=nullandnodeToRemove.right!=null//暂存右侧的值next-nodeToRemove.right//找到递归左结点到叶子结点whilenext.left!=nullnext-next.leftendwhile//如果暂存的最下层的左结点不等于要删除的有结点ifnext!=nodeToRemove.right//删除最下层的这个叶子结点remove(next.value)//并且吧这个值放在要删除的节点上//核心思路是找到左侧最大值挪到要删除的结点上nodeToRemove.value←next.value//如果想等else//直接把删除结点左侧最大的左叶子节点替换nodeToRemove.value-next.value//并且把删除结点的右结点复制上移一层nodeToRemove.right-nodeToRemove.right.rightendif//其他情况else//如果删除结点的左结点为空ifnodeToRemove.left=null//暂存右结点next-nodeToRemove.rightelse//否则暂存左结点next-nodeToRemove.leftendif//如果要删除结点是根结点ifroot=nodeToRemove//把next放到跟上root=next//如果删除的是左子树elseifparent.left=nodeToRemove//替换parent.left=nextelseifparent.right=nodeToRemove//替换parent.right=nextendifendif//计数减一count←count-1returntrueendremove
大家看完这个删除操作肯定特别懵逼，今天因为时间问题，先写到这。明天专门写一期图示，来展示删除操作。
最后提醒大家疫情期间注意勤洗手，勤消*，少聚集，出门戴口罩。
福利时间，应广大粉丝要求。我建了一个前端技术交流群。扫码即可进入如果群满了人，请添加我的