一、樹
1、深度為n的滿m叉數的第k層有 m^(k-1) 個結點（1≤k≤h）
決議：樹的根節點為1，滿M叉樹，第n層節點樹肯定是前一層節點的m倍
第1層： 1 m^0
第2層： 1*m m^1
第3層： 1*m*m m^2
. . . . . .
第k層： 1*m^(k-1) m^(k-1)
2、 二叉樹有一個性質：n0=n2+1 (n0是指度為0的節點，n2是指度為2的節點）
若二叉樹有67個結點，那么，要么度為0（m），要么度為2（n），則有 m+n = 67， m=n+1，2n+1 = 67， 則有 n=33 ，m=34，所以度為2的節點有33個，度為0的節點有34個，
3、使用一個長度最大為150的佇列，對滿二叉樹進行廣度優先遍歷時，能容納的二叉樹最大深度為 2^(n-1) ，
4、一棵左右子樹不空的二叉樹，前序和后序先說好空指標域都是1，中序是2，
5、求圖的最小生成樹演算法：
①Prim演算法：適合稠密圖，貪心演算法的運用，時間復雜度O（n+e），鄰接表存盤；O(n^2)
②Kruskal演算法：適合稠密圖，貪心演算法的運用，時間復雜度O（eloge），e為邊數，
6、平衡因子=左子樹高度-右子樹高度，有四種情況可能導致二叉查找樹不平衡，分別為：
①LL：插入一個新節點到根節點的左子樹（Left）的左子樹（Left），導致根節點的平衡因子由1變為2，
②RR：插入一個新節點到根節點的右子樹（Right）的右子樹（Right），導致根節點的平衡因子由-1變為-2，
③LR：插入一個新節點到根節點的左子樹（Left）的右子樹（Right），導致根節點的平衡因子由1變為2，
④RL：插入一個新節點到根節點的右子樹（Right）的左子樹（Left），導致根節點的平衡因子由-1變為-2，
針對四種情況可能導致的不平衡，可以通過旋轉使之變平衡，有兩種基本的旋轉：
①左旋轉：將根節點旋轉到（根節點的）右子樹的右子樹的位置
②右旋轉：將根節點旋轉到（根節點的）左子樹的左子樹的位置
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/236429.html
標籤：其他
上一篇：安裝/洗掉MySQL資料庫