计算树中的叶节点

假设我们有一棵树，每个节点都有一组预定的传出节点。是否有可能提出一个快速的方式/优化来计算给定级别值的叶节点数量？如果有人能够提出任何想法/链接/资源来做同样的事情，那将会很棒。计算树中的叶节点

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

回答