// 求二叉樹的深度和寬度.cpp : 定義控制臺應用程序的入口點。
<pre name="code" class="cpp">#include <iostream>
#include <queue>
using namespace std;struct BTNode
{char m_value;BTNode *m_left;BTNode *m_right;
};//先序創建二叉樹
void CreatBTree(BTNode *&root)
{ char nValue = 0;cin >> nValue;if ('#' == nValue){return;}else{root = new BTNode();root->m_value = nValue;CreatBTree(root->m_left);CreatBTree(root->m_right);} 
}//求二叉樹的深度
int GetDepth(BTNode *pRoot)
{if (pRoot == NULL){return 0;}// int nLeftLength = GetDepth(pRoot->m_left);// int nRigthLength = GetDepth(pRoot->m_right);// return nLeftLength > nRigthLength ? (nLeftLength + 1) : (nRigthLength + 1);return GetDepth(pRoot->m_left) > GetDepth(pRoot->m_right) ? (GetDepth(pRoot->m_left) + 1) : (GetDepth(pRoot->m_right) + 1);
}//求二叉樹的寬度
int GetWidth(BTNode *pRoot)   //方法一
{if (pRoot == NULL){return 0;}int nLastLevelWidth = 0;//記錄上一層的寬度int nTempLastLevelWidth = 0;int nCurLevelWidth = 0;//記錄當前層的寬度int nWidth = 1;//二叉樹的寬度queue<BTNode *> myQueue;myQueue.push(pRoot);//將根節點入隊列nLastLevelWidth = 1;BTNode *pCur = NULL;while (!myQueue.empty())//隊列不空{nTempLastLevelWidth = nLastLevelWidth;while (nTempLastLevelWidth != 0){pCur = myQueue.front();//取出隊列頭元素myQueue.pop();//將隊列頭元素出對if (pCur->m_left != NULL){myQueue.push(pCur->m_left);}if (pCur->m_right != NULL){myQueue.push(pCur->m_right);}nTempLastLevelWidth--;}nCurLevelWidth = myQueue.size();nWidth = nCurLevelWidth > nWidth ? nCurLevelWidth : nWidth;nLastLevelWidth = nCurLevelWidth;}return nWidth;
}
int GetWidth2(BTNode *head)  //方法二
{if (head == NULL)  {  return 0;  }  int nTempLastLevelWidth = 0;  int nWidth = 1;//二叉樹的寬度  queue<BTNode *> myQueue;  myQueue.push(head);//將根節點入隊列    myQueue.push(NULL);BTNode *pCur = NULL;  while (!myQueue.empty())//隊列不空  {  pCur = myQueue.front();//取出隊列頭元素  while (pCur != NULL)  {   myQueue.pop();//將隊列頭元素出對  if (pCur->m_left != NULL)  {  myQueue.push(pCur->m_left);  }  if (pCur->m_right != NULL)  {  myQueue.push(pCur->m_right);  }  pCur = myQueue.front();//取出隊列頭元素 } myQueue.pop();//將隊列頭元素NULL出對  nTempLastLevelWidth = myQueue.size();  //新增加的一層個數if (nTempLastLevelWidth>0){myQueue.push(NULL);}nWidth = nTempLastLevelWidth > nWidth ? nTempLastLevelWidth : nWidth;  }  return nWidth;  }int main()
{BTNode *pRoot = NULL;CreatBTree(pRoot);cout << "二叉樹的深度為：" << GetDepth(pRoot) << endl;cout << "二叉樹的寬度為：" << GetWidth(pRoot) << endl;system("pause");return 0;
}

說明：

? ?1.概念解析：

寬度:節點的葉子數
深度:節點的層數

算法上有所謂的"寬度優先算法"和"深度優先算法"

二叉樹的寬度定義為具有最多結點數的層中包含的結點數。



比如上圖中，
第1層有1個節點，
第2層有2個節點，
第3層有4個節點，
第4層有1個節點，
可知，第3層的結點數最多
所以這棵二叉樹的寬度就是4

2. 求解二叉樹根節點的深度就是比較左右子樹的深度。因此根節點的深度=左右子樹深度的最大值+1；

因此可以使用遞歸算法。在使用中實際上就是后序遍歷.

3.求解寬度，何為二叉樹的寬度，即為含有節點個數最多也就是最長的那一層的長度。因此我們可以想到層次遍歷。使用queue。

我們需要理清每層的節點分別是誰？可以有兩種辦法，一種就是在插入新節點的時候計算長度，等到下一次遍歷時清除掉上一層的節點，依據個數。

二、就是在每一層后面插入一個NULL，最后一層沒有數據，可以不插。這樣一層層遍歷，遇到NULL，表明到達結尾。然后開始下一層遍歷。

參考文獻：

?1.?http://blog.csdn.net/htyurencaotang/article/details/12406223

?2.?http://blog.csdn.net/wuzhekai1985/article/details/6730352