目錄

一、樹(shù)型結(jié)構(gòu)

二、二叉樹(shù)

2.1 概念

2.2?特殊的二叉樹(shù)

?2.3?二叉樹(shù)的性質(zhì)

2.4 二叉樹(shù)的存儲(chǔ)

2.5 遍歷二叉樹(shù)

2.6 操作二叉樹(shù)

總結(jié)

---

一、樹(shù)型結(jié)構(gòu)

樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由 n(n>=0) 個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合，一棵 n 個(gè)結(jié)點(diǎn)的樹(shù)有 n-1 條邊。

• 結(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)具有的子樹(shù)個(gè)數(shù)稱為該結(jié)點(diǎn)的度。如上圖，結(jié)點(diǎn) A 的度為 6。
• 樹(shù)的度：一棵樹(shù)中，所有結(jié)點(diǎn)度的最大值稱為樹(shù)的度。如上圖，樹(shù)的度為 6。
• 葉子結(jié)點(diǎn) (終端結(jié)點(diǎn))：度為 0 的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。如上圖，B、C、H、I、N 等結(jié)點(diǎn)為葉子結(jié)點(diǎn)。
• 父結(jié)點(diǎn) (雙親結(jié)點(diǎn))：若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn)，則稱該結(jié)點(diǎn)為其子結(jié)點(diǎn)的父節(jié)點(diǎn)。如上圖，A 是 B 的父結(jié)點(diǎn)。
• 根結(jié)點(diǎn)：是每棵樹(shù)的起始結(jié)點(diǎn)，即沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)。如上圖，A 為根結(jié)點(diǎn)。
• 子結(jié)點(diǎn) (孩子結(jié)點(diǎn))：一個(gè)結(jié)點(diǎn)含有的子樹(shù)的根結(jié)點(diǎn)，稱為該結(jié)點(diǎn)的子節(jié)點(diǎn)。如上圖，B 是 A 的子結(jié)點(diǎn)。
• 結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開(kāi)始，根結(jié)點(diǎn)為第 1 層，根結(jié)點(diǎn)的子結(jié)點(diǎn)為第 2 層，以此類推。如上圖，結(jié)點(diǎn) A 為第 1 層，結(jié)點(diǎn) B、C、D 等為第 2 層。
• 樹(shù)的高度 (深度)：樹(shù)中結(jié)點(diǎn)的最大層次。如上圖，樹(shù)的高度為 4。
• 分支結(jié)點(diǎn)：度不為 0 的結(jié)點(diǎn)。
• 兄弟結(jié)點(diǎn)：具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互為兄弟。
• 堂兄弟結(jié)點(diǎn)：父結(jié)點(diǎn)在同一層的結(jié)點(diǎn)互為堂兄弟。
• 結(jié)點(diǎn)的祖先：從根結(jié)點(diǎn)到該結(jié)點(diǎn)分支上的所有結(jié)點(diǎn)。如上圖，A 是所有結(jié)點(diǎn)的祖先。
• 子孫：以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。如上圖，所有結(jié)點(diǎn)都是 A 的子孫。
• 森林：由 m(m>=0) 棵互不相交的樹(shù)組成的集合稱為森林。

---

二、二叉樹(shù)

2.1 概念

一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，二叉樹(shù)有兩種情況：

① 空樹(shù)；

② 由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

【特點(diǎn)】

1、二叉樹(shù)不存在度大于 2 的結(jié)點(diǎn)；

2、二叉樹(shù)的子樹(shù)有左右之分，次序不能顛倒，因此二叉樹(shù)是有序樹(shù)。

---

2.2?特殊的二叉樹(shù)

1、滿二叉樹(shù)：若一棵二叉樹(shù)每層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這棵樹(shù)就是滿二叉樹(shù)。即若一棵二叉樹(shù)的高度為 k，且結(jié)點(diǎn)總數(shù)是?，則它就是滿二叉樹(shù)。

2、完全二叉樹(shù)：滿二叉樹(shù)是一種特殊的完全二叉樹(shù)。對(duì)于高度為 K，有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)都與高度為 k?的滿二叉樹(shù)中編號(hào)從 0 至 n-1 的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱為完全二叉樹(shù)。

---

?2.3?二叉樹(shù)的性質(zhì)

• 一棵非空二叉樹(shù)的第 k?層上最多有??個(gè)結(jié)點(diǎn)；
• 高度為 k 的二叉樹(shù)最大結(jié)點(diǎn)數(shù)為?；
• 葉子結(jié)點(diǎn)個(gè)數(shù)為?，度為 2 的結(jié)點(diǎn)個(gè)數(shù)為?，則有?；
• 有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)高度為?；("[]"為取整)
• 一棵有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，對(duì)于其編號(hào)為 i 的結(jié)點(diǎn)有：

• 若 i > 0，父結(jié)點(diǎn)編號(hào)：[(i-1) / 2]；若 i = 0，則 i 為根結(jié)點(diǎn)編號(hào)，無(wú)父結(jié)點(diǎn)。
• 若 2i+1 <?n，左孩子編號(hào)：2i+1；反之無(wú)左孩子。
• 若 2i+2?<?n，右孩子編號(hào)：2i+2；反之無(wú)右孩子。

---

2.4 二叉樹(shù)的存儲(chǔ)

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)是通過(guò)一個(gè)一個(gè)結(jié)點(diǎn)引用構(gòu)造出的，例如，孩子表示法和孩子雙親表示法：

    //孩子表示法class Node {int val; //數(shù)據(jù)域Node left; //左孩子Node right; //右孩子}//孩子雙親表示法class Node {int val; //數(shù)據(jù)域Node left; //左孩子Node right; //右孩子Node parent; //當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)}

