二叉樹搜索字符串我是計算機專業的學生，我上週在C.在C
其中一個問題有一個考試是一個二進制搜索一個特定的詞（串）樹，並計算它出現的次數。
樹中的每個節點都包含一個字母。
例如，如果單詞是「媽媽」，並且樹看起來像附加圖像，則函數應該返回2.請注意，如果有這樣的單詞 - 「momom」 - 函數將會計數「媽媽」只有一次。
我還沒有能夠解決這個問題。你能幫我嗎？
a
/\
b m
//\
v o o
/\ \
m t m
你要列舉所有詞語的樹，並在詞的兩端檢查是否有使用strstr()匹配。
要搜索的關鍵字是樹行走樹深度優先。
您的樹結構的語義混淆。爲了澄清你的問題，你應該手工列舉出現在樹中的所有單詞，然後編寫一個遍歷樹並打印相同列表的函數，最後一步很簡單：不要打印它們，檢查字符串是否與strstr匹配，以及統計匹配詞。
所以基本上，因爲圖像中的樹似乎沒有排序或平衡，所以你必須搜索每一個分支，直到你找到一個匹配，或者你打了一個葉子。一旦你打了一場比賽，你可以忽略下面的所有分支，因爲它們不相關。但除此之外，你不知道樹的深度，所以你不能根據深度提前結束搜索。
所以，你的算法會是這樣來的效果：
// returns the number of matches
// matchMask is a bitmap of the string sublengths that match so far...
int search(const char *substr, int substrlen, uint32_t matchMask, node_t *node) {
uint16_t newMatchMask = 0;
int bit;
ASSERT(substrlen < (sizeof(matchMask)*8));
if (node == NULL) {
// hit a leaf, stop return 0
return 0;
}
while (bit = LSB(matchMask) != -1)
{
if (node->ch == substr[bit+1])
newMatchMask |= (1 << (bit+1));
}
if (node->ch == substr[0])
newMatchMask;
if (newMatchMask & (1 << strlen)) {
// found a match, don't bother recursing
return 1;
} else {
return
search(substr, substrlen, newMatchMask, node->left) +
search(substr, substrlen, newMatchMask, node->right);
}
}
注意，我不得不做一些時髦的位圖的東西有跟蹤到目前爲止匹配，你可以匹配的深處部分子字符串。假設LSB是最低有效位的宏，如果沒有設置位，則返回-1。此外，這沒有經過測試，所以在位掩碼中可能會出現錯誤，但這個想法仍然存在。
- 編輯 -
哎呀，忘了停下遞歸如果您的節點是空白...修復
所以這個詞是樹，如果這個詞的所有字母是樹？ – wdc
是的，但按順序 – Luli
所以，基本上，你有一本字典，並正在尋找具有特定子字符串的所有單詞... – blackghost