算法分析與設(shè)計：習(xí)題選講第七章前5題

1、第七章1426 電話號碼前綴檢索1310 二叉查找樹，前序中序后序遍歷1210 二叉樹 ，知道前序、后序求可能的方法數(shù)1090 最小生成樹1156 二叉樹的前序遍歷2011-10-2011426 電話號碼前綴檢索題目大意：給出N個電話號碼（N = 10000）,每個電話號碼的長度不大于10，當(dāng)存在一個電話號碼是另外一個電話號碼的前綴時，則會發(fā)生沖突。如果不存在沖突輸出YES，否則輸出NO2011-10-2021426 電話號碼前綴檢索解題思路：1. 把n個電話號碼放進(jìn)一個set內(nèi)2. 枚舉每個電話號碼的前綴，查詢是否存在于set里2011-10-2031426 電話號碼前綴檢索int n;st

2、ring c11000;set ss;bool isConsistent()ss.clear();for (int i = 0; i n; i+) ss.insert(ci);for (int i = 0; i n; i+) string st = ;for (int j = 0; j ci.size() - 1; j+) st += cij;if (ss.count(st) return false;return true;2011-10-2041310 二叉查找樹題目大意：給出N個數(shù)，按照順序建立一棵二叉查找樹，然后輸出該樹的前序遍歷，中序遍歷，后序遍歷。2011-10-2051310 二

3、叉查找樹struct Node int val;int left, right;Node(int val = 0):val(val), left(0),right(0) ; p300000;2011-10-2061310 二叉查找樹void Add(int root, int val) while (true) if (proot.val val) if (proot.right) root = proot.right; else proot.right = +tot； ptot = Node(val); return; else if (proot.left) root = proot.le

4、ft; else proot.left = +tot; ptot = Node(val); return; 2011-10-2071310 二叉查找樹inline void Preorder(int root)if (!root) return;printf( %d, proot.val);Preorder(proot.left);Preorder(proot.right);inline void Inorder(int root)if (!root) return;Inorder(proot.left);printf( %d, proot.val);Inorder(proot.right);

5、inline void Postorder(int root)if (!root) return;Postorder(proot.left);Postorder(proot.right);printf( %d, proot.val);2011-10-2081210 二叉樹題目大意：給出一棵二叉樹前序遍歷和后序遍歷的順序，要求出總共有多少棵不同形態(tài)的二叉樹滿足這樣的遍歷順序。2011-10-2091210 二叉樹解題思路：1. 前序遍歷第一個元素是根，后序遍歷最后一個元素是根 2. 前序遍歷第二個元素是某子樹的根，但左右不確定 3. 在后序遍歷中找到前序遍歷的第二個元素，那么以這個元素為基準(zhǔn)，可

6、以劃分新的左右子樹 4. 當(dāng)前序遍歷的第二個元素出現(xiàn)在后序遍歷的倒數(shù)第二位，以后序遍歷倒數(shù)第三位起向左數(shù)都是子樹的元素，但是左右不確定，因此有2種情況 2011-10-20101210 二叉樹long long calc(string pre, string post) long long ans = 1;int len=pre.size();for(int i= 0; i len - 1; i+) int current = len - 1;while(prei != postcurrent) current-;if(current & prei+1 = postcurrent - 1) a

7、ns *= 2;return ans;2011-10-20111090 最小生成樹題目大意：給出N=500個節(jié)點(diǎn)的無向圖，每兩個點(diǎn)之間都有一條無向邊。問該無向圖的最小生成樹中，最長的一條邊的長度。2011-10-20121090 最小生成樹解題思路： 求最小生成樹的算法中，有Prim算法和kruskal算法。Prim算法復(fù)雜度N2（N為點(diǎn)數(shù)）, Kruskal算法MlogM（M為邊數(shù)） 因此，對于稠密圖而言，Prim算法的復(fù)雜度更高效率。2011-10-20131090 最小生成樹int solve()for (int i = 0; i n; i+) ui = false, disti = e

8、0i;int ans = 0, p;for (int i = 0; i n; i+) p = -1;for (int j = 0; j distj) p = j;up = true; ans = max(ans, distp);for (int j = 0; j n; j+) if (uj | distj = epj) continue;distj = epj;return ans;2011-10-20141156 二叉樹的前序遍歷題目大意：給定一棵N個節(jié)點(diǎn)的二叉樹，輸出其前序遍歷的順序解題思路：1.按照題目要求把二叉樹讀入2.以前序遍歷順序輸出（可參考1310）2011-10-20151156 二叉樹的前序遍歷void Read_Tree()memset(is_root, 0, sizeof(is_root);char c;int l, r, m; for (int i = 0; i m c l r;is_rootm = !is_rootm;is_rootl = !is_rootl;is_rootr = !is_rootr;pm.Left = l; pm.Right = r; pm.ch = c;for (int i = 1; i = 1000; i+) if (is_rooti) root = i;2011-10-20