摘要：自查找二叉樹起，可以說種族崛起了。編碼不善言辭，為敬首先代碼定義出查找二叉樹的結(jié)構(gòu)結(jié)構(gòu)，存儲業(yè)務(wù)數(shù)據(jù)左節(jié)點(diǎn)右節(jié)點(diǎn)注意查找二叉樹的結(jié)構(gòu)可類比數(shù)據(jù)庫表結(jié)構(gòu)理解。
載一棵小樹苗，精心培育，總有一天會長成參天大樹
????????????????比如查找二叉、AVL、B + *、紅黑……
結(jié)構(gòu)
繼線性結(jié)構(gòu)之后，人們之所以又發(fā)明了樹形結(jié)構(gòu)，是為了方便查找。普通樹隨便生長，看著就眼暈，除了和自然界的樹結(jié)構(gòu)相似對得起Tree這名號，沒太大價(jià)值，更別提方便查找了。
自查找二叉樹起，可以說種族崛起了。結(jié)構(gòu)上：從根節(jié)點(diǎn)起，小于父節(jié)點(diǎn)的在左，大于父節(jié)點(diǎn)的在右。如此結(jié)構(gòu)，本身就是有序的，以中序遍歷（左->中->右）的方式走一遍，很方便把值從小到大排序。
以下給出這種樹的關(guān)鍵方法的邏輯，以及具體的編碼實(shí)現(xiàn)。
編碼
（不善言辭，coding為敬……）
首先代碼定義出查找二叉樹的結(jié)構(gòu)：
// 結(jié)構(gòu)
public class BinaryNode {
// key
private Integer id;
// val，存儲業(yè)務(wù)數(shù)據(jù)
private V val;
// 左節(jié)點(diǎn)
private BinaryNode leftNode;
// 右節(jié)點(diǎn)
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;
}
}
注意：
查找二叉樹的結(jié)構(gòu)可類比數(shù)據(jù)庫表結(jié)構(gòu)理解。
對于mysql中采用innodb引擎創(chuàng)建的表而言，以id為主鍵的表數(shù)據(jù)會自動加持索引。（實(shí)際上索引是B+ tree結(jié)構(gòu)，可視作{{BANNED}}版的查找樹）
這也是上面的代碼結(jié)構(gòu)定義中，key采用id命名的原因，val則可視為該數(shù)據(jù)庫表的其它字段。
新增節(jié)點(diǎn)
每次新增節(jié)點(diǎn)，會從根節(jié)點(diǎn)開始，根據(jù)值的大小，尋找自己的位置。
舉個(gè)例子，上圖的樹再增加一個(gè)節(jié)點(diǎn)35，會經(jīng)歷如下心路歷程：
與根節(jié)點(diǎn)50比較，新節(jié)點(diǎn)35較小，置左；很不幸，左邊已經(jīng)有節(jié)點(diǎn)30雄踞。
新節(jié)點(diǎn)35繼續(xù)與節(jié)點(diǎn)30比較。其實(shí)此時(shí)可以忽略根節(jié)點(diǎn)50，把左子樹視作一顆新樹，節(jié)點(diǎn)30視作新的根節(jié)點(diǎn)……沒錯(cuò)，就是遞歸，直到最終找到一個(gè)空位置，方安身立命。
代碼實(shí)現(xiàn)如下：
//新增，先不考慮id重復(fù)的問題
//@param id：新增節(jié)點(diǎn)的key
//@param val：新增節(jié)點(diǎn)的值
BinaryNode add(Integer id,V val,BinaryNode tree){
//該位置無節(jié)點(diǎn)，安身立命
if(tree == null){
tree = new BinaryNode<>(id,val,null,null);
}
//遞歸：新節(jié)點(diǎn)id大于當(dāng)前節(jié)點(diǎn)，新節(jié)點(diǎn)置右
if(id>tree.id){
tree.rightNode = add(id,val,tree.rightNode);
}
//遞歸：新節(jié)點(diǎn)id小于當(dāng)前節(jié)點(diǎn)，新節(jié)點(diǎn)置左
if(id
范圍查找
正如之前提過的，查找二叉樹的優(yōu)勢就在于范圍查找。
怎么在一顆查找二叉樹中找到min>=且<=max的全部值？具體步驟如下：
當(dāng)前節(jié)點(diǎn)與min比較，如果大于min，則遞歸查看它的左節(jié)點(diǎn)；如果它沒有左節(jié)點(diǎn)，結(jié)束遞歸
當(dāng)前節(jié)點(diǎn)在min和max范圍內(nèi)，放入結(jié)果集
當(dāng)前節(jié)點(diǎn)與max比較，如果小于max，則遞歸查看它的右節(jié)點(diǎn)；如果它沒有右節(jié)點(diǎn)，結(jié)束遞歸
Collection searchRange(Integer min, Integer max, Collection collection,BinaryNode tree){
//當(dāng)前節(jié)點(diǎn)與min比較，如果大于min，遞歸查看當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)（如果有左節(jié)點(diǎn)的話）
if(min=tree.getId()){
collection.add(tree.getVal());
}
//當(dāng)前節(jié)點(diǎn)與max比較，如果小于max，遞歸查看當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)（如果有右節(jié)點(diǎn)的話）
if(tree.getId()
刪除節(jié)點(diǎn)
刪除節(jié)點(diǎn)相對比較復(fù)雜，涉及到子樹銜接問題，分幾種情況：
無子：被刪節(jié)點(diǎn)沒有子節(jié)點(diǎn)（葉子節(jié)點(diǎn)），直接移除就好。
單子：直接頂替被刪除節(jié)點(diǎn)的位置。
雙子
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); //找到最小節(jié)點(diǎn)
tree.id = min.id;
tree.val = min.val;
tree.rightNode = remove(tree.id,tree.rightNode);
}
//無子
else {
tree = null;
}
}
return tree;
}
注意：
這里有個(gè)小訣竅。在做節(jié)點(diǎn)替換時(shí)（`32`替換`30`），可直接修改id和val，這樣就不需要修改引用了！
不足
試想一下這種情況，查找二叉樹在新增節(jié)點(diǎn)時(shí)，假如一直增加更小的節(jié)點(diǎn)，我們將得到一個(gè)只有左節(jié)點(diǎn)的查找二叉樹（雖然二叉不起來）。這樣的樹與鏈表又有什么區(qū)別呢？這種極端情況下，就失去了樹的優(yōu)勢了。
也就是說，在新增或刪除操作過程中，樹越不均衡（左傾或右傾），越影響查找效率！
如何彌補(bǔ)這種不足？需要保持樹的平衡，敬請期待AVL樹——平衡的查找二叉樹。
附錄
完整代碼實(shí)現(xiàn)見我的git練習(xí)項(xiàng)目com.evolution.tree包下，地址：evolution 暗夜君王的各種demo練習(xí)
啰嗦幾句，demo項(xiàng)目中查找二叉樹的實(shí)現(xiàn)com.evolution.tree.BinaryNodeBak，模擬了數(shù)據(jù)庫表，會多一些id的唯一性驗(yàn)證。另外，還增加了中序遍歷實(shí)現(xiàn)sort()方法。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72476.html
