二叉树非递归求深度详解编程语言

#include <assert.h> 
#include <iostream> 
#include <queue> 
#include <ctime> 
 
using namespace std; 
 
struct Node 
{ 
	int data; 
	Node *left; 
	Node *right; 
}; 
 
struct denode 
{ 
	Node* node; 
	int degree; 
}; 
 
//二叉树非递归求深度 
int getDegree(Node* root) 
{ 
	assert(root); 
	queue<denode> que; 
	 
	denode dnode; 
	dnode.degree=1; 
	dnode.node=root; 
 
	que.push(dnode); 
 
	int degree=1; 
	while(!que.empty()) 
	{ 
		denode ptr=que.back(); 
		que.pop(); 
 
		degree=ptr.degree; 
 
		if(ptr.node->left!=NULL) 
		{ 
			denode p; 
			p.node=ptr.node->left; 
			p.degree=ptr.degree+1; 
			que.push(p); 
		} 
 
		if(ptr.node->right!=NULL) 
		{ 
			denode p; 
			p.node=ptr.node->right; 
			p.degree=ptr.degree+1; 
			que.push(p); 
		} 
	} 
	return degree; 
} 
 
Node * insert(Node* root,int key) 
{ 
	if(!root) 
	{ 
		root=new Node; 
		root->data=key; 
		root->left=root->right=NULL; 
	} 
	else if(key<=root->data) 
		root->left=insert(root->left,key); 
	else 
		root->right=insert(root->right,key); 
	return root; 
} 
 
Node* init(int n) 
{ 
	Node* root=NULL; 
	srand((int)time(0));//给rand()提供种子seed 
	for(int i=0;i<n;i++) 
	{ 
		root=insert(root,rand()%n);//使得种子为一个不固定的数， 这样产生的随机数就不会每次执行都一样了 
	}		 
	return root; 
} 
 
int main() 
{ 
	Node* root=init(5); 
	int degree=getDegree(root); 
	cout<<degree<<endl; 
	getchar(); 
	return 0; 
}