摘要：自查找二叉樹起，可以說種族崛起了。編碼不善言辭，為敬首先代碼定義出查找二叉樹的結構結構，存儲業務數據左節點右節點注意查找二叉樹的結構可類比數據庫表結構理解。
載一棵小樹苗，精心培育，總有一天會長成參天大樹
????????????????比如查找二叉、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()方法。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/72476.html
