什么是樹？

簡單認識樹 

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

這里我們要注意幾點：

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

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

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

樹的概念 

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

節(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)?！?/p>

孩子節(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) 顆互不相交的樹組成的集合叫做森林，一棵樹也可以叫做森林。

樹的表示形式

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

孩子兄弟表示法：

二叉樹

二叉樹的概念

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

注意：

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

特殊的二叉樹

這里有個問題，前面學習的 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)系，我們直接看圖：

二叉樹的性質(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é)點下標為 i，左孩子節(jié)點下標為：2 * i + 1 且 < n，右孩子下標為：2 * i + 2 且 < n，已知孩子節(jié)點下標，求父節(jié)點：(i - 1) / 2 = 父節(jié)點下標，若 i = 0，則 i 為根節(jié)點編號。 

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

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等于多少？當k等于9時，2^9 = 512，即k=9當前完全二叉樹最大節(jié)點數(shù)為512小于531，不滿足題意，當k等于10時，2^10 = 1024，滿足題意，所以本題選 B！

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

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

二叉樹的存儲結(jié)構(gòu)分為順序存儲和鏈式存儲，順序存儲后續(xù)講解優(yōu)先級隊列會講，鏈式存儲跟前面的鏈表還是有一定區(qū)別的。

二叉樹的鏈式存儲也是由一個個節(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; //當前節(jié)點的根節(jié)點的引用
}

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

由于目前的學習深度不夠，為了降低成本，我們需要先學習簡單的二叉樹的操作， 熟練掌握這些操作之后，下期我們在講解二叉樹的練習題時會講到如何構(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)造出如上圖一樣的一顆二叉樹了，下面我們將學習二叉樹的一些相關(guān)操作，測試樣例都是在上圖的基礎(chǔ)上進行測試。

二叉樹的前序遍歷

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

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

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

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

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

二叉樹的中序

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

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

代碼實現(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)多畫圖！

獲取二叉樹節(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，這個代碼采用的是子問題思想，如果還不熟悉遞歸，一定要下去畫遞歸展開圖，就像博主畫上面前序遍歷那樣。

獲取二叉樹葉子節(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é)點的左子樹為空，右子樹也為空，如果采用子問題思路，可以寫出如上的代碼。 如果不理解這個遞歸，一定要畫遞歸展開圖哦，多畫幾次就理解了！

獲取第k層的節(jié)點個數(shù)

這個方法其實很簡單，前面我們會求節(jié)點個數(shù)，那么第 k 層的節(jié)點個數(shù)，是不是就是第 k-1 層的子節(jié)點個數(shù)呢？所以當我們遞歸到第 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);
}

獲取二叉樹的高度

二叉樹的高度，如果用子問題方法來解決的話，那是不是以任意一個根節(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;
}

檢測值為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;
}

層序遍歷

解決這個方法我們來換一種思路，采用非遞歸的方式，思路是這樣的，定義一個隊列，先把根節(jié)點入隊，如果隊列不為空，將隊頭的元素出隊放入臨時變量中，接著入隊臨時變量不為空的左右子節(jié)點，左右節(jié)點為 null 則不入隊，上述循環(huán)，當隊列為空，層序遍歷結(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); 
        } 
    }
}

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

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

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

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

最新評論