什么是樹？

簡單認(rèn)識樹 

在生活中，有楊樹，石榴樹，棗樹，而在計(jì)算機(jī)中的樹呢，是一種非線性結(jié)構(gòu)，是由 n(n>=0) 個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。當(dāng) n==0 也就是沒有節(jié)點(diǎn)的樹，我們稱為空樹！

這里我們要注意幾點(diǎn)：

• 樹的根節(jié)點(diǎn)為最頂層的節(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)
• 除了根節(jié)點(diǎn)之外，其余節(jié)點(diǎn)被分為 M(M>0) 個(gè)不相交的集合，又是一棵樹，我們把這種樹稱為子樹，每棵子樹的根節(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或者多個(gè)后繼
• 樹是遞歸定義的

這也不像一棵樹啊，是的，但是他像一顆倒過來的樹?? 。

注意：在樹型結(jié)構(gòu)中，子樹之間不能相交，比如上圖中如果 B 與 C 有相交關(guān)系了，也就是他倆連起來了，那么這就不能稱之為樹！

樹的概念 

還是拿這張圖來說，我們來聊一聊樹的概念。

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有子樹的個(gè)數(shù)，也就是他可以分出多少個(gè)子樹，比如節(jié)點(diǎn) A 的度為 3，節(jié)點(diǎn) F 的度為1。

樹的度：一棵樹中，所有節(jié)點(diǎn)的度里面的最大值，就是這棵樹的度，上圖樹的度為 3。

葉子節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，也就是說，該節(jié)點(diǎn)沒有任何子樹。上圖 C E G H 就是葉子節(jié)點(diǎn)。

雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：如果一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)，上圖 B 是 F 的父節(jié)點(diǎn)，但是 B 不是 H 的父節(jié)點(diǎn)，H 并不是 B 的子節(jié)點(diǎn)，而是 F 的子節(jié)點(diǎn)，【B是F的父親，F(xiàn)又是 H 的父親，那么 B 不就是 H 的爺爺嗎？(dog)?！?/p>

孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：如果一個(gè)節(jié)點(diǎn)含有子樹，那么這個(gè)子樹的根節(jié)點(diǎn)就為該節(jié)點(diǎn)的子節(jié)點(diǎn)，上圖 B 是 A 的子節(jié)點(diǎn)，但 E 并不是 A 的子節(jié)點(diǎn)。

根節(jié)點(diǎn)：一棵樹中，沒有父節(jié)點(diǎn)的樹為根節(jié)點(diǎn)，上圖 A 為根節(jié)點(diǎn)。

節(jié)點(diǎn)的層次：從根節(jié)點(diǎn)開始，根為第一層，根的子節(jié)點(diǎn)為第二層，以此類推，上圖B是第二層，H是第四層。

樹的高度：樹中節(jié)點(diǎn)的最大層次，上圖樹的深度為 4。

下面的概念不是很重要，了解即可：

非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)，也就是有孩子的節(jié)點(diǎn)，都為非終端節(jié)點(diǎn)，如上圖A B D F。

兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)為兄弟節(jié)點(diǎn)，如上圖 E 和 F 互為兄弟節(jié)點(diǎn)。

堂兄弟節(jié)點(diǎn)：父節(jié)點(diǎn)在同一層的節(jié)點(diǎn)互為堂兄弟，如上圖 F 和 G 互為堂兄弟節(jié)點(diǎn)。

祖先節(jié)點(diǎn)：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)，都為該節(jié)點(diǎn)的祖先節(jié)點(diǎn)，如上圖 A 是所有節(jié)點(diǎn)的祖先節(jié)點(diǎn)。

子孫：以某節(jié)點(diǎn)為根的子樹中任意一個(gè)節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫，如上圖 F 是 A 的子孫節(jié)點(diǎn)，也是 B 的子孫節(jié)點(diǎn)。

森林：由m(m>=0) 顆互不相交的樹組成的集合叫做森林，一棵樹也可以叫做森林。

