// 求二叉樹的深度和寬度.cpp : 定義控制臺應(yīng)用程序的入口點。 <pre name="code" class="cpp">#include <iostream> #include <queue> using namespace std;struct BTNode {char m_value;BTNode *m_left;BTNode *m_right; };//先序創(chuàng)建二叉樹 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;//記錄當(dāng)前層的寬度int nWidth = 1;//二叉樹的寬度queue<BTNode *> myQueue;myQueue.push(pRoot);//將根節(jié)點入隊列nLastLevelWidth = 1;BTNode *pCur = NULL;while (!myQueue.empty())//隊列不空{(diào)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);//將根節(jié)點入隊列 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(); //新增加的一層個數(shù)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.概念解析：

寬度:節(jié)點的葉子數(shù)
深度:節(jié)點的層數(shù)

算法上有所謂的"寬度優(yōu)先算法"和"深度優(yōu)先算法"

二叉樹的寬度定義為具有最多結(jié)點數(shù)的層中包含的結(jié)點數(shù)。



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

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

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

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

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

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

參考文獻(xiàn)：

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

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

總結(jié)

以上是生活随笔為你收集整理的求二叉树的深度和宽度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。