[数据结构与算法]【专题四】求二叉树深度的递归与非递归写法

//求二叉树深度  递归写法
int deep1(BTNode *T)
{
	if(T==NULL)
		return 0;
	int lhight = deep1(T->lchild)+1;//左子树高度
	int rhight = deep1(T->rchild)+1;//右子树高度
	return lhight>rhight?lhight:rhight; //返回最大的高度	
} 

//求二叉树深度  非递归写法  
/**
算法思想：设置一个level指针指向当前遍历的层数，
    每次遍历到当前层最右边的一个结点后，就将level指针+1，即开始遍历下一层。
 	遍历完所有结点后level的大小就该树的高度。 
**/
int deep2(BTNode *T)
{	 
	if(T==NULL)
		return 0;
	int level,rear,front,last;//指向当前遍历到的层数	
	rear = front = -1;
	last = level = 0;  //last表示当前遍历所在层的最右结点在队列中的位置。 
	/**
	初始时rear和front为0，而last为0的原因，是因为初始时根结点入队，且数组队列是从下标为0开始存数据的,que[0]中存储的是第一层的最右边结点。
		如果初始时，rear = front = 0;last=1，也是可以的。这表示从下标为1开始存数据，que[1]存储的是第一层的最右边的结点 
	*/ 
	BTNode *que[maxSize],*q;
	que[++rear] = T;//根结点先入队
	//开始层序遍历所有结点 
	while(front<rear) //如果队列不为空，即结点没被遍历完就一直循环遍历 
	{
		q = que[++front]; //队首元素出队

		if(q->lchild!=NULL)//该元素有左孩子则将左孩子入队 
			que[++rear] = q->lchild; 
			
		if(q->rchild!=NULL)//该元素有右孩子则将左孩子入队 
			que[++rear] = q->rchild; 
			
		if(front == last)  //如果遍历到了该层的最右结点，则处理level指针
		{
			last = rear;//将last指向下一层的最右边结点,而执行完前面的孩子入队操作后，rear指向的就是队尾，所以将rear赋给last 
			++level;//将level指向下一层 
		} 
	} 
	return level;
}