樹的表示形式

樹結(jié)構(gòu)不同于我們前面學(xué)習(xí)的順序結(jié)構(gòu)，樹型結(jié)構(gòu)的表示方式就有很多了，比如：雙親表示法，孩子表示法，孩子雙親表示法，孩子兄弟表示法等等，最常用的還是孩子兄弟表示法。

孩子兄弟表示法：

二叉樹

二叉樹的概念

二叉樹是一個(gè)有限的集合，該集合為空，或者是由一個(gè)根節(jié)點(diǎn)和兩顆子樹構(gòu)成，分別為左子樹和右子樹，只含有一個(gè)根節(jié)點(diǎn)的也可也稱為二叉樹。

注意：

• 二叉樹不存在度大于2的節(jié)點(diǎn)
• 二叉樹的子樹有左右之分
• 每個(gè)子樹的根節(jié)點(diǎn)往下都可看作一個(gè)新的二叉樹
• 空樹和只有一個(gè)節(jié)點(diǎn)的樹都可以稱為二叉樹
• 根節(jié)點(diǎn)只有左樹（或右樹）并滿足節(jié)點(diǎn)度不大于2的情況下，也是二叉樹

特殊的二叉樹

這里有個(gè)問題，前面學(xué)習(xí)的 Stack 和 ArrayList 需要判斷滿的情況并擴(kuò)容，那么二叉樹可能出現(xiàn)滿的情況嗎？顯然不會，因?yàn)槎鏄涫怯晒?jié)點(diǎn)構(gòu)造而成的，但是如果每層的節(jié)點(diǎn)數(shù)都達(dá)到了最大值，那么這棵樹就是滿二叉樹。換句話說，如果一顆二叉樹的層數(shù)為k，且總結(jié)點(diǎn)的個(gè)數(shù)是2^k-1，那么就是滿二叉樹。

滿二叉樹圖例：

第二個(gè)概念：完全二叉樹，籃球哥這里用簡短的話來描述，每一層的節(jié)點(diǎn)都是從左往右的，依次排列，中間不能空， 完全二叉樹是一種效率很高的數(shù)據(jù)結(jié)構(gòu)，后續(xù)講優(yōu)先級隊(duì)列會講解到，理論看不明白沒關(guān)系，我們直接看圖：

二叉樹的性質(zhì)

性質(zhì)1: 如果規(guī)定根節(jié)點(diǎn)的層數(shù)為1，那么一顆非空的二叉樹的第 k 層上最多有 2^(k-1) 個(gè)節(jié)點(diǎn) k>0。

性質(zhì)2: 如果規(guī)定只有根節(jié)點(diǎn)的二叉樹的深度為 1，則深度為 k 的二叉樹的最大節(jié)點(diǎn)數(shù)是 2^k - 1（k >= 0）。

性質(zhì)3: 對于任何一棵二叉樹，如果葉子(度為0)節(jié)點(diǎn)的個(gè)數(shù)為 n0，度為2的非葉子節(jié)點(diǎn)的個(gè)數(shù)為 n2，則 n0 = n2 + 1。

性質(zhì)4: 具有 n 個(gè)節(jié)點(diǎn)的完全二叉樹的深度 k 為 log(n+1) 上取整。（以2為底）

性質(zhì)5: 對于具有n個(gè)節(jié)點(diǎn)的完全二叉樹，如果從上至下，從左至右的順序?qū)λ械墓?jié)點(diǎn)從 0 開始進(jìn)行編號，如果父節(jié)點(diǎn)下標(biāo)為 i，左孩子節(jié)點(diǎn)下標(biāo)為：2 * i + 1 且 < n，右孩子下標(biāo)為：2 * i + 2 且 < n，已知孩子節(jié)點(diǎn)下標(biāo)，求父節(jié)點(diǎn)：(i - 1) / 2 = 父節(jié)點(diǎn)下標(biāo)，若 i = 0，則 i 為根節(jié)點(diǎn)編號。 

