一棵倒立過來的樹.?
目錄
1、什么是樹？
1.1 簡單認識樹?
1.2 樹的概念?
1.3 樹的表示形式
2、二叉樹
2.1 二叉樹的概念
2.2 特殊的二叉樹
2.3 二叉樹的性質(zhì)
2.4 二叉樹性質(zhì)相關(guān)習(xí)題
3、實現(xiàn)二叉樹的基本操作
3.1 了解二叉樹的存儲結(jié)構(gòu)
3.2 簡單構(gòu)造一棵二叉樹
3.3 二叉樹的前序遍歷
3.4 二叉樹的中序，后序遍歷
3.5 獲取二叉樹節(jié)點的個數(shù)
3.6 獲取二叉樹葉子節(jié)點個數(shù)
3.7 獲取第k層的節(jié)點個數(shù)
3.8 獲取二叉樹的高度
3.9 檢測值為value的元素是否存在
3.10 層序遍歷
3.11 判斷一棵二叉樹是否為完全二叉樹
1、什么是樹？
1.1 簡單認識樹?
在生活中，有楊樹，石榴樹，棗樹，而在計算機中的樹呢，是一種非線性結(jié)構(gòu)，是由 n(n>=0) 個有限節(jié)點組成一個具有層次關(guān)系的集合。當(dāng) n==0 也就是沒有節(jié)點的樹，我們稱為空樹！
這里我們要注意幾點：
- 樹的根節(jié)點為最頂層的節(jié)點，根節(jié)點沒有前驅(qū)
- 除了根節(jié)點之外，其余節(jié)點被分為 M(M>0) 個不相交的集合，又是一棵樹，我們把這種樹稱為子樹，每棵子樹的根節(jié)點有且只有一個前驅(qū)，可以有0個或者多個后繼
- 樹是遞歸定義的
?
這也不像一棵樹啊，是的，但是他像一顆倒過來的樹?? 。
注意：在樹型結(jié)構(gòu)中，子樹之間不能相交，比如上圖中如果 B 與 C 有相交關(guān)系了，也就是他倆連起來了，那么這就不能稱之為樹！
1.2 樹的概念?
還是拿這張圖來說，我們來聊一聊樹的概念。
節(jié)點的度：一個節(jié)點含有子樹的個數(shù)，也就是他可以分出多少個子樹，比如節(jié)點 A 的度為 3，節(jié)點 F 的度為1。
樹的度：一棵樹中，所有節(jié)點的度里面的最大值，就是這棵樹的度，上圖樹的度為 3。
葉子節(jié)點或終端節(jié)點：度為0的節(jié)點為葉子節(jié)點，也就是說，該節(jié)點沒有任何子樹。上圖 C E?G H?就是葉子節(jié)點。
雙親節(jié)點或父節(jié)點：如果一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點，上圖 B 是 F 的父節(jié)點，但是 B 不是 H 的父節(jié)點，H 并不是 B 的子節(jié)點，而是 F 的子節(jié)點，【B是F的父親，F(xiàn)又是 H 的父親，那么 B?不就是 H 的爺爺嗎？(dog)。】
孩子節(jié)點或子節(jié)點：如果一個節(jié)點含有子樹，那么這個子樹的根節(jié)點就為該節(jié)點的子節(jié)點，上圖 B 是 A 的子節(jié)點，但 E 并不是 A 的子節(jié)點。
根節(jié)點：一棵樹中，沒有父節(jié)點的樹為根節(jié)點，上圖 A 為根節(jié)點。
節(jié)點的層次：從根節(jié)點開始，根為第一層，根的子節(jié)點為第二層，以此類推，上圖B是第二層，H是第四層。
樹的高度：樹中節(jié)點的最大層次，上圖樹的深度為 4。
下面的概念不是很重要，了解即可：
非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點，也就是有孩子的節(jié)點，都為非終端節(jié)點，如上圖A B D F。
兄弟節(jié)點：具有相同父節(jié)點的節(jié)點為兄弟節(jié)點，如上圖 E 和 F 互為兄弟節(jié)點。
堂兄弟節(jié)點：父節(jié)點在同一層的節(jié)點互為堂兄弟，如上圖 F 和 G 互為堂兄弟節(jié)點。
祖先節(jié)點：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點，都為該節(jié)點的祖先節(jié)點，如上圖?A 是所有節(jié)點的祖先節(jié)點。
子孫：以某節(jié)點為根的子樹中任意一個節(jié)點都稱為該節(jié)點的子孫，如上圖 F 是 A 的子孫節(jié)點，也是 B 的子孫節(jié)點。
森林：由m(m>=0) 顆互不相交的樹組成的集合叫做森林，一棵樹也可以叫做森林。
1.3 樹的表示形式
樹結(jié)構(gòu)不同于我們前面學(xué)習(xí)的順序結(jié)構(gòu)，樹型結(jié)構(gòu)的表示方式就有很多了，比如：雙親表示法，孩子表示法，孩子雙親表示法，孩子兄弟表示法等等，最常用的還是孩子兄弟表示法。
孩子兄弟表示法：
2、二叉樹
2.1 二叉樹的概念
二叉樹是一個有限的集合，該集合為空，或者是由一個根節(jié)點和兩顆子樹構(gòu)成，分別為左子樹和右子樹，只含有一個根節(jié)點的也可也稱為二叉樹。
注意：
- 二叉樹不存在度大于2的節(jié)點
- 二叉樹的子樹有左右之分
- 每個子樹的根節(jié)點往下都可看作一個新的二叉樹
- 空樹和只有一個節(jié)點的樹都可以稱為二叉樹
- 根節(jié)點只有左樹（或右樹）并滿足節(jié)點度不大于2的情況下，也是二叉樹
2.2 特殊的二叉樹
這里有個問題，前面學(xué)習(xí)的 Stack 和 ArrayList 需要判斷滿的情況并擴容，那么二叉樹可能出現(xiàn)滿的情況嗎？顯然不會，因為二叉樹是由節(jié)點構(gòu)造而成的，但是如果每層的節(jié)點數(shù)都達到了最大值，那么這棵樹就是滿二叉樹。換句話說，如果一顆二叉樹的層數(shù)為k，且總結(jié)點的個數(shù)是2^k-1，那么就是滿二叉樹。滿二叉樹圖例：
第二個概念：完全二叉樹，籃球哥這里用簡短的話來描述，每一層的節(jié)點都是從左往右的，依次排列，中間不能空，?完全二叉樹是一種效率很高的數(shù)據(jù)結(jié)構(gòu)，后續(xù)講優(yōu)先級隊列會講解到，理論看不明白沒關(guān)系，我們直接看圖：
2.3 二叉樹的性質(zhì)
性質(zhì)1:?如果規(guī)定根節(jié)點的層數(shù)為1，那么一顆非空的二叉樹的第 k 層上最多有 2^(k-1) 個節(jié)點 k>0。
性質(zhì)2:?如果規(guī)定只有根節(jié)點的二叉樹的深度為 1，則深度為 k 的二叉樹的最大節(jié)點數(shù)是 2^k - 1（k >= 0）。
性質(zhì)3:?對于任何一棵二叉樹，如果葉子(度為0)節(jié)點的個數(shù)為 n0，度為2的非葉子節(jié)點的個數(shù)為 n2，則 n0 = n2 + 1。
性質(zhì)4:?具有 n 個節(jié)點的完全二叉樹的深度 k 為 log(n+1) 上取整。（以2為底）
性質(zhì)5: 對于具有n個節(jié)點的完全二叉樹，如果從上至下，從左至右的順序?qū)λ械墓?jié)點從 0 開始進行編號，如果父節(jié)點下標(biāo)為 i，左孩子節(jié)點下標(biāo)為：2 * i + 1 且 < n，右孩子下標(biāo)為：2 * i + 2?且 < n，已知孩子節(jié)點下標(biāo)，求父節(jié)點：(i - 1) / 2 = 父節(jié)點下標(biāo)，若 i = 0，則 i 為根節(jié)點編號。?
2.4 二叉樹性質(zhì)相關(guān)習(xí)題
1. 某二叉樹共有 399 個結(jié)點，其中有 199 個度為 2 的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)為（ ）
A.不存在這樣的二叉樹? ? B.200? ? C.198? ? D.199
題解： 這道題我們可以運用上面的二叉樹的性質(zhì)3，任意一顆二叉樹中，度為2比度為0的節(jié)點多一個，那題目告訴我們有 199 個度為 2 的節(jié)點，所以度為 0 的節(jié)點就是 199 + 1，本題選 A
2.在具有 2n 個結(jié)點的完全二叉樹中，葉子結(jié)點個數(shù)為（ ）
A.n? ? B.n+1? ? C.n-1? ? D.n/2
題解：因為二叉樹不存在度大于 2 的節(jié)點，因此我們可知，度為0的節(jié)點 + 度為1的節(jié)點 + 度為2的節(jié)點 = 2n。?設(shè)度為 0 的節(jié)點為 n0，度為 1 的節(jié)點為 n1，度為 2 的節(jié)點為 n2，所以：n0 + n1 + n2 = 2n。得出了這個公式，后面就好辦了，我們看圖：
3.一個具有767個節(jié)點的完全二叉樹，其葉子節(jié)點個數(shù)為（）
A.383? ? B.384? ? C.385? ? D.386?
題解：這道題跟上一道題思路類似，同樣可以設(shè)：度為 0 的節(jié)點為 n0，度為 1 的節(jié)點為 n1，度為 2 的節(jié)點為 n2，?那么是不是得出：767 = n0 + n1 + n2，后面豈不是好辦了嗎？直接看圖：
4.一棵完全二叉樹的節(jié)點數(shù)為531個，那么這棵樹的高度為（ ）
A.11? ? B.10? ? C.8? ? D.12?
這個題就比較簡單了，?運用上面二叉樹的性質(zhì)2，即：531 = 2^k - 1，532 = 2^k
k等于多少？當(dāng)k等于9時，2^9 = 512，即k=9當(dāng)前完全二叉樹最大節(jié)點數(shù)為512小于531，不滿足題意，當(dāng)k等于10時，2^10 = 1024，滿足題意，所以本題選 B！
3、實現(xiàn)二叉樹的基本操作
3.1 了解二叉樹的存儲結(jié)構(gòu)
二叉樹的存儲結(jié)構(gòu)分為順序存儲和鏈?zhǔn)酱鎯?，順序存儲后續(xù)講解優(yōu)先級隊列會講，鏈?zhǔn)酱鎯Ω懊娴逆湵磉€是有一定區(qū)別的。
二叉樹的鏈?zhǔn)酱鎯σ彩怯梢粋€個節(jié)點構(gòu)成的，通常采用二叉鏈和三叉鏈(平衡二叉樹...)?
// 孩子表示法
public class TreeNode {
private char val; //數(shù)據(jù)域
private TreeNode left; //左孩子的引用，以左孩子為根的整棵樹
private TreeNode right; //右孩子的引用，以右孩子為根的整棵樹
}
// 孩子雙親表示法
public class TreeNode {
private char val; //數(shù)據(jù)域
private TreeNode left; //左孩子的引用，以左孩子為根的整棵樹
private TreeNode right; //右孩子的引用，以右孩子為根的整棵樹
private TreeNode parent; //當(dāng)前節(jié)點的根節(jié)點的引用
}3.2 簡單構(gòu)造一棵二叉樹
由于目前的學(xué)習(xí)深度不夠，為了降低成本，我們需要先學(xué)習(xí)簡單的二叉樹的操作，?熟練掌握這些操作之后，下期我們在講解二叉樹的練習(xí)題時會講到如何構(gòu)造一顆二叉樹，比如將字符串轉(zhuǎn)換成二叉樹，而這里我們采用列舉的方法來構(gòu)造一顆二叉樹。
如圖：
public TreeNode creationTree() {
// 這里我們用列舉的方法創(chuàng)建一顆樹
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;
}這樣我們就簡單構(gòu)造出如上圖一樣的一顆二叉樹了，下面我們將學(xué)習(xí)二叉樹的一些相關(guān)操作，測試樣例都是在上圖的基礎(chǔ)上進行測試。
3.3 二叉樹的前序遍歷
前序遍歷就是先訪問根節(jié)點，在訪問左子樹，根的右子樹，這里我們一定要弄清楚一個點，根的左子樹和右子樹也可以看成一棵二叉樹，根的左子樹的根節(jié)點的左右子樹又是一棵二叉樹。
// 前序遍歷 -> 根 左子樹 右子樹
public void preOrder(TreeNode root) {
if (root == null) {
return;
}
// 碰到根節(jié)點就打印
System.out.print(root.val + " ");
// 遍歷左子樹
preOrder(root.left);
// 遍歷右子樹
preOrder(root.right);
}初學(xué)者看不懂這個代碼沒關(guān)系，博主來畫遞歸展開圖來詳細介紹。
由這個遞歸展開圖相信也能看明白，碰到根節(jié)點就打印，然后就去遍歷當(dāng)前根的左子樹，如果實在不理解，就把博主的代碼粘貼下去畫遞歸展開圖，多畫幾遍，你就能慢慢理解遞歸了！?
按照我們這棵樹，此時的前序遍歷就是：A? B? D? E? C? F?
3.4 二叉樹的中序，后序遍歷
有了前序遍歷的學(xué)習(xí)，其實中序后序遍歷就很簡單了，但是我們還是要了解他們的概念。
- 中序遍歷：根的左子樹 -> 根 -> 根的右子樹
- 后序遍歷：根的左子樹 -> 根的右子樹 -> 根?
代碼實現(xiàn)：
// 中序遍歷 -> 左子樹 根 右子樹
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
// 遍歷左子樹
inOrder(root.left);
// 打印根節(jié)點
System.out.print(root.val + " ");
// 遍歷右子樹
inOrder(root.right);
}
// 后序遍歷 -> 左子樹 右子樹 根
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
// 遍歷左子樹
postOrder(root.left);
// 遍歷右子樹
postOrder(root.right);
// 打印根節(jié)點
System.out.print(root.val + " ");
}至于遞歸展開圖，博主就不畫了，不理解的小伙伴可以自己去畫一畫，還是那句話，數(shù)據(jù)結(jié)構(gòu)多畫圖！
3.5 獲取二叉樹節(jié)點的個數(shù)
這道題我們?nèi)匀豢梢圆捎们靶虮闅v的思想，先看代碼，在作解釋：
// 獲取二叉樹中節(jié)點的個數(shù)
public int size(TreeNode root) {
// 采用前序遍歷的方式來獲取這個樹的節(jié)點個數(shù)
if (root == null) {
return 0;
}
return size(root.left) + size(root.right) + 1;
}如果以任意一顆樹的根節(jié)點的角度看，我的左子樹為null，我的右子樹也為空，那么是不是意味著這顆子樹走完了，也就是上述方法結(jié)束了，既然我方法結(jié)束了，我是不是要歸回去，遞歸從哪來回哪去，那么是不是也要統(tǒng)計一下走完的這個根節(jié)點，也即加1，這個代碼采用的是子問題思想，如果還不熟悉遞歸，一定要下去畫遞歸展開圖，就像博主畫上面前序遍歷那樣。
3.6 獲取二叉樹葉子節(jié)點個數(shù)
// 獲取葉子節(jié)點的個數(shù)
public int getLeafNodeCount(TreeNode root) {
if (root == null) {
return 0;
}
// 葉子節(jié)點的左孩子和右孩子都為null
if (root.left == null && root.right == null) {
return 1;
}
return getLeafNodeCount(root.left)
+ getLeafNodeCount(root.right);
}在二叉樹的性質(zhì)，我們提到過，葉子節(jié)點的左子樹為空，右子樹也為空，如果采用子問題思路，可以寫出如上的代碼。 如果不理解這個遞歸，一定要畫遞歸展開圖哦，多畫幾次就理解了！
3.7 獲取第k層的節(jié)點個數(shù)
這個方法其實很簡單，前面我們會求節(jié)點個數(shù)，那么第 k 層的節(jié)點個數(shù)，是不是就是第 k-1 層的子節(jié)點個數(shù)呢？所以當(dāng)我們遞歸到第 k 層的時候，我們就不用往后遞歸了。
// 獲取第K層節(jié)點的個數(shù)
public int getKLevelNodeCount(TreeNode root, int k) {
// 第k層節(jié)點的個數(shù)，也就是第k-1層的子節(jié)點個數(shù)
if (root == null) {
return 0;
}
if (k == 1) {
return 1;
}
return getKLevelNodeCount(root.left, k - 1)
+ getKLevelNodeCount(root.right, k - 1);
}3.8 獲取二叉樹的高度
二叉樹的高度，如果用子問題方法來解決的話，那是不是以任意一個根節(jié)點為樹的高度都是左子樹右子樹的高度較大值+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;
}3.9 檢測值為value的元素是否存在
這道題仍然可以采用遍歷二叉樹的思想，我們要注意的是，如果找到了這個節(jié)點，是不是就不用遞歸了？換句話說，如果我在任意一棵左子樹中找到了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值對應(yīng)的節(jié)點
//直接返回該節(jié)點,不用再去遞歸右子樹了！
return l;
}
TreeNode r = find(root.right, val);
if (r != null) {
//如果我的右子樹返回值不為null,表示在右子樹找到了val值對應(yīng)的節(jié)點
return r;
}
return null;
}3.10 層序遍歷
解決這個方法我們來換一種思路，采用非遞歸的方式，思路是這樣的，定義一個隊列，先把根節(jié)點入隊，如果隊列不為空，將隊頭的元素出隊放入臨時變量中，接著入隊臨時變量不為空的左右子節(jié)點，左右節(jié)點為 null 則不入隊，上述循環(huán)，當(dāng)隊列為空，層序遍歷結(jié)束。
//層序遍歷
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);
}
}
}3.11 判斷一棵二叉樹是否為完全二叉樹
這個方法實現(xiàn)思路跟上述差不多，具體就是左右子樹為null的時候也要入棧，當(dāng)發(fā)現(xiàn)出隊出到了null，如果是完全二叉樹，隊列的后續(xù)節(jié)點應(yīng)該都為空，否則則不是完全二叉樹！
// 判斷一棵樹是不是完全二叉樹
public boolean isCompleteTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode tmp = queue.poll();
if (tmp != null) {
queue.offer(tmp.left);
queue.offer(tmp.right);
} else {
// 走到這里表示碰到了null節(jié)點，因為是完全二叉樹，而我們又是層序遍歷
// 所以此時如果是完全二叉樹的情況，隊列剩下的元素都是null
// 在遍歷隊列剩余的元素中，一旦發(fā)現(xiàn)不為有一個元素不為null，都不是完全二叉樹
while (!queue.isEmpty()) {
tmp = queue.poll();
if (tmp != null) {
return false;
}
}
}
}
return true;
}以上就是二叉樹的一些基本操作了，有了二叉樹的基礎(chǔ)，我們后面學(xué)習(xí)優(yōu)先級隊列或者二叉搜索樹會更輕松，初學(xué)者剛接觸二叉樹可能有點難，但不用擔(dān)心，慢慢來就好，多畫圖。文章來源：http://www.zghlxwxcb.cn/news/detail-794562.html
下期預(yù)告：【Java 數(shù)據(jù)結(jié)構(gòu)】優(yōu)先級隊列文章來源地址http://www.zghlxwxcb.cn/news/detail-794562.html
到了這里，關(guān)于【Java 數(shù)據(jù)結(jié)構(gòu)】樹和二叉樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
