我需要知道一棵樹有多少片葉子，但有一些條件。
- 所有的孩子或葉子，總是在同一層，但可以是 1、2、3、4、5 層……我不知道會是哪一個。所以你不能算孫子 孫子……??他們將處于同一級別并且將是其中較低的一個，在這種情況下：孫子。
- 一定有一個沒有葉子的節點，但如果不是最低層的葉子，則不必算作葉子。
我將嘗試用一些例子來解釋自己。想象一下你有這棵樹：
A
|- B
| |- B1
| |- B2 Number of 'leafs' = 2 (B1 and B2). C doesn't count as it is in an
| upper level)
|- C
另一個例子：
A
|- B
| |- B1
| |- B2 Number of 'leafs' = 3 (B1,B2,D1)
|
|- C
|- D
|-D1
另一個例子：
A
|- B
| |- B1
| | |-B11
| |- B2 Number of 'leafs' = 1 (B11). D1 is not a leaf. It is a 'node' as
| leafs in this case are in level 4 (counting A as 1)
|- C
|- D
|-D1
我正在使用類似于 QTreeWidgetItem 的 C 和 Qt，所以我有一個物件（讓我們稱其為 myTree，我可以問這樣的問題：myTree->childCount()所以在第一個示例中，如果我呼叫它，它會說 2（B 和 C）對于每一個，我都可以重復操作。
I was trying to count everything that gives me childcount() but then, it gaves me 4 (B,C,B1 and B2) instead of 2 (B1,B2) which is what i want...Here I put what I was trying:
int grandchild = 0;
for (int i = 0; i < myTree->childCount( ); i)
{
Obj* child = myTree->child( i ); //Get the children. First time will be B and C
if (child)
{
grandchild = p_child->childCount( ); // Here I wanted to get a total, for first example, I will get 3 which is not what I want
}
}
Thank you in advance.
uj5u.com熱心網友回復：
對于遞回函式，您首先假設該函式在節點上運行時將回傳有關該節點的所有相關資訊。然后每個節點只需要檢查它的子節點和它自己來決定回傳到它上面的級別。
如果該節點沒有子節點，則結果很簡單：該節點在深度為 0（自身）處有一個最大深度節點。
否則，最大深度等于其子級中最大的最大深度 1，并且計數等于共享最大最大深度的所有子級的計數之和。
#include <utility>
#include <vector>
struct node_type {
std::vector<node_type*> children;
};
// returns the max depth between the node and all of its children
// along with the number of nodes at that depth
std::pair<int, int> max_depth_count(const node_type& node) {
int depth = 0; // itself
int count = 1; // itself
for (const auto c : node.children) {
auto [child_depth, child_count] = max_depth_count(*c);
child_depth ;
if (child_depth > depth) {
depth = child_depth;
count = child_count;
}
else if (child_depth == depth) {
count = child_count;
}
}
return {depth, count};
}
uj5u.com熱心網友回復：
一種方法是執行廣度優先遍歷。這樣您就可以逐層訪問，最后一個非空層的大小就是您所需要的。
這種廣度優先遍歷可以使用佇列來完成。
以下是如何使用您在問題中提供的介面 ( Obj*, childCount, child)對其進行編碼：
int n = 0; // number of nodes in the "current" level
if (myTree != nullptr) {
std::queue<Obj*> q;
q.push(myTree); // The first level just has the root
while (q.size()) { // While the level is not empty...
n = q.size(); // ...remember its size
for (int i = 0; i < n; i) { // ...and replace this level with the next
Obj* node = q.front();
q.pop();
int m = node->childCount();
for (int j = 0; j < m; j) {
q.push(node->child(j));
}
}
}
}
std::cout << n << "\n";
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/359391.html
標籤：c algorithm qt tree qtreewidget