二叉樹性質(zhì)相關(guān)習(xí)題

1. 某二叉樹共有 399 個(gè)結(jié)點(diǎn)，其中有 199 個(gè)度為 2 的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)為（ ）

A.不存在這樣的二叉樹    B.200    C.198    D.199

題解： 這道題我們可以運(yùn)用上面的二叉樹的性質(zhì)3，任意一顆二叉樹中，度為2比度為0的節(jié)點(diǎn)多一個(gè)，那題目告訴我們有 199 個(gè)度為 2 的節(jié)點(diǎn)，所以度為 0 的節(jié)點(diǎn)就是 199 + 1，本題選 A

2.在具有 2n 個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為（ ）

A.n    B.n+1    C.n-1    D.n/2

題解：因?yàn)槎鏄洳淮嬖诙却笥?2 的節(jié)點(diǎn)，因此我們可知，度為0的節(jié)點(diǎn) + 度為1的節(jié)點(diǎn) + 度為2的節(jié)點(diǎn) = 2n。 設(shè)度為 0 的節(jié)點(diǎn)為 n0，度為 1 的節(jié)點(diǎn)為 n1，度為 2 的節(jié)點(diǎn)為 n2，所以：n0 + n1 + n2 = 2n。得出了這個(gè)公式，后面就好辦了，我們看圖：

3.一個(gè)具有767個(gè)節(jié)點(diǎn)的完全二叉樹，其葉子節(jié)點(diǎn)個(gè)數(shù)為（）

A.383    B.384    C.385    D.386 

題解：這道題跟上一道題思路類似，同樣可以設(shè)：度為 0 的節(jié)點(diǎn)為 n0，度為 1 的節(jié)點(diǎn)為 n1，度為 2 的節(jié)點(diǎn)為 n2， 那么是不是得出：767 = n0 + n1 + n2，后面豈不是好辦了嗎？直接看圖：

4.一棵完全二叉樹的節(jié)點(diǎn)數(shù)為531個(gè)，那么這棵樹的高度為（ ）

A.11    B.10    C.8    D.12 

這個(gè)題就比較簡單了， 運(yùn)用上面二叉樹的性質(zhì)2，即：531 = 2^k - 1，532 = 2^k

k等于多少？當(dāng)k等于9時(shí)，2^9 = 512，即k=9當(dāng)前完全二叉樹最大節(jié)點(diǎn)數(shù)為512小于531，不滿足題意，當(dāng)k等于10時(shí)，2^10 = 1024，滿足題意，所以本題選 B！

實(shí)現(xiàn)二叉樹的基本操作

了解二叉樹的存儲結(jié)構(gòu)

二叉樹的存儲結(jié)構(gòu)分為順序存儲和鏈?zhǔn)酱鎯?，順序存儲后續(xù)講解優(yōu)先級隊(duì)列會講，鏈?zhǔn)酱鎯Ω懊娴逆湵磉€是有一定區(qū)別的。

二叉樹的鏈?zhǔn)酱鎯σ彩怯梢粋€(gè)個(gè)節(jié)點(diǎn)構(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é)點(diǎn)的根節(jié)點(diǎn)的引用
}

簡單構(gòu)造一棵二叉樹

由于目前的學(xué)習(xí)深度不夠，為了降低成本，我們需要先學(xué)習(xí)簡單的二叉樹的操作， 熟練掌握這些操作之后，下期我們在講解二叉樹的練習(xí)題時(shí)會講到如何構(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ǔ)上進(jìn)行測試。

二叉樹的前序遍歷

前序遍歷就是先訪問根節(jié)點(diǎn)，在訪問左子樹，根的右子樹，這里我們一定要弄清楚一個(gè)點(diǎn)，根的左子樹和右子樹也可以看成一棵二叉樹，根的左子樹的根節(jié)點(diǎn)的左右子樹又是一棵二叉樹。

