柚子快報(bào)激活碼778899分享：java 【數(shù)據(jù)結(jié)構(gòu)】二叉樹
柚子快報(bào)激活碼778899分享：java 【數(shù)據(jù)結(jié)構(gòu)】二叉樹
目錄
二叉樹特殊二叉樹二叉樹的性質(zhì)二叉樹的模擬實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)接口實(shí)現(xiàn)內(nèi)部類遍歷前序遍歷中序遍歷后序遍歷遍歷確定二叉樹層序遍歷
獲取節(jié)點(diǎn)個(gè)數(shù)獲取葉子節(jié)點(diǎn)的個(gè)數(shù)獲取第K層節(jié)點(diǎn)的個(gè)數(shù)獲取二叉樹的高度檢測值為value的元素是否存在判斷一棵樹是不是完全二叉樹
練習(xí)鏈接
二叉樹
二叉樹（Binary Tree）是n（n >= 0 ）個(gè)節(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個(gè)根節(jié)點(diǎn)和兩顆互不相交的、分別稱為根節(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。 
特殊二叉樹
有以下三種特殊二叉樹：
1.斜樹：所有的節(jié)點(diǎn)都只有左子樹的二叉樹叫斜樹。所有的節(jié)點(diǎn)只有右子樹 的二叉樹叫右斜樹。兩者統(tǒng)稱為斜樹。 2.滿二叉樹：在一棵二叉樹中，如果所有分支節(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子節(jié)點(diǎn)都在同一層上，這樣的二叉樹稱為滿二叉樹。 3.完全二叉樹：對(duì)一棵具有n個(gè)節(jié)點(diǎn)的二叉樹按照層序編號(hào)，如果編號(hào)為i（1 <= i <= n）的節(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)節(jié)點(diǎn)為i的節(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹為完全二叉樹。
二叉樹的性質(zhì)
二叉樹的5個(gè)性質(zhì)：
規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i - 1) (i>0)個(gè)結(jié)點(diǎn)。規(guī)定只有根結(jié)點(diǎn)的二叉樹的深度為1，則深度為K的二叉樹的最大結(jié)點(diǎn)數(shù)是 2^k - 1 (k>=0)。對(duì)任何一棵二叉樹, 如果其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的非葉結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0＝n2＋1。具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為log(N+1)以2為底向上取整。對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的順序?qū)λ泄?jié)點(diǎn)從0開始編號(hào)，則對(duì)于序號(hào)為i的結(jié)點(diǎn)有： 若i>0，雙親序號(hào)：(i-1)/2；i=0，i為根結(jié)點(diǎn)編號(hào)，無雙親結(jié)點(diǎn)； 若2i+1 二叉樹的模擬實(shí)現(xiàn) 我們用代碼模擬實(shí)現(xiàn)一個(gè)二叉樹。 存儲(chǔ)結(jié)構(gòu) 在講解樹的時(shí)候就講解了樹有兩種存儲(chǔ)方式，順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。 二叉樹的順序存儲(chǔ)在下一文講解堆在介紹。 本文主要講解鏈?zhǔn)酱鎯?chǔ)，使用孩子表示法。 接口實(shí)現(xiàn) 實(shí)現(xiàn)的接口（成員方法）如下： public class BinaryTree { // 前序遍歷 public void preOrder(TreeNode root) {} // 中序遍歷 void inOrder(TreeNode root) {} // 后序遍歷 void postOrder(TreeNode root) {} // 獲取節(jié)點(diǎn)的個(gè)數(shù)：子問題的思路 int size2(TreeNode root) {} //獲取葉子節(jié)點(diǎn)的個(gè)數(shù)：子問題 int getLeafNodeCount2(TreeNode root) {} //獲取第K層節(jié)點(diǎn)的個(gè)數(shù) int getKLevelNodeCount(TreeNode root, int k) {} //獲取二叉樹的高度 時(shí)間復(fù)雜度：O(N) int getHeight(TreeNode root) {} // 檢測值為value的元素是否存在 TreeNode find(TreeNode root, char val) {} //層序遍歷 void levelOrder(TreeNode root) {} // 判斷一棵樹是不是完全二叉樹 boolean isCompleteTree(TreeNode root) {} } 內(nèi)部類 我們使用孩子表示法來存儲(chǔ)二叉樹，那么在節(jié)點(diǎn)內(nèi)部類中就要包含左孩子和右孩子的引用。 static class TreeNode { public char val; public TreeNode left;//左孩子的引用 public TreeNode right;//右孩子的引用 public TreeNode(char val) { this.val = val; } } 遍歷 二叉樹的遍歷（traversing binary tree）是指從根節(jié)點(diǎn)出發(fā)，按照某種次序依次訪問二叉樹的所有節(jié)點(diǎn)，使得每個(gè)節(jié)點(diǎn)被訪問一次且僅被訪問一次。 前序遍歷 前序遍歷的規(guī)則就是：若二叉樹為空，則空操作返回，否則先訪問根節(jié)點(diǎn)，然后前序遍歷左子樹，再前序遍歷右子樹。 以打印為例：通俗講就是遇根節(jié)點(diǎn)就打印，然后走左子樹，再進(jìn)右子樹。 // 前序遍歷 public void preOrder(TreeNode root) { if (root == null) return; System.out.print(root.val + " "); preOrder(root.left); preOrder(root.right); } 中序遍歷 中序遍歷的規(guī)則就是：若二叉樹為空，則空操作返回，否則從根節(jié)點(diǎn)開始（注意不是先訪問根節(jié)點(diǎn)），中序遍歷根節(jié)點(diǎn)的左子樹，再前序遍歷右子樹。 以打印為例：通俗講就是先進(jìn)左子樹，遇根節(jié)點(diǎn)如果該根節(jié)點(diǎn)的左子樹已經(jīng)打印完了就打印該根節(jié)點(diǎn)，再進(jìn)右子樹。 // 中序遍歷 void inOrder(TreeNode root) { if (root == null) return; inOrder(root.left); System.out.print(root.val + " "); inOrder(root.right); } 后序遍歷 后序遍歷的規(guī)則就是：若二叉樹為空，則空操作返回，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問左右節(jié)點(diǎn)。 以打印為例：通俗講就是先進(jìn)左子樹，再進(jìn)右子樹，遇根節(jié)點(diǎn)如果該根節(jié)點(diǎn)的左子樹和右子樹都已經(jīng)打印完了就打印該根節(jié)點(diǎn)。 // 后序遍歷 void postOrder(TreeNode root) { if (root == null) return; postOrder(root.left); postOrder(root.right); System.out.print(root.val + " "); } 遍歷確定二叉樹 根據(jù)前中后遍歷的特點(diǎn)： 前序遍歷從前向后的節(jié)點(diǎn)是每顆樹根節(jié)點(diǎn)。中序遍歷的特點(diǎn)就是每個(gè)節(jié)點(diǎn)的左邊是左子樹的節(jié)點(diǎn)，右邊是右子樹的節(jié)點(diǎn)。后序遍歷是從后向前的節(jié)點(diǎn)是每棵樹根節(jié)點(diǎn)。 我們只要中序遍歷加任一遍歷就可以確定當(dāng)前二叉樹。 以前序遍歷和中序遍歷為例： 根據(jù)前序遍歷依次往后拿到節(jié)點(diǎn)，第一個(gè)節(jié)點(diǎn)是整棵樹的根節(jié)點(diǎn)，往后拿到的節(jié)點(diǎn)根據(jù)中序遍歷結(jié)果觀察是在已確定的二叉樹中確定該節(jié)點(diǎn)的父親節(jié)點(diǎn)，然后左邊就是左孩子，右邊就是右孩子。 層序遍歷 層序遍歷的規(guī)則就是：若二叉樹為空，則空操作返回，否則從樹的第一層，也就是根節(jié)點(diǎn)開始訪問，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)?jié)點(diǎn)逐個(gè)訪問。 代碼實(shí)現(xiàn)思路： 進(jìn)行層序遍歷時(shí)，我們要用到隊(duì)列（先進(jìn)先出）這個(gè)數(shù)據(jù)結(jié)構(gòu)， 將根結(jié)點(diǎn)先放進(jìn)隊(duì)列去。每次都記錄隊(duì)列的節(jié)點(diǎn)，如果該節(jié)點(diǎn)左右孩子不為空就入隊(duì)。直到隊(duì)列為空為止。 這樣我們?nèi)腙?duì)列是層序遍歷的順序，那出隊(duì)列也是這個(gè)順序了。 //層序遍歷 void levelOrder(TreeNode root) { if (root == null) return; Queue queue.offer(root); while (!queue.isEmpty()) { TreeNode cur = queue.poll(); System.out.print(cur.val + " "); if (cur.left != null) { queue.offer(cur.left); } if (cur.right != null) { queue.offer(cur.right); } } } 獲取節(jié)點(diǎn)個(gè)數(shù) 代碼思路： 如果樹為空，返回0。不為空，直接返回左子樹和右子樹的節(jié)點(diǎn)樹加上根。 int size2(TreeNode root) { if (root == null) return 0; return size2(root.left) + size2(root.right) + 1; } 獲取葉子節(jié)點(diǎn)的個(gè)數(shù) 代碼思路： 如果樹為空，返回0。不為空，如果節(jié)點(diǎn)左子樹和右子樹為空則返回1。最后返回根節(jié)點(diǎn)左子樹和右子樹的葉子結(jié)點(diǎn)之和。 int getLeafNodeCount2(TreeNode root) { if (root == null) return 0; if (root.left == null && root.right == null) { return 1; } return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right); } 獲取第K層節(jié)點(diǎn)的個(gè)數(shù) 代碼思路： 如果樹為空，返回0。不為空，如果層數(shù)為1并且該節(jié)點(diǎn)不為空則返回1。最后返回根節(jié)點(diǎn)左子樹和右子樹的第k-1層結(jié)點(diǎn)之和。 int getKLevelNodeCount(TreeNode root, int k) { if (root == null) return 0; if (k == 1) return 1; return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1); } 獲取二叉樹的高度 代碼思路： 如果樹為空，返回0。不為空，求根節(jié)點(diǎn)的左子樹的高度和根節(jié)點(diǎn)右子樹的高度。返回子樹高度的最大值然后加上根節(jié)點(diǎn)這一層。 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的元素是否存在 代碼思路： 4. 如果樹為空，返回空。 5. 不為空，看根節(jié)點(diǎn)是不是所求節(jié)點(diǎn)，是返回。 6. 不是就在左子樹查看，返回值不是空就返回。 7. 左子樹結(jié)果是空，查看右子樹，返回結(jié)果。 TreeNode find(TreeNode root, char val) { if (root == null) return null; if (root.val == val) return root; TreeNode ret = find(root.left, val); if (ret != null) { return ret; } ret = find(root.right, val); return ret; } 判斷一棵樹是不是完全二叉樹 我們需要使用隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)。 如果是完全二叉樹，那么層序遍歷結(jié)果下節(jié)點(diǎn)之間就不會(huì)有空值。 代碼思路： 如果根節(jié)點(diǎn)為空直接返回false。不為空將根放入隊(duì)列。取出隊(duì)列值，如果值不為空就將左孩子和右孩子入隊(duì)，為空直接出循環(huán)。因?yàn)榍懊媸悄玫疥?duì)列中的空節(jié)點(diǎn)出循環(huán)的，遍歷剩余節(jié)點(diǎn)如果遇到不為空的節(jié)點(diǎn)那該樹就不是完全二叉樹。 boolean isCompleteTree(TreeNode root) { if (root == null) return false; Queue queue.offer(root); while (!queue.isEmpty()) { TreeNode cur = queue.poll(); if (cur != null) { queue.offer(cur.left); queue.offer(cur.right); } else { break; } } //第2次遍歷隊(duì)列 判斷隊(duì)列當(dāng)中 是否存在非空的元素 while(!queue.isEmpty()) { TreeNode cur = queue.peek(); if (cur == null) { queue.poll(); } else { return false; } } return true; } } 練習(xí)鏈接 相同的樹 另一棵樹的子樹 翻轉(zhuǎn)二叉樹 平衡二叉樹 對(duì)稱二叉樹 二叉樹遍歷 二叉樹層序遍歷 二叉樹的公共祖先 從前序遍歷和中序遍歷構(gòu)建二叉樹 從中序遍歷和后序遍歷構(gòu)建二叉樹 根據(jù)二叉樹構(gòu)建字符串 二叉樹的前序遍歷 二叉樹的中序遍歷 二叉樹的后序遍歷 柚子快報(bào)激活碼778899分享：java 【數(shù)據(jù)結(jié)構(gòu)】二叉樹 相關(guān)文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Voghion國際時(shí)尚坊
