摘要：自查找二叉树起，可以说种族崛起了。编码不善言辞，为敬首先代码定义出查找二叉树的结构结构，存储业务数据左节点右节点注意查找二叉树的结构可类比数据库表结构理解。
载一棵小树苗，精心培育，总有一天会长成参天大树
比如查找二叉、AVL、B + *、红黑……
结构
继线性结构之后，人们之所以又发明了树形结构，是为了方便查找。普通树随便生长，看着就眼晕，除了和自然界的树结构相似对得起Tree这名号，没太大价值，更别提方便查找了。
自查找二叉树起，可以说种族崛起了。结构上：从根节点起，小于父节点的在左，大于父节点的在右。如此结构，本身就是有序的，以中序遍历（左->中->右）的方式走一遍，很方便把值从小到大排序。
以下给出这种树的关键方法的逻辑，以及具体的编码实现。
编码
（不善言辞，coding为敬……）
首先代码定义出查找二叉树的结构：
// 结构
public class BinaryNode {
// key
private Integer id;
// val，存储业务数据
private V val;
// 左节点
private BinaryNode leftNode;
// 右节点
private BinaryNode rightNode;
public BinaryNode(Integer id, V val, BinaryNode leftNode, BinaryNode rightNode) {
this.id = id;
this.val = val;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
}
注意：
查找二叉树的结构可类比数据库表结构理解。
对于mysql中采用innodb引擎创建的表而言，以id为主键的表数据会自动加持索引。（实际上索引是B+ tree结构，可视作{{BANNED}}版的查找树）
这也是上面的代码结构定义中，key采用id命名的原因，val则可视为该数据库表的其它字段。
新增节点
每次新增节点，会从根节点开始，根据值的大小，寻找自己的位置。
举个例子，上图的树再增加一个节点35，会经历如下心路历程：
与根节点50比较，新节点35较小，置左；很不幸，左边已经有节点30雄踞。
新节点35继续与节点30比较。其实此时可以忽略根节点50，把左子树视作一颗新树，节点30视作新的根节点……没错，就是递归，直到最终找到一个空位置，方安身立命。
代码实现如下：
//新增，先不考虑id重复的问题
//@param id：新增节点的key
//@param val：新增节点的值
BinaryNode add(Integer id,V val,BinaryNode tree){
//该位置无节点，安身立命
if(tree == null){
tree = new BinaryNode<>(id,val,null,null);
}
//递归：新节点id大于当前节点，新节点置右
if(id>tree.id){
tree.rightNode = add(id,val,tree.rightNode);
}
//递归：新节点id小于当前节点，新节点置左
if(id
范围查找
正如之前提过的，查找二叉树的优势就在于范围查找。
怎么在一颗查找二叉树中找到min>=且<=max的全部值？具体步骤如下：
当前节点与min比较，如果大于min，则递归查看它的左节点；如果它没有左节点，结束递归
当前节点在min和max范围内，放入结果集
当前节点与max比较，如果小于max，则递归查看它的右节点；如果它没有右节点，结束递归
Collection searchRange(Integer min, Integer max, Collection collection,BinaryNode tree){
//当前节点与min比较，如果大于min，递归查看当前节点的左节点（如果有左节点的话）
if(min=tree.getId()){
collection.add(tree.getVal());
}
//当前节点与max比较，如果小于max，递归查看当前节点的右节点（如果有右节点的话）
if(tree.getId()
删除节点
删除节点相对比较复杂，涉及到子树衔接问题，分几种情况：
无子：被删节点没有子节点（叶子节点），直接移除就好。
单子：直接顶替被删除节点的位置。
双子
BinaryNode remove(Integer id,BinaryNode tree){
if(tree==null){
return null;
}
if(id>tree.getId()){
tree.rightNode = remove(id,tree.rightNode);
}
if(id min = findMin(tree.rightNode); //找到最小节点
tree.id = min.id;
tree.val = min.val;
tree.rightNode = remove(tree.id,tree.rightNode);
}
//无子
else {
tree = null;
}
}
return tree;
}
注意：
这里有个小诀窍。在做节点替换时（`32`替换`30`），可直接修改id和val，这样就不需要修改引用了！
不足
试想一下这种情况，查找二叉树在新增节点时，假如一直增加更小的节点，我们将得到一个只有左节点的查找二叉树（虽然二叉不起来）。这样的树与链表又有什么区别呢？这种极端情况下，就失去了树的优势了。
也就是说，在新增或删除操作过程中，树越不均衡（左倾或右倾），越影响查找效率！
如何弥补这种不足？需要保持树的平衡，敬请期待AVL树——平衡的查找二叉树。
附录
完整代码实现见我的git练习项目com.evolution.tree包下，地址：evolution 暗夜君王的各种demo练习
啰嗦几句，demo项目中查找二叉树的实现com.evolution.tree.BinaryNodeBak，模拟了数据库表，会多一些id的唯一性验证。另外，还增加了中序遍历实现sort()方法。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/72476.html
