前言
只有光頭才能變強。
文本已收錄至我的GitHub倉庫,歡迎Star:https://github.com/ZhongFuCheng3y/3y一、二叉樹就是這么簡單
本文撇開一些非常苦澀、難以理解的概念來講講二叉樹,僅入門觀看(或復習)....
首先,我們來講講什么是樹:
樹是一種非線性的數據結構,相對于線性的數據結構(鏈表、數組)而言,樹的平均運行時間更短(往往與樹相關的排序時間復雜度都不會高)
在現實生活中,我們一般的樹長這個樣子的:
但是在編程的世界中,我們一般把樹“倒”過來看,這樣容易我們分析:
一般的樹是有很多很多個分支的,分支下又有很多很多個分支,如果在程序中研究這個會非常麻煩。因為本來樹就是非線性的,而我們計算機的內存是線性存儲的,太過復雜的話我們無法設計出來的。
因此,我們先來研究簡單又經常用的---> 二叉樹
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); } //中序遍歷樹 inTraverseBTree(root.getTreeRoot()); System.out.println("---------------公眾號:Java3y"); //先序遍歷樹 preTraverseBTree(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。公眾號內有200多篇原創技術文章、海量視頻資源、精美腦圖,不妨來關注一下!
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/76367.html
摘要:并且,我們的底層都是紅黑樹來實現的。紅黑樹是一種平衡二叉樹因此它沒有節點。 前言 聲明,本文用得是jdk1.8 前面已經講了Collection的總覽和剖析List集合: Collection總覽 List集合就這么簡單【源碼剖析】 原本我是打算繼續將Collection下的Set集合的,結果看了源碼發現:Set集合實際上就是HashMap來構建的! showImg(https:/...
閱讀 1148·2021-09-22 15:43
閱讀 2345·2021-09-22 15:32
閱讀 4455·2021-09-22 15:11
閱讀 2187·2019-08-30 15:55
閱讀 2564·2019-08-30 15:54
閱讀 984·2019-08-30 15:44
閱讀 1095·2019-08-29 13:26
閱讀 794·2019-08-29 12:54