Java數據結構之樹和二叉樹的相關資料
什麼是樹？
簡單認識樹
在生活中，有楊樹，石榴樹，棗樹，而在計算機中的樹呢，是一種非線性結構，是由 n(n>=0) 個有限節點組成一個具有層次關系的集合。當 n==0 也就是沒有節點的樹，我們稱為空樹！
這裡我們要註意幾點：
- 樹的根節點為最頂層的節點，根節點沒有前驅
- 除瞭根節點之外，其餘節點被分為 M(M>0) 個不相交的集合，又是一棵樹，我們把這種樹稱為子樹，每棵子樹的根節點有且隻有一個前驅，可以有0個或者多個後繼
- 樹是遞歸定義的
這也不像一棵樹啊，是的，但是他像一顆倒過來的樹😏 。
註意：在樹型結構中，子樹之間不能相交，比如上圖中如果 B 與 C 有相交關系瞭，也就是他倆連起來瞭，那麼這就不能稱之為樹！
樹的概念
還是拿這張圖來說，我們來聊一聊樹的概念。
節點的度：一個節點含有子樹的個數，也就是他可以分出多少個子樹，比如節點 A 的度為 3，節點 F 的度為1。
樹的度：一棵樹中，所有節點的度裡面的最大值，就是這棵樹的度，上圖樹的度為 3。
葉子節點或終端節點：度為0的節點為葉子節點，也就是說，該節點沒有任何子樹。上圖 C E G H 就是葉子節點。
雙親節點或父節點：如果一個節點含有子節點，則這個節點稱為其子節點的父節點，上圖 B 是 F 的父節點，但是 B 不是 H 的父節點，H 並不是 B 的子節點，而是 F 的子節點，【B是F的父親，F又是 H 的父親，那麼 B 不就是 H 的爺爺嗎？(dog)。】
孩子節點或子節點：如果一個節點含有子樹，那麼這個子樹的根節點就為該節點的子節點，上圖 B 是 A 的子節點，但 E 並不是 A 的子節點。
根節點：一棵樹中，沒有父節點的樹為根節點，上圖 A 為根節點。
節點的層次：從根節點開始，根為第一層，根的子節點為第二層，以此類推，上圖B是第二層，H是第四層。
樹的高度：樹中節點的最大層次，上圖樹的深度為 4。
下面的概念不是很重要，瞭解即可：
非終端節點或分支節點：度不為0的節點，也就是有孩子的節點，都為非終端節點，如上圖A B D F。
兄弟節點：具有相同父節點的節點為兄弟節點，如上圖 E 和 F 互為兄弟節點。
堂兄弟節點：父節點在同一層的節點互為堂兄弟，如上圖 F 和 G 互為堂兄弟節點。
祖先節點：從根到該節點所經分支上的所有節點，都為該節點的祖先節點，如上圖 A 是所有節點的祖先節點。
子孫：以某節點為根的子樹中任意一個節點都稱為該節點的子孫，如上圖 F 是 A 的子孫節點，也是 B 的子孫節點。
森林：由m(m>=0) 顆互不相交的樹組成的集合叫做森林，一棵樹也可以叫做森林。
樹的表示形式
樹結構不同於我們前面學習的順序結構，樹型結構的表示方式就有很多瞭，比如：雙親表示法，孩子表示法，孩子雙親表示法，孩子兄弟表示法等等，最常用的還是孩子兄弟表示法。
孩子兄弟表示法：
二叉樹
二叉樹的概念
二叉樹是一個有限的集合，該集合為空，或者是由一個根節點和兩顆子樹構成，分別為左子樹和右子樹，隻含有一個根節點的也可也稱為二叉樹。
註意：
- 二叉樹不存在度大於2的節點
- 二叉樹的子樹有左右之分
- 每個子樹的根節點往下都可看作一個新的二叉樹
- 空樹和隻有一個節點的樹都可以稱為二叉樹
- 根節點隻有左樹（或右樹）並滿足節點度不大於2的情況下，也是二叉樹
特殊的二叉樹
這裡有個問題，前面學習的 Stack 和 ArrayList 需要判斷滿的情況並擴容，那麼二叉樹可能出現滿的情況嗎？顯然不會，因為二叉樹是由節點構造而成的，但是如果每層的節點數都達到瞭最大值，那麼這棵樹就是滿二叉樹。換句話說，如果一顆二叉樹的層數為k，且總結點的個數是2^k-1，那麼就是滿二叉樹。
滿二叉樹圖例：
第二個概念：完全二叉樹，籃球哥這裡用簡短的話來描述，每一層的節點都是從左往右的，依次排列，中間不能空， 完全二叉樹是一種效率很高的數據結構，後續講優先級隊列會講解到，理論看不明白沒關系，我們直接看圖：
二叉樹的性質
性質1: 如果規定根節點的層數為1，那麼一顆非空的二叉樹的第 k 層上最多有 2^(k-1) 個節點 k>0。
性質2: 如果規定隻有根節點的二叉樹的深度為 1，則深度為 k 的二叉樹的最大節點數是 2^k – 1（k >= 0）。
性質3: 對於任何一棵二叉樹，如果葉子(度為0)節點的個數為 n0，度為2的非葉子節點的個數為 n2，則 n0 = n2 + 1。
性質4: 具有 n 個節點的完全二叉樹的深度 k 為 log(n+1) 上取整。（以2為底）
性質5: 對於具有n個節點的完全二叉樹，如果從上至下，從左至右的順序對所有的節點從 0 開始進行編號，如果父節點下標為 i，左孩子節點下標為：2 * i + 1 且 < n，右孩子下標為：2 * i + 2 且 < n，已知孩子節點下標，求父節點：(i – 1) / 2 = 父節點下標，若 i = 0，則 i 為根節點編號。
二叉樹性質相關習題
1. 某二叉樹共有 399 個結點，其中有 199 個度為 2 的結點，則該二叉樹中的葉子結點數為（ ）
A.不存在這樣的二叉樹 B.200 C.198 D.199
題解： 這道題我們可以運用上面的二叉樹的性質3，任意一顆二叉樹中，度為2比度為0的節點多一個，那題目告訴我們有 199 個度為 2 的節點，所以度為 0 的節點就是 199 + 1，本題選 A
2.在具有 2n 個結點的完全二叉樹中，葉子結點個數為（ ）
A.n B.n+1 C.n-1 D.n/2
題解：因為二叉樹不存在度大於 2 的節點，因此我們可知，度為0的節點 + 度為1的節點 + 度為2的節點 = 2n。 設度為 0 的節點為 n0，度為 1 的節點為 n1，度為 2 的節點為 n2，所以：n0 + n1 + n2 = 2n。得出瞭這個公式，後面就好辦瞭，我們看圖：
3.一個具有767個節點的完全二叉樹，其葉子節點個數為（）
A.383 B.384 C.385 D.386
題解：這道題跟上一道題思路類似，同樣可以設：度為 0 的節點為 n0，度為 1 的節點為 n1，度為 2 的節點為 n2， 那麼是不是得出：767 = n0 + n1 + n2，後面豈不是好辦瞭嗎？直接看圖：
4.一棵完全二叉樹的節點數為531個，那麼這棵樹的高度為（ ）
A.11 B.10 C.8 D.12
這個題就比較簡單瞭， 運用上面二叉樹的性質2，即：531 = 2^k – 1，532 = 2^k
k等於多少？當k等於9時，2^9 = 512，即k=9當前完全二叉樹最大節點數為512小於531，不滿足題意，當k等於10時，2^10 = 1024，滿足題意，所以本題選 B！
實現二叉樹的基本操作
瞭解二叉樹的存儲結構
二叉樹的存儲結構分為順序存儲和鏈式存儲，順序存儲後續講解優先級隊列會講，鏈式存儲跟前面的鏈表還是有一定區別的。
二叉樹的鏈式存儲也是由一個個節點構成的，通常采用二叉鏈和三叉鏈(平衡二叉樹…)
// 孩子表示法
public class TreeNode {
private char val; //數據域
private TreeNode left; //左孩子的引用，以左孩子為根的整棵樹
private TreeNode right; //右孩子的引用，以右孩子為根的整棵樹
}
// 孩子雙親表示法
public class TreeNode {
private char val; //數據域
private TreeNode left; //左孩子的引用，以左孩子為根的整棵樹
private TreeNode right; //右孩子的引用，以右孩子為根的整棵樹
private TreeNode parent; //當前節點的根節點的引用
}
簡單構造一棵二叉樹
由於目前的學習深度不夠，為瞭降低成本，我們需要先學習簡單的二叉樹的操作， 熟練掌握這些操作之後，下期我們在講解二叉樹的練習題時會講到如何構造一顆二叉樹，比如將字符串轉換成二叉樹，而這裡我們采用列舉的方法來構造一顆二叉樹。
如圖：
public TreeNode creationTree() {
// 這裡我們用列舉的方法創建一顆樹
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
return A;
}
這樣我們就簡單構造出如上圖一樣的一顆二叉樹瞭，下面我們將學習二叉樹的一些相關操作，測試樣例都是在上圖的基礎上進行測試。
二叉樹的前序遍歷
前序遍歷就是先訪問根節點，在訪問左子樹，根的右子樹，這裡我們一定要弄清楚一個點，根的左子樹和右子樹也可以看成一棵二叉樹，根的左子樹的根節點的左右子樹又是一棵二叉樹。
// 前序遍歷 -> 根 左子樹 右子樹
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
// 碰到根節點就打印
System.out.print(root.val + " ");
// 遍歷左子樹
preOrder(root.left);
// 遍歷右子樹
preOrder(root.right);
}
初學者看不懂這個代碼沒關系，博主來畫遞歸展開圖來詳細介紹。
由這個遞歸展開圖相信也能看明白，碰到根節點就打印，然後就去遍歷當前根的左子樹，如果實在不理解，就把博主的代碼粘貼下去畫遞歸展開圖，多畫幾遍，你就能慢慢理解遞歸瞭！
按照我們這棵樹，此時的前序遍歷就是：A B D E C F
二叉樹的中序
中序遍歷：根的左子樹 -> 根 -> 根的右子樹
後序遍歷：根的左子樹 -> 根的右子樹 -> 根
代碼實現：
// 中序遍歷 -> 左子樹 根 右子樹
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
// 遍歷左子樹
inOrder(root.left);
// 打印根節點
System.out.print(root.val + " ");
// 遍歷右子樹
inOrder(root.right);
}
// 後序遍歷 -> 左子樹 右子樹 根
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
// 遍歷左子樹
postOrder(root.left);
// 遍歷右子樹
postOrder(root.right);
// 打印根節點
System.out.print(root.val + " ");
}
至於遞歸展開圖，博主就不畫瞭，不理解的小夥伴可以自己去畫一畫，還是那句話，數據結構多畫圖！
獲取二叉樹節點的個數
這道題我們仍然可以采用前序遍歷的思想，先看代碼，在作解釋：
// 獲取二叉樹中節點的個數
public int size(TreeNode root) {
// 采用前序遍歷的方式來獲取這個樹的節點個數
if (root == null) {
return 0;
}
return size(root.left) + size(root.right) + 1;
}
如果以任意一顆樹的根節點的角度看，我的左子樹為null，我的右子樹也為空，那麼是不是意味著這顆子樹走完瞭，也就是上述方法結束瞭，既然我方法結束瞭，我是不是要歸回去，遞歸從哪來回哪去，那麼是不是也要統計一下走完的這個根節點，也即加1，這個代碼采用的是子問題思想，如果還不熟悉遞歸，一定要下去畫遞歸展開圖，就像博主畫上面前序遍歷那樣。
獲取二叉樹葉子節點個數
// 獲取葉子節點的個數
public int getLeafNodeCount(TreeNode root) {
if (root == null) {
return 0;
}
// 葉子節點的左孩子和右孩子都為null
if (root.left == null && root.right == null) {
return 1;
}
return getLeafNodeCount(root.left)
+ getLeafNodeCount(root.right);
}
在二叉樹的性質，我們提到過，葉子節點的左子樹為空，右子樹也為空，如果采用子問題思路，可以寫出如上的代碼。 如果不理解這個遞歸，一定要畫遞歸展開圖哦，多畫幾次就理解瞭！
獲取第k層的節點個數
這個方法其實很簡單，前面我們會求節點個數，那麼第 k 層的節點個數，是不是就是第 k-1 層的子節點個數呢？所以當我們遞歸到第 k 層的時候，我們就不用往後遞歸瞭。
// 獲取第K層節點的個數
public int getKLevelNodeCount(TreeNode root, int k) {
// 第k層節點的個數，也就是第k-1層的子節點個數
if (root == null) {
return 0;
}
if (k == 1) {
return 1;
}
return getKLevelNodeCount(root.left, k - 1)
+ getKLevelNodeCount(root.right, k - 1);
}
獲取二叉樹的高度
二叉樹的高度，如果用子問題方法來解決的話，那是不是以任意一個根節點為樹的高度都是左子樹右子樹的高度較大值+1 ？
// 獲取二叉樹的高度
public int getHeight(TreeNode root) {
// 求左子樹的高度和右子樹的高度，返回他們的較大值
if (root == null) {
return 0;
}
int leftH = getHeight(root.left);
int rightH = getHeight(root.right);
return leftH > rightH ? leftH + 1 : rightH + 1;
}
檢測值為value的元素是否存在
這道題仍然可以采用遍歷二叉樹的思想，我們要註意的是，如果找到瞭這個節點，是不是就不用遞歸瞭？換句話說，如果我在任意一棵左子樹中找到瞭val，我還需要去右子樹找嗎？肯定是不需要的，如果左子樹右子樹都找完瞭，還是找不到，就返回 null 瞭。
// 檢測值為value的元素是否存在
TreeNode find(TreeNode root, char val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
// 遞歸左子樹和右子樹
TreeNode l = find(root.left, val);
if (l != null) {
//如果我的左子樹返回值不為null,表示在左子樹找到瞭val值對應的節點
//直接返回該節點,不用再去遞歸右子樹瞭！
return l;
}
TreeNode r = find(root.right, val);
if (r != null) {
//如果我的右子樹返回值不為null,表示在右子樹找到瞭val值對應的節點
return r;
}
return null;
}
層序遍歷
解決這個方法我們來換一種思路，采用非遞歸的方式，思路是這樣的，定義一個隊列，先把根節點入隊，如果隊列不為空，將隊頭的元素出隊放入臨時變量中，接著入隊臨時變量不為空的左右子節點，左右節點為 null 則不入隊，上述循環，當隊列為空，層序遍歷結束。
//層序遍歷
public void levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
//出隊頭元素
TreeNode tmp = queue.poll();
System.out.print(tmp.val + " ");
if (tmp.left != null) {
queue.offer(tmp.left);
}
if (tmp.right != null) {
queue.offer(tmp.right);
}
}
}
判斷一棵二叉樹是否為完全二叉樹
這個方法實現思路跟上述差不多，具體就是左右子樹為null的時候也要入棧，當發現出隊出到瞭null，如果是完全二叉樹，隊列的後續節點應該都為空，否則則不是完全二叉樹！
以上就是二叉樹的一些基本操作瞭，有瞭二叉樹的基礎，我們後面學習優先級隊列或者二叉搜索樹會更輕松，初學者剛接觸二叉樹可能有點難，但不用擔心，慢慢來就好，多畫圖。
以上就是Java 數據結構之樹和二叉樹的相關資料的詳細內容，更多關於Java 樹和二叉樹的資料請關註WalkonNet其它相關文章！,希望大傢以後多多支持WalkonNet！
推薦閱讀：
- C++實現LeetCode(105.由先序和中序遍歷建立二叉樹)
- Java二叉樹的四種遍歷（遞歸與非遞歸）
- Python 遞歸式實現二叉樹前序,中序,後序遍歷
- C++實現LeetCode(106.由中序和後序遍歷建立二叉樹)
- java基礎二叉搜索樹圖文詳解