// 前序遍歷 -> 根 左子樹 右子樹
public void preOrder(TreeNode root) { 
    if (root == null) { 
        return; 
    } 
    // 碰到根節(jié)點(diǎn)就打印 
    System.out.print(root.val + " "); 
    // 遍歷左子樹 
    preOrder(root.left); 
    // 遍歷右子樹 
    preOrder(root.right);
}

初學(xué)者看不懂這個(gè)代碼沒關(guān)系，博主來畫遞歸展開圖來詳細(xì)介紹。

由這個(gè)遞歸展開圖相信也能看明白，碰到根節(jié)點(diǎn)就打印，然后就去遍歷當(dāng)前根的左子樹，如果實(shí)在不理解，就把博主的代碼粘貼下去畫遞歸展開圖，多畫幾遍，你就能慢慢理解遞歸了！ 

按照我們這棵樹，此時(shí)的前序遍歷就是：A  B  D  E  C  F 

二叉樹的中序

中序遍歷：根的左子樹 -> 根 -> 根的右子樹

后序遍歷：根的左子樹 -> 根的右子樹 -> 根 

代碼實(shí)現(xiàn)：

// 中序遍歷 -> 左子樹 根 右子樹
public void inOrder(TreeNode root) { 
    if (root == null) { 
        return; 
    } 
    // 遍歷左子樹 
    inOrder(root.left); 
    // 打印根節(jié)點(diǎn) 
    System.out.print(root.val + " "); 
    // 遍歷右子樹 
    inOrder(root.right);
}

// 后序遍歷 -> 左子樹 右子樹 根
public void postOrder(TreeNode root) { 
    if (root == null) { 
        return; 
    } 
    // 遍歷左子樹 
    postOrder(root.left); 
    // 遍歷右子樹 
    postOrder(root.right); 
    // 打印根節(jié)點(diǎn) 
    System.out.print(root.val + " ");
}

至于遞歸展開圖，博主就不畫了，不理解的小伙伴可以自己去畫一畫，還是那句話，數(shù)據(jù)結(jié)構(gòu)多畫圖！

獲取二叉樹節(jié)點(diǎn)的個(gè)數(shù)

這道題我們?nèi)匀豢梢圆捎们靶虮闅v的思想，先看代碼，在作解釋：

// 獲取二叉樹中節(jié)點(diǎn)的個(gè)數(shù)
public int size(TreeNode root) { 
    // 采用前序遍歷的方式來獲取這個(gè)樹的節(jié)點(diǎn)個(gè)數(shù) 
    if (root == null) { 
        return 0; 
    } 
    return size(root.left) + size(root.right) + 1;
}

如果以任意一顆樹的根節(jié)點(diǎn)的角度看，我的左子樹為null，我的右子樹也為空，那么是不是意味著這顆子樹走完了，也就是上述方法結(jié)束了，既然我方法結(jié)束了，我是不是要?dú)w回去，遞歸從哪來回哪去，那么是不是也要統(tǒng)計(jì)一下走完的這個(gè)根節(jié)點(diǎn)，也即加1，這個(gè)代碼采用的是子問題思想，如果還不熟悉遞歸，一定要下去畫遞歸展開圖，就像博主畫上面前序遍歷那樣。

獲取二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)

// 獲取葉子節(jié)點(diǎn)的個(gè)數(shù)
public int getLeafNodeCount(TreeNode root) { 
    if (root == null) { 
        return 0; 
    } 
    // 葉子節(jié)點(diǎn)的左孩子和右孩子都為null 
    if (root.left == null && root.right == null) { 
        return 1; 
    } 
    return getLeafNodeCount(root.left) 
            + getLeafNodeCount(root.right);
}

在二叉樹的性質(zhì)，我們提到過，葉子節(jié)點(diǎn)的左子樹為空，右子樹也為空，如果采用子問題思路，可以寫出如上的代碼。 如果不理解這個(gè)遞歸，一定要畫遞歸展開圖哦，多畫幾次就理解了！

