C++ getting lowest level of a tree

0
votes

I need to know how many leafs have a tree but with some conditions.

  • All the children or leafs, will be always on the same level, but it can be the level 1,2,3,4,5 ... I don't know which one will be. So you can't count grandhildren + grandgrandchildren ... they will be at the same level and will be the lower of them, in that case: grandgrandchildren.
  • There must be a node without leafs, but if it is not the lowest level of leafs, it doesn't have to count as leaf.

I will try to explain myself with some examples. Imagine you have this tree:

 A
 |- B
 |  |- B1
 |  |- B2                 Number of 'leafs' = 2 (B1 and B2). C doesn't count as it is in an 
 |                                                           upper level)
 |- C

Another example:

 A
 |- B
 |  |- B1
 |  |- B2                 Number of 'leafs' = 3 (B1,B2,D1)
 |
 |- C
 |- D
    |-D1

Another example:

 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

I'm working with C++ and Qt with something similar to QTreeWidgetItem so I have an object (let's call it myTree and I can ask something like: myTree->childCount() so in the first example, if I call it, it will say 2 (B and C) and for each one I can repeat the operation.

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.

2
c++algorithmqttreeqtreewidget
You want each node to report the furthest leaf distance, and the number of leafs at that distance, among its children. Call this recursively for your answer. What's your question? – JohnFilleau
If you're getting to "grandchildren" you're already going too far. – JohnFilleau
@JohnFilleau ´report the furthest leaf distance,´ Oh.. I didn't think in that option! Thank you! About recursively, need to check how to do it :) Why do you think grandchildren is too far? It could be a tree with 10 levels... (hope not hehe) – Megasa3
when dealing with recursive algorithms, the current iteration of the recursion should only care about itself, and the thing "below" it. This operation on a given node should only inspect its children using the same operation, and return the result up. It should only care about its children. If a node starts caring about its grandchild, you're making things harder on yourself. – JohnFilleau
Probably because tracking three levels of nodes is unnecessary. Tree height is easily computed with only parent and child tracked. For example, the recursive tree height for a binary tree looks something like int get_height(Node * current) { if (!current)return 0; return 1+ max(get_height(current->right), get_height(current->left)); With a non-binary tree you expand to get the max of an arbitrary number of children and you'll have to add logic for your own extra special rules. – user4581301

2 Answers

0
votes

For recursive functions, you start with the assumption that the function, when operating on a node, will return all relevant information about that node. Each node then only needs to inspect its children and itself to decide what to return to the level above it.

If the node has no children, then the result is trivial: this node has one max depth node at a depth of 0 (itself).

Otherwise, the max depth is equal to the largest max depth among its children + 1, and the count is equal to the sum of the counts of all children that share the largest max depth.

#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};
}
0
votes

One way to do this, is to perform a breadth-first traversal. That way you visit one level after the other, and the size of the last non-empty level is then what you need.

Such a breadth-first traversal can be done using a queue.

Here is how you can code it using the interface (Obj*, childCount, child) you provided in the question:

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";