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