樹是一種比較重要的數據結構,尤其是二叉樹。二叉樹是一種特殊的樹,在二叉樹中每個節點最多有兩個子節點,一般稱為左子節點和右子節點(或左孩子和右孩子),並且二叉樹的子樹有左右之分,其次序不能任意顛倒。二叉樹是遞歸定義的,因此,與二叉樹有關的題目基本都可以用遞歸思想解決,當然有些題目非遞歸解法也應該掌握,如非遞歸遍歷節點等等。本文努力對二叉樹相關題目做一個較全的整理總結,希望對找工作的同學有所幫助。
二叉樹的常見問題及其解決程序 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