2013-11-26 76 views
0

晚上好C中的二叉樹:遍歷指定級別

我有一個任務:計算樹指定級別元素的平均值。我不知道如何在樹中定義一個特定的水平,並得到節點的上這個級別的元素SUMM ...

這裏是現有代碼:

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

如果可能的話,建議我要的功能這個任務。

+1

這是C++,而不是C. –

+0

您是否知道您的教師在「指定級別」上的含義? –

+0

@qwrrty:我猜根節點級別0,它下面的兩個子節點級別1等。 –

回答

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