【文章內(nèi)容簡(jiǎn)介】 不是我們熟悉的前序、中序或者后序遍歷。我們從樹(shù)的根結(jié)點(diǎn)開(kāi)始分析。自然先應(yīng)該打印根結(jié)點(diǎn)8，同時(shí)為了下次能夠打印8的兩個(gè)子結(jié)點(diǎn)，我們應(yīng)該在遍歷到8時(shí)把子結(jié)點(diǎn)6和10保存到一個(gè)數(shù)據(jù)容器中?，F(xiàn)在數(shù)據(jù)容器中就有兩個(gè)元素6和10了。按照從左往右的要求，我們先取出6訪問(wèn)。打印6的同時(shí)要把6的兩個(gè)子結(jié)點(diǎn)5和7放入數(shù)據(jù)容器中，此時(shí)數(shù)據(jù)容器中有三個(gè)元素5和7。接下來(lái)我們應(yīng)該從數(shù)據(jù)容器中取出結(jié)點(diǎn)10訪問(wèn)了。注意10比5和7先放入容器，此時(shí)又比5和7先取出，就是我們通常說(shuō)的先入先出。因此不難看出這個(gè)數(shù)據(jù)容器的類型應(yīng)該是個(gè)隊(duì)列。既然已經(jīng)確定數(shù)據(jù)容器是一個(gè)隊(duì)列，現(xiàn)在的問(wèn)題變成怎么實(shí)現(xiàn)隊(duì)列了。實(shí)際上我們無(wú)需自己動(dòng)手實(shí)現(xiàn)一個(gè)，因?yàn)镾TL已經(jīng)為我們實(shí)現(xiàn)了一個(gè)很好的deque（兩端都可以進(jìn)出的隊(duì)列），我們只需要拿過(guò)來(lái)用就可以了。我們知道樹(shù)是圖的一種特殊退化形式。同時(shí)如果對(duì)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷有比較深刻的理解，將不難看出這種遍歷方式實(shí)際上是一種廣度優(yōu)先遍歷。因此這道題的本質(zhì)是在二元樹(shù)上實(shí)現(xiàn)廣度優(yōu)先遍歷。參考代碼：include dequeinclude iostreamusing namespace std。struct BTreeNode // a node in the binary tree{ int m_nValue。 // value of node BTreeNode *m_pLeft。 // left child of node BTreeNode *m_pRight。 // right child of node}。///////////////////////////////////////////////////////////////////////// Print a binary tree from top level to bottom level// Input: pTreeRoot the root of binary tree///////////////////////////////////////////////////////////////////////void PrintFromTopToBottom(BTreeNode *pTreeRoot){ if(!pTreeRoot) return。 // get a empty queue dequeBTreeNode * dequeTreeNode。 // insert the root at the tail of queue (pTreeRoot)。 while(()) { // get a node from the head of queue BTreeNode *pNode = ()。 ()。 // print the node cout pNodem_nValue 39。 39。 // print its left child subtree if it has if(pNodem_pLeft) (pNodem_pLeft)。 // print its right child subtree if it has if(pNodem_pRight) (pNodem_pRight)。 }}程序員面試題精選100題(13)－第一個(gè)只出現(xiàn)一次的字符字符串 20070321 21:17:22 閱讀5465 評(píng)論30 字號(hào)：大中小訂閱 題目：在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。 分析：這道題是2006年google的一道筆試題。看到這道題時(shí)，最直觀的想法是從頭開(kāi)始掃描這個(gè)字符串中的每個(gè)字符。當(dāng)訪問(wèn)到某字符時(shí)拿這個(gè)字符和后面的每個(gè)字符相比較，如果在后面沒(méi)有發(fā)現(xiàn)重復(fù)的字符，則該字符就是只出現(xiàn)一次的字符。如果字符串有n個(gè)字符，每個(gè)字符可能與后面的O(n)個(gè)字符相比較，因此這種思路時(shí)間復(fù)雜度是O(n2)。我們?cè)囍フ乙粋€(gè)更快的方法。由于題目與字符出現(xiàn)的次數(shù)相關(guān)，我們是不是可以統(tǒng)計(jì)每個(gè)字符在該字符串中出現(xiàn)的次數(shù)？要達(dá)到這個(gè)目的，我們需要一個(gè)數(shù)據(jù)容器來(lái)存放每個(gè)字符的出現(xiàn)次數(shù)。在這個(gè)數(shù)據(jù)容器中可以根據(jù)字符來(lái)查找它出現(xiàn)的次數(shù)，也就是說(shuō)這個(gè)容器的作用是把一個(gè)字符映射成一個(gè)數(shù)字。在常用的數(shù)據(jù)容器中，哈希表正是這個(gè)用途。哈希表是一種比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。由于比較復(fù)雜，STL中沒(méi)有實(shí)現(xiàn)哈希表，因此需要我們自己實(shí)現(xiàn)一個(gè)。但由于本題的特殊性，我們只需要一個(gè)非常簡(jiǎn)單的哈希表就能滿足要求。由于字符（char）是一個(gè)長(zhǎng)度為8的數(shù)據(jù)類型，因此總共有可能256 種可能。于是我們創(chuàng)建一個(gè)長(zhǎng)度為256的數(shù)組，每個(gè)字母根據(jù)其ASCII碼值作為數(shù)組的下標(biāo)對(duì)應(yīng)數(shù)組的對(duì)應(yīng)項(xiàng)，而數(shù)組中存儲(chǔ)的是每個(gè)字符對(duì)應(yīng)的次數(shù)。這樣我們就創(chuàng)建了一個(gè)大小為256，以字符ASCII碼為鍵值的哈希表。我們第一遍掃描這個(gè)數(shù)組時(shí)，每碰到一個(gè)字符，在哈希表中找到對(duì)應(yīng)的項(xiàng)并把出現(xiàn)的次數(shù)增加一次。這樣在進(jìn)行第二次掃描時(shí)，就能直接從哈希表中得到每個(gè)字符出現(xiàn)的次數(shù)了。參考代碼如下：///////////////////////////////////////////////////////////////////////// Find the first char which appears only once in a str