Бинарное дерево

[gorro]

у меня всегда с бинарными деревьями проблемы были. задание - Подсчитать число узлов на k-ом уровне бинарного дерева. Корень считать узлом 1-го уровня.
помогите кто может,пжлст

[pacniwassano]

код приложите

[gorro]

я вот набрасал кое-чего, но надо, чтоб узлы вводились рандомом и надо подсчитать в конечном итоге число узлов на уровне, который введется с клавы

#include <iostream>
using namespace std;
struct node{
int d;
node *left;
node *right;
};

node * first(int d);
node * search_insert(node *root, int d);
void print_tree(node *root, int l);
int i;

int main();
int b[8]={10, 25, 20, 6, 21, 8, 1, 30};
node *root=first(b[0]);
for (int i=1; i<8; i++)search_insert(root, b[i]);
print_tree(root, 0);
return 0;
}

node *first(int d){
node *pv=new node;
pv->d=d;
pv->left=0;
pv->right=0;
return pv;
}

node *search_insert(node *root, int d){
node *pv=root, *prev;
bool found=false;
while (pv && !found){
prev=pv;
if (d==pv->d)found=true;
else if (d<pv->d) pv=pv->left;
else pv=pv->right;
}
if (found) return pv;

node *pnew=new node;
pnew->d=d;
pnew->left=0;
pnew->right=0;
if (d<prev->d)
prev->left=pnew;
else prev->right=pnew;
return pnew;
}

void print_tree(node *p, int level){
if (p){
print_tree(p->left, level+1);
for (int i=0; i<level, i++)cout << "   ";
cout << p->d << endl;
print_tree(p->right, level+1);}}

[Eugenij]

ну вообще-то принцип обхода деревьев (необязательно бинарных)
таков:
получаем корень (простой цикл)
передаем рекурсивной ф-ции в задачу которой входит обработать свой уровень и передать себе-же те узлы, которые имеют свои ветви.
в качестве второго параметра можно использовать показатель уровня (так мы гарантируем сохранность показателя при возврате)

а для вашего случая лучше пройтись циклом - ведь это просто дву-связный список.

ЗЫ.
вот рабочий пример (выдрал из одного своего проекта)

class DWPEX
{
	DWPEX* parrent;
	DWPEX* prev_s;
	DWPEX* next_s;
	DWPEX*  child;
	
	public:
		
		HWND hWnd;
		int x,y,w,h,f;
		
		DWPEX(HWND hw, int nx, int ny, int nw, int nh, int nf)
		{
			parrent=prev_s=next_s=child=0;
			hWnd=hw;
			x=nx;
			y=ny;
			w=nw;
			h=nh;
			f=nf;
		};
		
		DWPEX* get_parent(){return parrent;};
		DWPEX* get_next_siblings(){return next_s;};
		DWPEX* get_prev_siblings(){return prev_s;};
		DWPEX* get_child(){return child;};
		
		DWPEX* insert_sibling(DWPEX* p){ 
			if (p && parrent)
			{
				p->parrent = parrent;
				p->prev_s = this;
				if (next_s)
				{
					if (p->next_s)
					{
						ERR_PRINT("p->next_s");
					}
					
					p->next_s = next_s;
					next_s->prev_s = p;
				}
				return next_s = p;
			}
			return 0;
		};
		
		DWPEX* set_child(DWPEX* p){ 
			if (p && (!p->parrent) && (!p->prev_s) && (!p->next_s))
			{
				p->parrent = this;
				if (child)
				{
					if (child->prev_s)
					{
						ERR_PRINT("child->prev_s");
					}
					child->prev_s = p;
				}
				p->next_s = child;
				child = p;
				return p;
			}
			return 0;
		};
		
		DWPEX* unlink(){
			if (parrent && parrent->child == this)
			{
				parrent->child = next_s;
			}
			if (next_s)
			{
				next_s->prev_s = prev_s;
			}
			if (prev_s)
			{
				prev_s->next_s = next_s;
			}
			return this;
		};
		
		DWPEX* destroy_childs()
		{
			DWPEX *t, *p;
			t = child;
			while (t)
			{
				p = t->next_s;
				delete t;
				t = p;
			}
			child=0;
			return this;
		};
		
		
		virtual ~DWPEX(){
			destroy_childs();
		};
		
};


void Realise_DWPEX(HDWPEX dwp)
{
	if ( dwp != NULL )
	{
		HDWPEX tmp = dwp;
		do
		{
			if (tmp->hWnd)
			{
				SetWindowPos(tmp->hWnd, 0, tmp->x, tmp->y, tmp->w, tmp->h, tmp->f);
			}
		} while (tmp = tmp->get_next_siblings());
		tmp = dwp;
		do
		{
			Realise_DWPEX(tmp->get_child());
		} while (tmp = tmp->get_next_siblings());
	}
}