樹是一種比較重要的數據結構，尤其是二叉樹。二叉樹是一種特殊的樹，在二叉樹中每個節點最多有兩個子節點，一般稱為左子節點和右子節點（或左孩子和右孩子），並且二叉樹的子樹有左右之分，其次序不能任意顛倒。二叉樹是遞歸定義的，因此，與二叉樹有關的題目基本都可以用遞歸思想解決，當然有些題目非遞歸解法也應該掌握，如非遞歸遍歷節點等等。本文努力對二叉樹相關題目做一個較全的整理總結，希望對找工作的同學有所幫助。
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
二叉樹節點定義如下：
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
題目列表：
1. 求二叉樹中的節點個數
2. 求二叉樹的深度
3. 前序遍歷，中序遍歷，後序遍歷
4.分層遍歷二叉樹（按層次從上往下，從左往右）
5. 將二叉查找樹變為有序的雙向鏈表
6. 求二叉樹第K層的節點個數
7. 求二叉樹中葉子節點的個數
8. 判斷兩棵二叉樹是否結構相同
9. 判斷二叉樹是不是平衡二叉樹
10. 求二叉樹的鏡像
11. 求二叉樹中兩個節點的最低公共祖先節點
12. 求二叉樹中節點的最大距離
13. 由前序遍歷序列和中序遍歷序列重建二叉樹
14.判斷二叉樹是不是完全二叉樹
詳細解答
1. 求二叉樹中的節點個數
遞歸解法：
（1）如果二叉樹為空，節點個數為0
（2）如果二叉樹不為空，二叉樹節點個數 = 左子樹節點個數 + 右子樹節點個數 + 1
參考代碼如下：
int GetNodeNum(BinaryTreeNode * pRoot)
{
if(pRoot == NULL) // 遞歸出口
return 0;
return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;
}
2. 求二叉樹的深度
遞歸解法：
（1）如果二叉樹為空，二叉樹的深度為0
（2）如果二叉樹不為空，二叉樹的深度 = max(左子樹深度， 右子樹深度) + 1
參考代碼如下：
int GetDepth(BinaryTreeNode * pRoot)
{
if(pRoot == NULL) // 遞歸出口
return 0;
int depthLeft = GetDepth(pRoot->m_pLeft);
int depthRight = GetDepth(pRoot->m_pRight);
return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);
}
3. 前序遍歷，中序遍歷，後序遍歷
前序遍歷遞歸解法：
（1）如果二叉樹為空，空操作
（2）如果二叉樹不為空，訪問根節點，前序遍歷左子樹，前序遍歷右子樹
參考代碼如下：
void PreOrderTraverse(BinaryTreeNode * pRoot)
{
if(pRoot == NULL)
return;
Visit(pRoot); // 訪問根節點
PreOrderTraverse(pRoot->m_pLeft); // 前序遍歷左子樹
PreOrderTraverse(pRoot->m_pRight); // 前序遍歷右子樹
}
中序遍歷遞歸解法
（1）如果二叉樹為空，空操作。
（2）如果二叉樹不為空，中序遍歷左子樹，訪問根節點，中序遍歷右子樹
參考代碼如下：
void InOrderTraverse(BinaryTreeNode * pRoot)
{
if(pRoot == NULL)
return;
InOrderTraverse(pRoot->m_pLeft); // 中序遍歷左子樹
Visit(pRoot); // 訪問根節點
InOrderTraverse(pRoot->m_pRight); // 中序遍歷右子樹
}
後序遍歷遞歸解法
（1）如果二叉樹為空，空操作
（2）如果二叉樹不為空，後序遍歷左子樹，後序遍歷右子樹，訪問根節點
參考代碼如下：
void PostOrderTraverse(BinaryTreeNode * pRoot)
{
if(pRoot == NULL)
return;
PostOrderTraverse(pRoot->m_pLeft); // 後序遍歷左子樹
PostOrderTraverse(pRoot->m_pRight); // 後序遍歷右子樹
Visit(pRoot); // 訪問根節點
}
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2014-07/104857p2.htm
