一、二叉樹就是這麼簡單 本文撇開一些非常苦澀、難以理解的概念來講講二叉樹，僅入門觀看(或複習).... 首先，我們來講講什麼是樹： 樹是一種 非線性 的數據結構，相對於線性的數據結構(鏈表、數組)而言， 樹的平均運行時間更短(往往與樹相關的排序時間複雜度都不會高) 在現實生活中，我們一般的樹長這個樣 ...
一、二叉樹就是這麼簡單
本文撇開一些非常苦澀、難以理解的概念來講講二叉樹，僅入門觀看(或複習)....
首先，我們來講講什麼是樹：
- 樹是一種非線性的數據結構，相對於線性的數據結構(鏈表、數組)而言，樹的平均運行時間更短(往往與樹相關的排序時間複雜度都不會高)
在現實生活中，我們一般的樹長這個樣子的：
但是在編程的世界中，我們一般把樹“倒”過來看，這樣容易我們分析：
一般的樹是有很多很多個分支的，分支下又有很多很多個分支，如果在程式中研究這個會非常麻煩。因為本來樹就是非線性的，而我們電腦的記憶體是線性存儲的，太過複雜的話我們無法設計出來的。
因此，我們先來研究簡單又經常用的---> 二叉樹
1.1樹的一些概念
我就拿上面的圖來進行畫來講解了：
二叉樹的意思就是說：每個節點不能多於有兩個兒子，上面的圖就是一顆二叉樹。
- 一棵樹至少會有一個節點(根節點)
- 樹由節點組成，每個節點的數據結構是這樣的：
- 因此，我們定義樹的時候往往是->定義節點->節點連接起來就成了樹，而節點的定義就是：一個數據、兩個指針(如果有節點就指向節點、沒有節點就指向null)
1.2靜態創建二叉樹
上面說了，樹是由若幹個節點組成，節點連接起來就成了樹，而節點由一個數據、兩個指針組成
- 因此，創建樹實際上就是創建節點，然後連接節點
首先，使用Java類定義節點：
public class TreeNode {
// 左節點(兒子)
private TreeNode lefTreeNode;
// 右節點(兒子)
private TreeNode rightNode;
// 數據
private int value;
}下麵我們就拿這個二叉樹為例來構建吧：
為了方便構建，我就給了它一個帶參數的構造方法和set、get方法了：
public TreeNode(int value) {
this.value = value;
}那麼我們現在就創建了5個節點：
public static void main(String[] args) {
//根節點-->10
TreeNode treeNode1 = new TreeNode(10);
//左孩子-->9
TreeNode treeNode2 = new TreeNode(9);
//右孩子-->20
TreeNode treeNode3 = new TreeNode(20);
//20的左孩子-->15
TreeNode treeNode4 = new TreeNode(15);
//20的右孩子-->35
TreeNode treeNode5 = new TreeNode(35)
}它們目前的狀態是這樣子的：
於是下麵我們去把它連起來：
//根節點的左右孩子
treeNode1.setLefTreeNode(treeNode2);
treeNode1.setRightNode(treeNode3);
//20節點的左右孩子
treeNode3.setLefTreeNode(treeNode4);
treeNode3.setRightNode(treeNode5);連接完之後，那麼我們的樹就創建完成了。
1.3遍歷二叉樹
上面說我們的樹創建完成了，那怎麼證明呢？？我們如果可以像數組一樣遍歷它(看它的數據)，那就說明它創建完成了～
值得說明的是：二叉樹遍歷有三種方式
- 先序遍歷
- 先訪問根節點，然後訪問左節點，最後訪問右節點(根->左->右)
- 中序遍歷
- 先訪問左節點，然後訪問根節點，最後訪問右節點(左->根->右)
- 後序遍歷
- 先訪問左節點，然後訪問右節點，最後訪問根節點(左->右->根)
以上面的二叉樹為例：
- 如果是先序遍歷：
10->9->20->15->35 - 如果是中序遍歷：
9->10->15->20->35- 可能需要解釋地方：訪問完10節點過後，去找的是20節點，但20下還有子節點，因此先訪問的是20的左兒子15節點。由於15節點沒有兒子了。所以就返回20節點，訪問20節點。最後訪問35節點
- 如果是後序遍歷：
9->15->35->20->10- 可能需要解釋地方：先訪問9節點，隨後應該訪問的是20節點，但20下還有子節點，因此先訪問的是20的左兒子15節點。由於15節點沒有兒子了。所以就去訪問35節點，由於35節點也沒有兒子了，所以返回20節點，最終返回10節點
一句話總結：先序(根->左->右)，中序(左->根->右)，後序(左->右->根)。如果訪問有孩子的節點，先處理孩子的，隨後返回
無論先中後遍歷，每個節點的遍歷如果訪問有孩子的節點，先處理孩子的(邏輯是一樣的)
- 因此我們很容易想到遞歸
- 遞歸的出口就是：當沒有子節點了，就返回
因此，我們可以寫出這樣的先序遍歷代碼：
/**
* 先序遍歷
* @param rootTreeNode 根節點
*/
public static void preTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//訪問根節點
System.out.println(rootTreeNode.getValue());
//訪問左節點
preTraverseBTree(rootTreeNode.getLefTreeNode());
//訪問右節點
preTraverseBTree(rootTreeNode.getRightNode());
}
}
結果跟我們剛纔說的是一樣的：
我們再用中序遍歷調用一遍吧：
/**
* 中序遍歷
* @param rootTreeNode 根節點
*/
public static void inTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//訪問左節點
inTraverseBTree(rootTreeNode.getLefTreeNode());
//訪問根節點
System.out.println(rootTreeNode.getValue());
//訪問右節點
inTraverseBTree(rootTreeNode.getRightNode());
}
}結果跟我們剛纔說的是一樣的：
有意思的是：通過先序和中序或者中序和後序我們可以還原出原始的二叉樹，但是通過先序和後續是無法還原出原始的二叉樹的
- 也就是說：通過中序和先序或者中序和後序我們就可以確定一顆二叉樹了！
二、動態創建二叉樹
上面我們是手動創建二叉樹的，一般地：都是給出一個數組給你，讓你將數組變成一個二叉樹，此時就需要我們動態創建二叉樹了。
二叉樹中還有一種特殊的二叉樹：二叉查找樹(binary search tree)
- 定義：當前根節點的左邊全部比根節點小，當前根節點的右邊全部比根節點大。
- 明眼人可以看出，這對我們來找一個數是非常方便快捷的
往往我們動態創建二叉樹都是創建二叉查找樹
2.1動態創建二叉樹體驗
假設我們有一個數組：int[] arrays = {3, 2, 1, 4, 5};
那麼創建二叉樹的步驟是這樣的：
- 首先將3作為根節點
- 隨後2進來了，我們跟3做比較，比3小，那麼放在3的左邊
- 隨後1進來了，我們跟3做比較，比3小，那麼放在3的左邊，此時3的左邊有2了，因此跟2比，比2小，放在2的左邊
- 隨後4進來了，我們跟3做比較，比3大，那麼放在3的右邊
- 隨後5進來了，我們跟3做比較，比3大，那麼放在3的右邊，此時3的右邊有4了，因此跟4比，比4大，放在4的右邊
那麼我們的二叉查找樹就建立成功了，無論任何一顆子樹，左邊都比根要小，右邊比根要大
2.2代碼實現
我們的代碼實現也很簡單，如果比當前根節點要小，那麼放到當前根節點左邊，如果比當前根節點要大，那麼放到當前根節點右邊。
因為是動態創建的，因此我們得用一個類來表示根節點
public class TreeRoot {
private TreeNode treeRoot;
public TreeNode getTreeRoot() {
return treeRoot;
}
public void setTreeRoot(TreeNode treeRoot) {
this.treeRoot = treeRoot;
}
}比較與根誰大，大的往右邊，小的往左邊：
/**
* 動態創建二叉查找樹
*
* @param treeRoot 根節點
* @param value 節點的值
*/
public static void createTree(TreeRoot treeRoot, int value) {
//如果樹根為空(第一次訪問)，將第一個值作為根節點
if (treeRoot.getTreeRoot() == null) {
TreeNode treeNode = new TreeNode(value);
treeRoot.setTreeRoot(treeNode);
} else {
//當前樹根
TreeNode tempRoot = treeRoot.getTreeRoot();
while (tempRoot != null) {
//當前值大於根值，往右邊走
if (value > tempRoot.getValue()) {
//右邊沒有樹根，那就直接插入
if (tempRoot.getRightNode() == null) {
tempRoot.setRightNode(new TreeNode(value));
return ;
} else {
//如果右邊有樹根，到右邊的樹根去
tempRoot = tempRoot.getRightNode();
}
} else {
//左沒有樹根，那就直接插入
if (tempRoot.getLefTreeNode() == null) {
tempRoot.setLefTreeNode(new TreeNode(value));
return;
} else {
//如果左有樹根，到左邊的樹根去
tempRoot = tempRoot.getLefTreeNode();
}
}
}
}
}測試代碼：
int[] arrays = {2, 3, 1, 4, 5};
//動態創建樹
TreeRoot root = new TreeRoot();
for (int value : arrays) {
createTree(root, value);
}
//先序遍歷樹
preTraverseBTree(root.getTreeRoot());
System.out.println("---------------公眾號：Java3y");
//中序遍歷樹
inTraverseBTree(root.getTreeRoot());
System.out.println("---------------公眾號：Java3y");三、查詢二叉查找樹相關
3.1查詢樹的深度
查詢樹的深度我們可以這樣想：左邊的子樹和右邊的字數比，誰大就返回誰，那麼再接上根節點+1就可以了
public static int getHeight(TreeNode treeNode) {
if (treeNode == null) {
return 0;
} else {
//左邊的子樹深度
int left = getHeight(treeNode.getLefTreeNode());
//右邊的子樹深度
int right = getHeight(treeNode.getRightNode());
int max = left;
if (right > max) {
max = right;
}
return max + 1;
}
}3.1查詢樹的最大值
從上面先序遍歷二叉查找樹的時候，細心的同學可能會發現：中序遍歷二叉查找樹得到的結果是排好順序的～
那麼，如果我們的二叉樹不是二叉查找樹，我們要怎麼查詢他的最大值呢？
可以這樣：
- 左邊找最大值->遞歸
- 右邊找最大值->遞歸
/**
* 找出樹的最大值
*
* @param rootTreeNode
*/
public static int getMax(TreeNode rootTreeNode) {
if (rootTreeNode == null) {
return -1;
} else {
//找出左邊的最大值
int left = getMax(rootTreeNode.getLefTreeNode());
//找出右邊的最大值
int right = getMax(rootTreeNode.getRightNode());
//與當前根節點比較
int currentRootValue = rootTreeNode.getValue();
//假設左邊的最大
int max = left;
if (right > max) {
max = right;
}
if (currentRootValue > max) {
max = currentRootValue;
}
return max ;
}
}四、最後
無論是在遍歷樹、查找深度、查找最大值都用到了遞歸，遞歸在非線性的數據結構中是用得非常多的...
樹的應用也非常廣泛，此篇簡單地說明瞭樹的數據結構，高級的東西我也沒弄懂，可能以後用到的時候會繼續深入...
如果文章有錯的地方歡迎指正，大家互相交流。習慣在微信看技術文章，想要獲取更多的Java資源的同學，可以關註微信公眾號:Java3y
