算法【一】树
關(guā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)擁有的子樹數(shù)目稱為結(jié)點(diǎn)的度。
?
節(jié)點(diǎn)關(guān)系?
結(jié)點(diǎn)子樹的根結(jié)點(diǎn)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。相應(yīng)該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。
圖2.2中，A為B的雙親結(jié)點(diǎn)，B為A的孩子結(jié)點(diǎn)。
同一個(gè)雙親結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱兄弟結(jié)點(diǎn)。
圖2.2中，結(jié)點(diǎn)B與結(jié)點(diǎn)C互為兄弟結(jié)點(diǎn)。
后面接的全是空的，我們叫它們?nèi)~子結(jié)點(diǎn)如：G、H、I
節(jié)點(diǎn)的層次：
從根開始定義起，根為第一層，根的孩子為第二層，以此類推。
樹中結(jié)點(diǎn)的最大層次數(shù)稱為樹的深度或高度。圖2.1所示樹的深度為4。
??二叉樹
由二叉樹定義以及圖示分析得出二叉樹有以下特點(diǎn)：
1）每個(gè)結(jié)點(diǎn)最多有兩顆子樹，所以二叉樹中不存在度大于2的結(jié)點(diǎn)。
2）左子樹和右子樹是有順序的，次序不能任意顛倒。
3）即使樹中某結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。
簡單來說就是：最多只有兩個(gè)字樹的樹就叫二叉樹
在日常編程中，二叉樹有一些性質(zhì)我們可能可以用到，比如
1）在二叉樹的第i層上最多有2i-1次方 個(gè)節(jié)點(diǎn) 。（i>=1）
2）二叉樹中如果深度為k,那么最多有2k次方-1個(gè)節(jié)點(diǎn)。(k>=1）
3）n0=n2+1 n0表示度數(shù)為0的節(jié)點(diǎn)數(shù)，n2表示度數(shù)為2的節(jié)點(diǎn)數(shù)。
4）在完全二叉樹中，具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1，其中[log2n]是向下取整。
5）若對含 n 個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行 1 至 n 的編號，則對完全二叉樹中任意一個(gè)編號為 i 的結(jié)點(diǎn)有如下特性：
(1) 若 i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親, 否則，編號為 [i/2] 的結(jié)點(diǎn)為其雙親結(jié)點(diǎn);
(2) 若 2i>n，則該結(jié)點(diǎn)無左孩子， 否則，編號為 2i 的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；
(3) 若 2i+1>n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)， 否則，編號為2i+1 的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。
對于第五點(diǎn)我們來詳細(xì)講下并給出一些實(shí)例，因?yàn)檫@個(gè)筆試題中經(jīng)常用到：?
用數(shù)組順序存儲(chǔ)二叉樹, 其顯著特征是: (n表示數(shù)組的索引值)?
- 在數(shù)組中index=n的元素對應(yīng)的父節(jié)點(diǎn)為 index=(n-1)/2的元素, 向下取整;
- 在數(shù)組中index=n的元素對應(yīng)的左子節(jié)點(diǎn)為 index=2*n+1的元素;
- 在數(shù)組中index=n的元素對應(yīng)的右子節(jié)點(diǎn)為 index=2*n+2的元素;
如果此時(shí)給我們一個(gè)順序存儲(chǔ)的數(shù)組，叫我們構(gòu)建一顆二叉樹
給定二叉樹?[3,9,20,null,null,15,7]，
Definition for a binary tree node.public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }} public static TreeNode createBT(int[] arr, int i) // 初始時(shí),傳入的i==0 {TreeNode root = null; // 定義根節(jié)點(diǎn)if (i >= arr.length) // i >= arr.length 時(shí),表示已經(jīng)到達(dá)了根節(jié)點(diǎn)return null;root = new TreeNode(arr[i]); // 根節(jié)點(diǎn)root.left = createBT(arr, 2*i+1); // 遞歸建立左孩子結(jié)點(diǎn)root.right = createBT(arr, 2*i+2); // 遞歸建立右孩子結(jié)點(diǎn)return root; }public class Main {public static void main(String[] args) {int[] arr = {3,9,20,null,null,15,7};TreeNode root = createBT(arr, 0);System.out.println("先序遍歷：");PreOrder(root);System.out.println("\n中序遍歷：");InOrder(root);System.out.println("\n后序遍歷：");PostOrder(root);} // 這里只寫preOrder，中序和后序自己寫下public static void preOrder(TreeNode root){if (root==null){return;}System.out.println(root.val);preOrder(root.left) ;preOrder(root.right);}至于二叉樹的遍歷比較簡單：遞歸就完事兒
// 先序遍歷public static void PreOrder(TreeNode root){if (root == null)return;System.out.print(root.val+" ");PreOrder(root.left);PreOrder(root.right);} // 中序遍歷public static void InOrder(TreeNode root){if (root == null)return;InOrder(root.left);System.out.print(root.val+" ");InOrder(root.right);} // 后序遍歷public static void PostOrder(TreeNode root){if (root == null)return;PostOrder(root.left);PostOrder(root.right);System.out.print(root.val+" ");}接下來我們來介紹一下二叉樹的種類：
1、滿二叉樹
所有葉結(jié)點(diǎn)同處于最底層（非底層結(jié)點(diǎn)均是內(nèi)部結(jié)點(diǎn)），一個(gè)深度為k(>=-1)且有2^(k+1) - 1個(gè)結(jié)點(diǎn)。如圖（圖來源于veil的博客）：
2、完全二叉樹
葉結(jié)點(diǎn)只能出現(xiàn)在最底層的兩層，且最底層葉結(jié)點(diǎn)均處于次底層葉結(jié)點(diǎn)的左側(cè)。設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊。
?一個(gè)完全二叉樹的初始化和遍歷：
我們來一道力扣題目：
完全二叉樹是每一層（除最后一層外）都是完全填充（即，節(jié)點(diǎn)數(shù)達(dá)到最大）的，并且所有的節(jié)點(diǎn)都盡可能地集中在左側(cè)。
設(shè)計(jì)一個(gè)用完全二叉樹初始化的數(shù)據(jù)結(jié)構(gòu)?CBTInserter，它支持以下幾種操作：
CBTInserter(TreeNode root)?使用頭節(jié)點(diǎn)為?root?的給定樹初始化該數(shù)據(jù)結(jié)構(gòu)；
CBTInserter.insert(int v)??向樹中插入一個(gè)新節(jié)點(diǎn)，節(jié)點(diǎn)類型為 TreeNode，值為 v 。使樹保持完全二叉樹的狀態(tài)，并返回插入的新節(jié)點(diǎn)的父節(jié)點(diǎn)的值；
CBTInserter.get_root() 將返回樹的頭節(jié)點(diǎn)。
?
示例 1：
輸入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
輸出：[null,1,[1,2]]
初始化一個(gè)完全二叉樹，然后做一個(gè)前序遍歷的代碼
public class CBTInserter {private static TreeNode root;//輸入就是一棵樹public CBTInserter(TreeNode root) {this.root = root;}public int insert(int val) {TreeNode newNode = new TreeNode(val);// 我最開始這么寫的，給的一個(gè)測試用例也通過了，但是想想有什么問題Deque<TreeNode> stack =new LinkedList<>();if (root==null){root = newNode;}stack.push(root);TreeNode node=null;while (stack!=null && stack.size()>0){node= stack.pop();if (node.left==null){node.left =newNode;}else if (node.right==null){node.right = newNode;}else if (node.left!=null){stack.push(node.left);}else if (node.right !=null){stack.push(node.right);}}return node.val;}public TreeNode get_root() {return root;}public static void main(String[] args) {int[] arr = {1,2,3,4,5,6}; //這就是不通過的，實(shí)際上我并沒有找到最小的TreeNode root =CreateTree.createBT(arr, 0);//這個(gè)前面有CBTInserter obj = new CBTInserter(root);obj.insert(7);obj.insert(8);obj.get_root();} }思路：回想一下我們的目的
將所有節(jié)點(diǎn)編號，按照從上到下從左到右的順序。
實(shí)際上我們希望，在每個(gè)插入步驟中，我們希望插入到一個(gè)編號最小的節(jié)點(diǎn)（并且它的字樹有空閑，那邊沒有我就插哪里）。
那么我們可以利用二叉樹的性質(zhì)，想到?jīng)]？我們只要找到我要新插入節(jié)點(diǎn)的父節(jié)點(diǎn)實(shí)際上就解決問題了 我們很容易得到父節(jié)點(diǎn)在數(shù)組中的下標(biāo)是這個(gè)n/2 -1，不會(huì)的自己手畫一下就推出來了
// 實(shí)際上你用一個(gè) int[]即可 class CBTInserter {private List<TreeNode> array = new LinkedList<>();public CBTInserter(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()){TreeNode treeNode = queue.remove();if (treeNode.left != null) {queue.add(treeNode.left);}if (treeNode.right != null) {queue.add(treeNode.right);}array.add(treeNode);}}public int insert(int v) {TreeNode node = new TreeNode(v);array.add(node);TreeNode p = array.get(array.size() / 2-1);if (p.left == null) {p.left = node;}else {p.right = node;}return p.val;}public TreeNode get_root() {return array.get(0);}}?實(shí)際上按照剛剛的思路其實(shí)也能做出來
讓我們來改造下：
// 就是力扣的官方答案了。 bfs將最編號并且子樹有一個(gè)部位null的取到 class CBTInserter {TreeNode root;Deque<TreeNode> deque;public CBTInserter(TreeNode root) {this.root = root;deque = new LinkedList();Queue<TreeNode> queue = new LinkedList();queue.offer(root);// BFS to populate dequewhile (!queue.isEmpty()) {TreeNode node = queue.poll();if (node.left == null || node.right == null)deque.offerLast(node);if (node.left != null)queue.offer(node.left);if (node.right != null)queue.offer(node.right);}}public int insert(int v) {TreeNode node = deque.peekFirst();deque.offerLast(new TreeNode(v));if (node.left == null)node.left = deque.peekLast();else {node.right = deque.peekLast();deque.pollFirst();}return node.val;}public TreeNode get_root() {return root;} }作者：LeetCode 鏈接：https://leetcode-cn.com/problems/complete-binary-tree-inserter/solution/wan-quan-er-cha-shu-cha-ru-qi-by-leetcode/ 來源：力扣（LeetCode） 著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。3、平衡二叉樹
?平衡二叉樹（Self-balancing binary search tree）又被稱為AVL樹（有別于AVL算法），且具有以下性質(zhì)：它是一 棵空樹或它的左右兩個(gè)子樹的高度差的絕對值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。平衡二叉樹的常用實(shí)現(xiàn)方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等。 最小二叉平衡樹的節(jié)點(diǎn)的公式如下 F(n)=F(n-1)+F(n-2)+1 這個(gè)類似于一個(gè)遞歸的數(shù)列，可以參考Fibonacci(斐波那契)數(shù)列，1是根節(jié)點(diǎn)，F(n-1)是左子樹的節(jié)點(diǎn)數(shù)量，F(n-2)是右子樹的節(jié)點(diǎn)數(shù)量。（百度百科）
關(guān)于平衡二叉樹可以查看這個(gè)博客：平衡二叉樹詳解 - zhangbaochong - 博客園
主要是清楚平衡二叉樹的幾種情況
1.對α的左兒子的左子樹進(jìn)行一次插入
2.對α的左兒子的右子樹進(jìn)行一次插入
3.對α的右兒子的左子樹進(jìn)行一次插入
4.對α的右兒子的右子樹進(jìn)行一次插入
情形1和情形4是關(guān)于α的鏡像對稱，二情形2和情形3也是關(guān)于α的鏡像對稱，因此理論上看只有兩種情況，但編程的角度看還是四種情形。
第一種情況是插入發(fā)生在“外邊”的情形（左左或右右），該情況可以通過一次單旋轉(zhuǎn)完成調(diào)整；第二種情況是插入發(fā)生在“內(nèi)部”的情形（左右或右左），這種情況比較復(fù)雜，需要通過雙旋轉(zhuǎn)來調(diào)。
那么旋轉(zhuǎn)究竟是做個(gè)什么事情？？針對四種情況的旋轉(zhuǎn)算法都不同。下面是針對左左情況的單旋轉(zhuǎn)算法的步驟
如果給你一個(gè)順序數(shù)組，如何來構(gòu)建成一棵樹呢？
來實(shí)戰(zhàn)一下
從上到下打印二叉樹
從上到下打印出二叉樹的每個(gè)節(jié)點(diǎn)，同一層的節(jié)點(diǎn)按照從左到右的順序打印。
如:
給定二叉樹:?[3,9,20,null,null,15,7],
? ? 3
? ?/ \
? 9 ?20
? ? / ?\
? ?15 ? 7
返回：
[3,9,20,15,7]
分析一下，從上到下，即代表從根節(jié)點(diǎn)開始。從左到右，那就是從左子樹到右子樹。想到了什么？
樹的前序遍歷對不對？所謂的前序、中序、后序不過是訪問根節(jié)點(diǎn)的順序。那么思路很簡單了，
樹的變種
字典樹（前綴樹題目）
前綴樹的定義：
又稱單詞查找樹，字典樹，Trie樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來減少查詢時(shí)間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。
前綴樹的性質(zhì)：
1）根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符
2）從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對應(yīng)的字符串
3）每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同
注：每個(gè)節(jié)點(diǎn)都含有26個(gè)鏈接表示出現(xiàn)的26個(gè)小寫字母，即每個(gè)節(jié)點(diǎn)表示的字符是26個(gè)字符中的一個(gè)，當(dāng)字符串插入完成時(shí)，我們就會(huì)標(biāo)記該字符串就是完整的字符串了。
?
添加與搜索單詞 - 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)
請你設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持 添加新單詞 和 查找字符串是否與任何先前添加的字符串匹配 。
實(shí)現(xiàn)詞典類 WordDictionary ：
WordDictionary() 初始化詞典對象
void addWord(word) 將 word 添加到數(shù)據(jù)結(jié)構(gòu)中，之后可以對它進(jìn)行匹配
bool search(word) 如果數(shù)據(jù)結(jié)構(gòu)中存在字符串與?word 匹配，則返回 true ；否則，返回??false 。word 中可能包含一些 '.' ，每個(gè)?. 都可以表示任何一個(gè)字母。
?
示例：
輸入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
輸出：
[null,null,null,null,false,true,true,true]
解釋：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
?
提示：
1 <= word.length <= 500
addWord 中的 word 由小寫英文字母組成
search 中的 word 由 '.' 或小寫英文字母組成
最多調(diào)用 50000 次 addWord 和 search
思路分析：
非常明顯的一道前綴樹的問題，我們只需要構(gòu)造一棵前綴樹，然后每個(gè)一次去遍歷這棵樹就行了 怎么實(shí)現(xiàn)呢？ 第一：需要有一個(gè)根節(jié)點(diǎn)；每次從根節(jié)點(diǎn)開始遍歷取出單詞的每一個(gè)單詞，從根開始遍歷，單詞的word，是否是這個(gè)單詞的結(jié)束 那么我們需要先構(gòu)造一個(gè)樹的節(jié)點(diǎn)的這樣的數(shù)據(jù)結(jié)構(gòu)：包含了下一個(gè)節(jié)點(diǎn)和單詞是都結(jié)束的標(biāo)識(shí)好了直接上代碼了：
public class WordDictionary {/** Initialize your data structure here. */public class ThreeNode {Map<Character,ThreeNode> childdren;Boolean wordEnd;public ThreeNode(){childdren = new HashMap<Character, ThreeNode>();wordEnd = false;}}private ThreeNode root;public WordDictionary() {root = new ThreeNode();root.wordEnd = false;}public void addWord(String word) {ThreeNode temp = root;// 取到根節(jié)點(diǎn)if (!word.isEmpty()){for (int i = 0; i < word.length(); i++) {if (!temp.childdren.containsKey( word.charAt(i)))temp.childdren.put(word.charAt(i),new ThreeNode());temp = temp.childdren.get(word.charAt(i));//這一步很重要，表示繼續(xù)從下一個(gè)節(jié)點(diǎn)開始遍歷}//遍歷完將這個(gè)節(jié)點(diǎn)單詞置為結(jié)束temp.wordEnd =true;}}public boolean search(String word) {ThreeNode temp = root;// 取到根節(jié)點(diǎn)boolean isFound =true;if (!word.isEmpty()){for (int i = 0; i < word.length(); i++) {//注意到題目中有個(gè)要求就是點(diǎn)號可以代替任何字母if (!temp.childdren.containsKey( word.charAt(i)) && !(word.charAt(i) =='.'))//搜索和插入很類似// temp.childdren.put(word.charAt(i),new ThreeNode());return false;temp = temp.childdren.get(word.charAt(i));//這一步很重要，表示繼續(xù)從下一個(gè)節(jié)點(diǎn)開始遍歷}}//解釋一下 題目是說的輸入的字符串完全匹配。所以必須要跟上字符串是否結(jié)束。如果是包含則直接返回了return isFound && temp.wordEnd;} }總結(jié)
- 上一篇： Maven之依赖管理
- 下一篇： RStudio（You‘re using