二叉樹題目總結(jié)
二叉樹題目總結(jié)
樹是一種比較重要的數(shù)據(jù)結(jié)構(gòu)，尤其是二叉樹。二叉樹是一種特殊的樹，在二叉樹中每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，一般稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)（或左孩子和右孩子），并且二叉樹的子樹有左右之分，其次序不能任意顛倒。二叉樹是遞歸定義的，因此，與二叉樹有關(guān)的題目基本都可以用遞歸思想解決，當(dāng)然有些題目非遞歸解法也應(yīng)該掌握，如非遞歸遍歷節(jié)點(diǎn)等等。本文努力對(duì)二叉樹相關(guān)題目做一個(gè)較全的整理總結(jié)，希望對(duì)找工作的同學(xué)有所幫助。
二叉樹節(jié)點(diǎn)定義如下：
struct BinaryTreeNode
{
?int m_nValue;
?BinaryTreeNode* m_pLeft;
?BinaryTreeNode* m_pRight;
};
相關(guān)鏈接：
輕松搞定面試中的鏈表題目
題目列表：
1. 求二叉樹中的節(jié)點(diǎn)個(gè)數(shù)
2. 求二叉樹的深度
3. 前序遍歷，中序遍歷，后序遍歷
4.分層遍歷二叉樹（按層次從上往下，從左往右）
5. 將二叉查找樹變?yōu)橛行虻碾p向鏈表
6. 求二叉樹第K層的節(jié)點(diǎn)個(gè)數(shù)
7. 求二叉樹中葉子節(jié)點(diǎn)的個(gè)數(shù)
8. 判斷兩棵二叉樹是否結(jié)構(gòu)相同
9. 判斷二叉樹是不是平衡二叉樹
10. 求二叉樹的鏡像
11. 求二叉樹中兩個(gè)節(jié)點(diǎn)的最低公共祖先節(jié)點(diǎn)
12. 求二叉樹中節(jié)點(diǎn)的最大距離
13. 由前序遍歷序列和中序遍歷序列重建二叉樹
14.判斷二叉樹是不是完全二叉樹
詳細(xì)解答
1. 求二叉樹中的節(jié)點(diǎn)個(gè)數(shù)
遞歸解法：
（1）如果二叉樹為空，節(jié)點(diǎn)個(gè)數(shù)為0
（2）如果二叉樹不為空，二叉樹節(jié)點(diǎn)個(gè)數(shù) = 左子樹節(jié)點(diǎn)個(gè)數(shù) + 右子樹節(jié)點(diǎn)個(gè)數(shù) + 1
參考代碼如下：
[cpp]view
plaincopy
intGetNodeNum(BinaryTreeNode*pRoot)
{
if(pRoot==NULL)//遞歸出口
return0;
returnGetNodeNum(pRoot->m_pLeft)+GetNodeNum(pRoot->m_pRight)+1;
}
2. 求二叉樹的深度
遞歸解法：
（1）如果二叉樹為空，二叉樹的深度為0
（2）如果二叉樹不為空，二叉樹的深度 = max(左子樹深度， 右子樹深度) + 1
參考代碼如下：
[cpp]view
plaincopy
intGetDepth(BinaryTreeNode*pRoot)
{
if(pRoot==NULL)//遞歸出口
return0;
intdepthLeft=GetDepth(pRoot->m_pLeft);
intdepthRight=GetDepth(pRoot->m_pRight);
returndepthLeft>depthRight?(depthLeft+1):(depthRight+1);
}
3. 前序遍歷，中序遍歷，后序遍歷
前序遍歷遞歸解法：
（1）如果二叉樹為空，空操作
（2）如果二叉樹不為空，訪問根節(jié)點(diǎn)，前序遍歷左子樹，前序遍歷右子樹
參考代碼如下：
[cpp]view
plaincopy
voidPreOrderTraverse(BinaryTreeNode*pRoot)
{
if(pRoot==NULL)
return;
Visit(pRoot);//訪問根節(jié)點(diǎn)
PreOrderTraverse(pRoot->m_pLeft);//前序遍歷左子樹
PreOrderTraverse(pRoot->m_pRight);//前序遍歷右子樹
}
中序遍歷遞歸解法
（1）如果二叉樹為空，空操作。
（2）如果二叉樹不為空，中序遍歷左子樹，訪問根節(jié)點(diǎn)，中序遍歷右子樹
參考代碼如下：
[cpp]view
plaincopy
voidInOrderTraverse(BinaryTreeNode*pRoot)
{
if(pRoot==NULL)
return;
InOrderTraverse(pRoot->m_pLeft);//中序遍歷左子樹
Visit(pRoot);//訪問根節(jié)點(diǎn)
InOrderTraverse(pRoot->m_pRight);//中序遍歷右子樹
}
后序遍歷遞歸解法
（1）如果二叉樹為空，空操作
（2）如果二叉樹不為空，后序遍歷左子樹，后序遍歷右子樹，訪問根節(jié)點(diǎn)
參考代碼如下：
[cpp]view
plaincopy
voidPostOrderTraverse(BinaryTreeNode*pRoot)
{
if(pRoot==NULL)
return;
PostOrderTraverse(pRoot->m_pLeft);//后序遍歷左子樹
PostOrderTraverse(pRoot->m_pRight);//后序遍歷右子樹
Visit(pRoot);//訪問根節(jié)點(diǎn)
}
4.分層遍歷二叉樹（按層次從上往下，從左往右）
相當(dāng)于廣度優(yōu)先搜索，使用隊(duì)列實(shí)現(xiàn)。隊(duì)列初始化，將根節(jié)點(diǎn)壓入隊(duì)列。當(dāng)隊(duì)列不為空，進(jìn)行如下操作：彈出一個(gè)節(jié)點(diǎn)，訪問，若左子節(jié)點(diǎn)或右子節(jié)點(diǎn)不為空，將其壓入隊(duì)列。
[cpp]view plaincopy voidLevelTraverse(BinaryTreeNode*pRoot) { if(pRoot==NULL) return; queue
下載文檔
