前序
昨天我們分析了樹形結構和特點，特别是二叉樹結構和特點，手動建立了一個二叉樹，并實作了先序，中序，後序三種周遊方式，那麼今天就先來一個動态建立二叉樹，并且是一個二叉查找樹。
什麼是二叉查找樹？
二叉查找樹是一種特殊的二叉樹
特點：
- 左側樹節點全部比根節點小，右側樹節點全部比根節點大。
- 任意一個節點左兒子節點小，右兒子節點大。
通過這個結構，查找一個數将會非常友善。
來一個動态建立的二叉查找樹
定義一個數組，用于建立二叉樹的資料
建立二叉樹步驟解析：
- 以數組arr第一個索引【3】為二叉樹根節點（根節點root）
- 以數組arr第二個索引【1】，和根節點比較，小于設定為根節點左側兒子節點（根節點-左兒子）
- 以數組arr第三個索引【5】，和根節點比較，大于設定為根節點右側兒子節點（根節點-右兒子）
- 以數組arr第四個索引【7】，和根節點比較大于，在和根節點右兒子比較大于，設定為右側節點（根節點-右兒子-右孫子）
- 以數組arr第五個索引【9】，和根節點比較大于，在和根節點右兒子比較大于，在和根右孫子節點比較大于，設定為右側節點（根節點-右兒子-右孫子-右曾孫子）
- 以數組arr第五個索引【4】，和根節點比較大于，在和根右兒子比較小于，設定為右兒子左側節點（根節點，右兒子，左孫子）
代碼邏輯
根據上述二叉樹步驟解析，通過自定義一個包裝類，完成二叉樹的建立
public class TreeRoot {
private TreeNode treeNode;
public TreeNode getTreeRoot() {
return treeNode;
}
public void setTreeRoot(TreeNode treeNode) {
this.treeNode = treeNode;
}
代碼邏輯說明:如果比目前根節點要小，那麼放到目前根節點左邊，如果比目前根節點要大，那麼放到目前根節點右邊。
/**
* 建立二叉樹
*
* @author 張江豐
* @param tr
* 二叉樹包裝對象
* @param value
* 節點值
*/
public static void createTree(TreeRoot tr, int value) {
// 首先判斷根節點資料為空
if (tr.getTreeRoot() == null) {
// 直接把value設定給root
tr.setTreeRoot(new TreeNode(value));
} else {
// 根不為空的
// value大于根節點設定到右側
if (value > tr.getTreeRoot().getValue()) {
// 根右側節點為空，直接設定
if (tr.getTreeRoot().getRightNode() == null) {
tr.getTreeRoot().setRightNode(new TreeNode(value));
} else {
// 右側節點不為空
TreeNode trr = comparTree(tr.getTreeRoot().getRightNode(), value);
// tr.setTreeRoot(trr);
}
} else {
// value小于根節點設定到左側
if (tr.getTreeRoot().getLeftNode() == null) {
tr.getTreeRoot().setLeftNode(new TreeNode(value));
// tr.setTreeRoot(new TreeNode(value));
} else {
// 左側節點不為空
TreeNode trl = comparTree(tr.getTreeRoot().getLeftNode(), value);
// tr.setTreeRoot(trl);
}
}
}
}
如果是孫子節點，通過遞歸判斷定位存放位置
/**
* 遞歸判斷--判斷資料存放節點位置
*
* @author 張江豐
* @param tn
* 左側/右側節點對象
* @param value
* 節點值
* @return
*/
public static TreeNode comparTree(TreeNode tn, int value) {
// 判斷value比節點資料大
if (value > tn.getValue()) {
// 右側節點為空，直接設定value
if (tn.getRightNode() == null) {
tn.setRightNode(new TreeNode(value));
return tn;
} else {
// 遞歸判斷下一級節點
comparTree(tn.getRightNode(), value);
}
} else {
// value比節點資料小
if (tn.getLeftNode() == null) {
// 左側節點為空，直接設定value
tn.setLeftNode(new TreeNode(value));
return tn;
} else {
// 左側節點有資料，遞歸判斷下一級節點
comparTree(tn.getLeftNode(), value);
}
}
return tn;
}
資料測試
public static void main(String[] args) {
int[] arr = { 3, 1, 5, 7, 9, 4 };
TreeRoot tr = new TreeRoot();
for (int i : arr) {
createTree(tr, i);
}
// TreeNode.befoTree(tr.getTreeRoot());
TreeNode.betTree(tr.getTreeRoot());
// TreeNode.afterTree(treeNode);
}
驗證：
這裡使用中序周遊方式，中序周遊的順序(左->根->右)，輸出結果應該為1-3-4-5-7-9，周遊代碼具體請看【來玩二叉樹NO.1】–之周遊算法
控制台輸出
邏輯debug
二叉查找樹深度查詢
查詢樹的深度我們可以這樣想：根節點下左邊的子樹和右邊的字數比，誰大就傳回誰(層級多)，然後再接上根節點+1就可以了。
public static int getDeep(TreeNode tn) {
if (tn == null) {
return 0;
} else {
// 查詢左側子樹深度
int left = getDeep(tn.getLeftNode());
// 查詢右側子樹深度
int right = getDeep(tn.getRightNode());
// 以左側子樹為錨點比較深度
int max = left;
// 判斷左，右子樹深度大小，如果左右兩側深度相等跳過直接加上根節點傳回
if (right > max) {
max = right;
}
// 加上根節點傳回計算深度結果
return max + 1;
}
充分利用遞歸算法的優勢，通過遞歸層層計算節點深度，最後傳回根節點，經過比較找出二叉查找樹深度。
二叉樹的最大值
在上一篇部落格二叉樹的周遊算法，中序周遊(左-根-右)的結果已經是排好序，那麼如果不是二叉查找樹，又如何查詢到最大值？
其實可以通過一個根節點和左右子節點比較，誰大傳回誰，在遞歸下傳回最大的值
public static int getMaxValue(TreeNode rootTreeNode) {
if (rootTreeNode == null) {
return -1;
} else {
// 找出左邊的最大值
int left = getMaxValue(rootTreeNode.getLeftNode());
// 找出右邊的最大值
int right = getMaxValue(rootTreeNode.getRightNode());
// 與目前根節點比較
int currentRootValue = rootTreeNode.getValue();
// 以左側子樹為錨點
int max = left;
//先比較左右兩側子節點，誰大傳回誰
if (right > max) {
max = right;
}
//父節點和最大的子節點比較，誰大傳回誰
if (currentRootValue > max) {
max = currentRootValue;
}
//傳回父節點-左兒子-右兒子的最大值
return max;
}
}