---

2.5 遍歷二叉樹(shù)

【前中后序遍歷】

前序(NLR)：根結(jié)點(diǎn) → 左子樹(shù)?→ 右子樹(shù)；(根左右)

中序(LNR)：左子樹(shù)?→ 根結(jié)點(diǎn) → 右子樹(shù)；(左根右)

后序(LRN)：左子樹(shù)?→ 右子樹(shù) → 根結(jié)點(diǎn)；(左右根)

前序：ABDEGCF

中序：DBGEAFC

后序：DGEBFCA

public class BinaryTree {//孩子表示法static class TreeNode {public String val; //數(shù)據(jù)域public TreeNode left; //左孩子public TreeNode right; //右孩子public TreeNode(String val) {this.val = val;}}//構(gòu)建樹(shù)，返回根結(jié)點(diǎn)public TreeNode createTree() {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");TreeNode G = new TreeNode("G");A.left = B;A.right = C;B.left = D;B.right = E;E.left = G;C.left = F;return A;}//前序遍歷public void preOrder(TreeNode root) {//若為空樹(shù)，返回if (root == null) {return;}System.out.print(root.val + " "); //根preOrder(root.left); //左preOrder(root.right); //右}//中序遍歷public void inOrder(TreeNode root) {//若為空樹(shù)，返回if (root == null) {return;}inOrder(root.left);//左System.out.print(root.val + " ");//根inOrder(root.right);//右}//后序遍歷public void postOrder(TreeNode root) {//若為空樹(shù)，返回if (root == null) {return;}postOrder(root.left);//左postOrder(root.right);//右System.out.print(root.val + " ");//根}
}public class Main {public static void main(String[] args) {//創(chuàng)建二叉樹(shù)對(duì)象BinaryTree binaryTree = new BinaryTree();//構(gòu)建二叉樹(shù)BinaryTree.TreeNode root = binaryTree.createTree();binaryTree.preOrder(root);//前序：A B D E G C F System.out.println();binaryTree.inOrder(root);//中序：D B G E A F CSystem.out.println();binaryTree.postOrder(root);//后序：D G E B F C A }
}

【層序遍歷】?

層序遍歷：即自上而下、從左至右逐層訪問(wèn)樹(shù)的結(jié)點(diǎn)的遍歷過(guò)程。

---

2.6 操作二叉樹(shù)

采用子問(wèn)題思路來(lái)實(shí)現(xiàn)二叉樹(shù)的操作。

1、獲取樹(shù)中結(jié)點(diǎn)個(gè)數(shù)

    //獲取樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)public int size(TreeNode root) {//若為空樹(shù)，返回if (root == null) {return 0;}//返回根結(jié)點(diǎn)的左子樹(shù) + 根結(jié)點(diǎn)的右子樹(shù) + 根結(jié)點(diǎn)本身return size(root.left) + size(root.right) + 1;}

2、獲取樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)

    //獲取葉子結(jié)點(diǎn)的個(gè)數(shù)public int getLeafNodeCount(TreeNode root) {//若為空樹(shù)，返回if (root == null) {return 0;}//若無(wú)左子樹(shù)與右子樹(shù)，便是葉子結(jié)點(diǎn)if (root.left == null && root.right == null) {//是葉子結(jié)點(diǎn)，返回 1return 1;}//返回根結(jié)點(diǎn)的左子樹(shù)、右子樹(shù)中的葉子結(jié)點(diǎn)return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);}

?3、獲取第 K 層結(jié)點(diǎn)個(gè)數(shù)

    //獲取第 K 層結(jié)點(diǎn)的個(gè)數(shù)public int getKLevelNodeCount(TreeNode root, int k) {//若為空樹(shù)，返回if (root == null) {return 0;}//第 K 層是第 1 層根結(jié)點(diǎn)的第 K-1 層，//也是第 2 層結(jié)點(diǎn)的第 K-2 層。//即第 K 層結(jié)點(diǎn)的第 1 層，if (k == 1) {return 1;}//返回根結(jié)點(diǎn)的左子樹(shù)、右子樹(shù)的第 K 層結(jié)點(diǎn)return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1);}

?4、獲取二叉樹(shù)的高度

    //獲取二叉樹(shù)的高度public int getHeight(TreeNode root) {//若為空樹(shù)，返回if (root == null) {return 0;}//左子樹(shù)高度int leftHeight = getHeight(root.left);//右子樹(shù)高度int rightHeight = getHeight(root.right);//根結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)對(duì)比，//誰(shuí)高返回誰(shuí) + 根結(jié)點(diǎn)本身，即左(右)子樹(shù)高度 + 1。return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;}

5、檢測(cè)值為 val 的元素是否存在

    //檢測(cè)值為 val 的元素是否存在public TreeNode find(TreeNode root, String val) {//若為空樹(shù)，返回if (root == null) {return null;}//判斷根結(jié)點(diǎn)元素if (root.val == val) {return root;}//判斷根結(jié)點(diǎn)的左子樹(shù)TreeNode left = find(root.left, val);if (left != null) {return left;}//判斷根結(jié)點(diǎn)的右子樹(shù)TreeNode right = find(root.right, val);if (right != null) {return right;}return null;}

---

總結(jié)

1、一棵 n 個(gè)結(jié)點(diǎn)的樹(shù)有 n-1 條邊。

2、二叉樹(shù)不存在度大于 2 的結(jié)點(diǎn)。

3、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

4、前序（根左右）；中序（左根右）；后序（左右根）。

5、層序遍歷：自上而下、從左至右逐層訪問(wèn)樹(shù)的結(jié)點(diǎn)的遍歷過(guò)程。