学步园

二叉树的深度：从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

二叉树的宽度：二叉树的每一层中都有一定数量的节点，节点数最多的那一层的节点数叫做二叉树的宽度。

假设二叉树的节点有如下数据结构：

struc Node{

int num;

Node* pLeft;

Node* pRight;

}

1)求二叉树的深度

根据刚才对二叉树深度的说明，我们会很容易想到递归的方法。很显然只有一个节点的二叉树的深度是1，没有节点的二叉树的深度是0.假设一棵二叉树带有两个孩子节点，那么我可以说这棵二叉树的深度等于根节点的左右孩子节点的深度的最大值再加上1.假设有如下的一颗二叉树，那么它的深度是3，宽度是2.

            10

       /   \

      5     15

    /       /

   3        12      

int DeepthOfTheTree(Node* pRoot)
{
	if(pRoot==NULL)
		return 0;
	int DL=DeepthOfTheTree(pRoot->pLeft);
	int DR=DeepthOfTheTree(pRoot->pRight);
	int Depth=DL>DR? DL:DR;
	return Depth+1;
}

2）求二叉树的宽度

我们可以把二叉树中每层的节点依次放入一个队列中。设置一个变量width用于存储树的宽度。每一层的节点入队时计算该层节点的数目，如果该层次节点的数目大于width的值，那么把该层次节点的数目赋给width.如此，对二叉树按层遍历一遍之后width中保存的就是该二叉树的宽度。

int WidthOfTheTree(Node* pRoot)
{
	if(pRoot==NULL)
		return 0;
	queue<Node*> MyQueue2;
	MyQueue2.push(pRoot);
	int width=1;
	int curwidth=1;
	int nextwidth=0;
	while(!MyQueue2.empty())
	{
		while(curwidth!=0)
		{
			Node* pTmp=MyQueue2.front();
			MyQueue2.pop();
			curwidth--;
			if(pTmp->pLeft!=NULL)
			{
				MyQueue2.push(pTmp->pLeft);
				nextwidth++;
			}
			if (pTmp->pRight!=NULL)
			{
				MyQueue2.push(pTmp->pRight);
				nextwidth++;
			}
		}
		if(nextwidth>width)
			width=nextwidth;
		curwidth=nextwidth;
		nextwidth=0;
	}
	return width;
}