c - C 中的二叉树 : Traversal specified level

Question

晚上好

我有一个任务:计算指定级别树的元素的平均值。我不知道如何在树中定义特定级别并获取该级别上节点元素的总和...

这是现有的代码:

#include <iostream>
#include <conio.h>

using namespace std;

struct Node
{
       int x;
       Node *left, *right;
};

Node *tree = NULL;

void push( int a, Node**Mytree)
{
     if( (*Mytree) == NULL ){
         (*Mytree) = new Node;
         (*Mytree) -> x = a;
         (*Mytree) -> left = (*Mytree) -> right = NULL;
         return;
     }

     if( a > ( (*Mytree) -> x) ) push( a, &(*Mytree) -> right);
     else push( a, &(*Mytree) -> left);
}

void print (Node *Mytree, int u)
{

      if(Mytree){
      print(Mytree->left, u+1);
      for ( int i = 0; i < u; i++) cout << "   ";
      cout << Mytree -> x<< endl;
      print( Mytree -> right, u+1);
      }

}
int main()
{
     int n,s;
     cout << "Enter amount of elements: \n";
     cin >> n;

     for ( int i =0; i < n; ++i){
         cout << "Enter element's value: \n";
         cin >> s;
         push ( s , &tree);
     }
     cout << "Printing your tree...\n";
     print(tree,0);
     getch();
     return 0;
     }

如果可能，请建议我执行此任务的函数。

Answer 1

struct result {
    int sum;
    unsigned int cnt;
}

void count_elems(struct Node const *tree, unsigned int lvl, struct result *res)
{
    if (!tree) {
         ; /* noop */
    } else if (lvl > 0) {
         count_elems(tree->left, lvl - 1, res);
         count_elems(tree->right, lvl - 1, res);
    } else {
         res->sum += tree->x;
         ++res->cnt;
    }
}