計算樹中的葉節點

假設我們有一棵樹，每個節點都有一組預定的傳出節點。是否有可能提出一個快速的方式/優化來計算給定級別值的葉節點數量？如果有人能夠提出任何想法/鏈接/資源來做同樣的事情，那將會很棒。計算樹中的葉節點

2016-03-23 nev.m

你的意思是說，每個節點都有「d」個孩子？ –

@SalvadorDali不一定 –

然後有沒有簡單的方法來計算它（通過容易我的意思是沒有看整個樹），因爲代碼實際上很容易。 –

不，你仍然需要遍歷整個樹。沒有辦法只從樹的每個節點的子節點數量來預測精確的結構 - 或近似它。

除此之外：只保留一個計數器並在每次插入時更新它。更簡單並且不會改變任何操作的時間複雜度，除了計算樹葉數量，其將減少到O(1)。

2016-03-23 23:12:59 Paul

你可以提供一個簡單的僞代碼來說明如何計算O（1）次葉節點的「數量」嗎？ –

@ N.M。正如我在答案中已經寫過的那樣：只用葉子的計數器。我不認爲這需要任何代碼來解釋。代碼幾乎是一個樹的完整實現 – Paul

這實際上可以變得非常艱難的事情。由於它改變了什麼是編程語言，什麼是輸入數據結構，是樹二進制還是一般樹（任意數量的子樹），樹的大小。

最普遍的想法是從根開始運行DFS或BFS，以獲取每個節點級別，然後創建一個集合列表，其中每個集合包含單個級別的節點。該集可以是任何結構，標準列表是好的。

假設你在C++中工作，如果你需要性能（甚至比C更好），那麼這是很好的，如果不是最好的實際選擇的話。

比方說，我們有一個通用樹，輸入結構就像您提到的那樣是鄰接表。

//nodes are numbered from zero to N-1 
vector<vector<int>> adjList;

然後，您運行BFS或DFS，要麼爲樹，要爲每個節點保留一個級別。下一個節點的級別是其父級加一級。

一旦你發現了關卡，你就把這個節點放在這裏。

vector<vector<int>> nodesPartitionedByLevels(nodeCount); 
//run bfs here 
//inside it you call 
nodesPartitionedByLevels[level].push_back(node)

就是這樣。

然後，當您擁有這些關卡時，您會迭代該關卡上的所有節點，並檢查鄰接關係列表是否包含任何節點。您可以撥打adjList[node].empty()。如果真的比那是葉節點。

2016-03-23 23:18:50 dimm

回答