二叉樹是一種非常有用的結(jié)構(gòu)，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。
二叉樹的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個(gè)結(jié)點(diǎn)；深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)；對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n_0，度為2的結(jié)點(diǎn)數(shù)為n_2，則n_0=n_2+1。
一棵深度為k，且有2^k-1個(gè)節(jié)點(diǎn)稱之為滿二叉樹；深度為k，有n個(gè)節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹中，序號(hào)為1至n的節(jié)點(diǎn)對(duì)應(yīng)時(shí)，稱之為完全二叉樹。詳細(xì)定義見百度百科
二叉樹的結(jié)構(gòu)使其在排序算法中非常有用，最有用的當(dāng)屬平衡二叉樹，平衡二叉樹將會(huì)在本人的博客中討論。
說(shuō)起二叉樹，就不得不討論一下二叉樹的遍歷，一般來(lái)說(shuō)，二叉樹的遍歷方式有4種：
假設(shè)我們的樹是這樣的：
（一）前序遍歷
首先我們得分析先序遍歷的順序：A,B,D,E,C,F,G。
樹的遍歷利用遞歸來(lái)實(shí)現(xiàn)會(huì)簡(jiǎn)單一點(diǎn)，我們將遍歷一整棵樹分解成遍歷左子樹和右子樹的子問(wèn)題。
重慶分公司
重慶分公司
void PrevOrder()//前序遍歷
{
_PrevOrder(_root);
}
void _PrevOrder(BinaryTreeNode* root)
{
if (root == NULL)
{
return;
}
cout << root->_data <<" ";//先輸出根節(jié)點(diǎn)
_PrevOrder(root->_left);//在輸出左子樹
_PrevOrder(root->_right);//最后右子樹
} （二）中序遍歷
遍歷的順序：D,B,E,A,F,C,G
void MidOrder()//中序遍歷
{
_MidOrder(_root);
}
void _MidOrder(BinaryTreeNode* root)
{
if (root == NULL)
{
return;
}
_MidOrder(root->_left);
cout << root->_data << " ";
_MidOrder(root->_right);
} （三）后序遍歷
遍歷順序：D,E,B,F,G,C,A
void RearOrder()//后序遍歷
{
_RearOrder(_root);
}
void _RearOrder(BinaryTreeNode* root)
{
if (root == NULL)
{
return;
}
_RearOrder(root->_left);
_RearOrder(root->_right);
cout << root->_data << " ";
} （四）層序遍歷
遍歷順序：A,B,C,D,E,F,G
層序遍歷的話可以利用隊(duì)列先進(jìn)先出的特點(diǎn)，將每一層的節(jié)點(diǎn)入隊(duì)列，只要隊(duì)列不為空，就出一次隊(duì)列。
void SequenceOrder()//層序遍歷
{
queue*> q;
if (_root)
q.push(_root);
while (!q.empty())
{
if (q.front()->_left)
{
q.push(q.front()->_left);
}
if (q.front()->_right)
{
q.push(q.front()->_right);
}
cout << q.front()->_data<< " ";
q.pop();
}
} 樹的遍歷是比較簡(jiǎn)單的，下面我們看一下有點(diǎn)難度的：
（一）求樹的葉子節(jié)點(diǎn)的個(gè)數(shù)：
數(shù)的葉子節(jié)點(diǎn)總是在最深的一層。，每次當(dāng)一個(gè)子問(wèn)題的根節(jié)點(diǎn)的左右子樹都為NULL時(shí)，我們就將戒子節(jié)點(diǎn)的個(gè)數(shù)加一，當(dāng)然，可以把葉子節(jié)點(diǎn)定義為一個(gè)靜態(tài)變量，這樣，每次加的都是同一個(gè)變量上。
也可以不用定義靜態(tài)的變量，因?yàn)殪o態(tài)變量會(huì)有線程的安全問(wèn)題。
size_t LeafCount()
{
return _LeafCount(_root);
}
size_t _LeafCount(BinaryTreeNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->_left==NULL && root->_right ==NULL)
{
return 1;
}
return (_LeafCount(root->_left)+_LeafCount(root->_right));
}
（二）求樹的深度
求樹的深度是一個(gè)比較有難度的問(wèn)題，因?yàn)槲覀円容^不同子樹的深度的大小，然后取大的哪一個(gè)，但是在一個(gè)遞歸程序中很難保證一個(gè)變量不會(huì)改變。在這里我們只要比較每個(gè)子問(wèn)題中的左右字?jǐn)?shù)的深度，每次返回使深度大值加一，最后的值就是樹的深度。
size_t Deepth()
{
return _Deepth(_root);
}
size_t _Deepth(BinaryTreeNode* root)
{
if (root == NULL)
{
return 0;
}
size_t leftDeep = _Deepth(root->_left)+1;
size_t rightDeep = _Deepth(root->_right)+1;
return leftDeep > rightDeep ? leftDeep: rightDeep;
} （三）求樹的節(jié)點(diǎn)的個(gè)數(shù)
這個(gè)問(wèn)題是比較容易的，我們可以用任意一種遍歷方式遍歷這棵樹，每遍歷到一個(gè)節(jié)點(diǎn)，個(gè)數(shù)就加以。
size_t Size()
{
return _Size(_root);
}
size_t _Size(BinaryTreeNode* root)
{
if (root == NULL)
{
return 0;
}
return _Size(root->_left) + _Size(root->_right) + 1;
} 另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