獲取第k層的節(jié)點(diǎn)個(gè)數(shù)

這個(gè)方法其實(shí)很簡單，前面我們會求節(jié)點(diǎn)個(gè)數(shù)，那么第 k 層的節(jié)點(diǎn)個(gè)數(shù)，是不是就是第 k-1 層的子節(jié)點(diǎn)個(gè)數(shù)呢？所以當(dāng)我們遞歸到第 k 層的時(shí)候，我們就不用往后遞歸了。

// 獲取第K層節(jié)點(diǎn)的個(gè)數(shù)
public int getKLevelNodeCount(TreeNode root, int k) { 
    // 第k層節(jié)點(diǎn)的個(gè)數(shù)，也就是第k-1層的子節(jié)點(diǎn)個(gè)數(shù) 
    if (root == null) { 
        return 0; 
    } 
    if (k == 1) { 
        return 1; 
    } 
    return getKLevelNodeCount(root.left, k - 1) 
            + getKLevelNodeCount(root.right, k - 1);
}

獲取二叉樹的高度

二叉樹的高度，如果用子問題方法來解決的話，那是不是以任意一個(gè)根節(jié)點(diǎn)為樹的高度都是左子樹右子樹的高度較大值+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的元素是否存在

這道題仍然可以采用遍歷二叉樹的思想，我們要注意的是，如果找到了這個(gè)節(jié)點(diǎn)，是不是就不用遞歸了？換句話說，如果我在任意一棵左子樹中找到了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é)點(diǎn) 
        //直接返回該節(jié)點(diǎn),不用再去遞歸右子樹了！ 
        return l; 
    } 
    TreeNode r = find(root.right, val);
    if (r != null) { 
        //如果我的右子樹返回值不為null,表示在右子樹找到了val值對應(yīng)的節(jié)點(diǎn) 
        return r; 
    } 
    return null;
}

層序遍歷

解決這個(gè)方法我們來換一種思路，采用非遞歸的方式，思路是這樣的，定義一個(gè)隊(duì)列，先把根節(jié)點(diǎn)入隊(duì)，如果隊(duì)列不為空，將隊(duì)頭的元素出隊(duì)放入臨時(shí)變量中，接著入隊(duì)臨時(shí)變量不為空的左右子節(jié)點(diǎn)，左右節(jié)點(diǎn)為 null 則不入隊(duì)，上述循環(huán)，當(dāng)隊(duì)列為空，層序遍歷結(jié)束。

//層序遍歷
public void levelOrder(TreeNode root) { 
    Queue<TreeNode> queue = new LinkedList<>(); 
    queue.offer(root); 
    while (!queue.isEmpty()) { 
        //出隊(duì)頭元素 
        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); 
        } 
    }
}

判斷一棵二叉樹是否為完全二叉樹

這個(gè)方法實(shí)現(xiàn)思路跟上述差不多，具體就是左右子樹為null的時(shí)候也要入棧，當(dāng)發(fā)現(xiàn)出隊(duì)出到了null，如果是完全二叉樹，隊(duì)列的后續(xù)節(jié)點(diǎn)應(yīng)該都為空，否則則不是完全二叉樹！

以上就是二叉樹的一些基本操作了，有了二叉樹的基礎(chǔ)，我們后面學(xué)習(xí)優(yōu)先級隊(duì)列或者二叉搜索樹會更輕松，初學(xué)者剛接觸二叉樹可能有點(diǎn)難，但不用擔(dān)心，慢慢來就好，多畫圖。

以上就是Java 數(shù)據(jù)結(jié)構(gòu)之樹和二叉樹的相關(guān)資料的詳細(xì)內(nèi)容，更多關(guān)于Java 樹和二叉樹的資料請關(guān)注腳本之家其它相關(guān)文章！,希望大家以后多多支持腳本之家！

最新評論