八、樹(shù)（Tree）
樹(shù)，顧名思義，長(zhǎng)得像一棵樹(shù)，不過(guò)通常我們畫(huà)成一棵倒過(guò)來(lái)的樹(shù)，根在上，葉在下。不說(shuō)那么多了，圖一看就懂：
當(dāng)然了，引入了樹(shù)之后，就不得不引入樹(shù)的一些概念，這些概念我照樣盡量用圖，誰(shuí)會(huì)記那么多文字？
樹(shù)這種結(jié)構(gòu)還可以表示成下面這種方式，可見(jiàn)樹(shù)用來(lái)描述包含關(guān)系是很不錯(cuò)的，但這種包含關(guān)系不得出現(xiàn)交叉重疊區(qū)域，否則就不能用樹(shù)描述了，看圖：
面試的時(shí)候我們經(jīng)常被考到的是一種叫“二叉樹(shù)”的結(jié)構(gòu)，二叉樹(shù)當(dāng)然也是樹(shù)的一種了，它的特點(diǎn)是除了葉以外的節(jié)點(diǎn)都有兩個(gè)子，圖：
由此我們還可以推出“三叉樹(shù)”：
當(dāng)然還有“四叉樹(shù)”，“五叉樹(shù)”，“六叉樹(shù)”……但太難畫(huà)了，節(jié)點(diǎn)太多，略過(guò)。
九、樹(shù)的遍歷（Traversal）
值得再提一下的是二叉樹(shù)，因?yàn)樗_實(shí)比較特別，節(jié)點(diǎn)有兩個(gè)子，這兩個(gè)子是有左右之分的，顛倒一下左右，就是不一樣的二叉樹(shù)了，所以左右是不能隨便顛倒的。
在第三篇講到“隊(duì)”的時(shí)候，提及到了廣度優(yōu)先遍歷（Breadth-first traversal），除了廣度優(yōu)先遍歷之外，還有深度優(yōu)先遍歷（Depth-first Traversal），深度優(yōu)先遍歷又可分為：前序遍歷（Preorder Traversal），后序遍歷（Postorder Traversal）和中序遍歷（Inorder Traversal），其中中序遍歷只有對(duì)二叉樹(shù)才有意義，下圖解釋這幾種遍歷：
好了，又到代碼階段，寫(xiě)點(diǎn)代碼。我看過(guò)許多數(shù)據(jù)結(jié)構(gòu)的教材，二叉樹(shù)遍歷都是必不可少的內(nèi)容，而且我知道的全部都是用遞歸實(shí)現(xiàn)的，現(xiàn)在，我要求你不用遞歸，實(shí)現(xiàn)對(duì)二叉樹(shù)的中序遍歷。怎么辦？我給個(gè)提示：廣度優(yōu)先遍歷時(shí)候我們用了隊(duì)，中序遍歷，我們使用*棧*。看看能不能寫(xiě)出來(lái)，我也來(lái)寫(xiě)：
#include <stdio.h>
// TreeNode
//////////////////////////////////////////////////////////////////////////
struct TreeNode
{
char m_cVal;
TreeNode* m_pLeft;
TreeNode* m_pRight;
TreeNode(char cVal);
~TreeNode();
};
TreeNode::TreeNode(char cVal)
{
m_cVal = cVal;
m_pLeft = 0;
m_pRight = 0;
}
TreeNode::~TreeNode()
{
}
//Stack
//////////////////////////////////////////////////////////////////////////
class Stack
{
public:
Stack(int iAmount = 10);
~Stack();
//return 1 means succeeded, 0 means failed.
int Pop(TreeNode* &pVal);
int Push(TreeNode* pVal);
int Top(TreeNode* &pVal);
//1 means not null, 0 means null.
int NotNull();
private:
TreeNode **m_ppData;
int m_iCount;
int m_iAmount;
};
Stack::Stack(int iAmount)
{
m_ppData = new TreeNode*[iAmount];
m_iCount = 0;
m_iAmount = iAmount;
}
Stack::~Stack()
{
delete m_ppData;
}
int Stack::Pop(TreeNode* &pVal)
{
if(m_iCount>0)
{
--m_iCount;
pVal = m_ppData[m_iCount];
return 1;
}
return 0;
}
int Stack::Push(TreeNode* pVal)
{
if(m_iCount<m_iAmount)
{
m_ppData[m_iCount] = pVal;
++m_iCount;
return 1;
}
return 0;
}
int Stack::Top(TreeNode* &pVal)
{
if(m_iCount>0 && m_iCount<=m_iAmount)
{
pVal = m_ppData[m_iCount-1];
return 1;
}
return 0;
}
int Stack::NotNull()
{
if(m_iCount!=0)
return 1;
return 0;
}
int main(int argc, char* argv[])
{
//Construct the tree.
// A
// / \
// / \
// B C
// \ / \
// D E F
// \ \
// G H
// / \
// I J
// / \
// K L
TreeNode nA('A');
TreeNode nB('B');
TreeNode nC('C');
TreeNode nD('D');
TreeNode nE('E');
TreeNode nF('F');
TreeNode nG('G');
TreeNode nH('H');
TreeNode nI('I');
TreeNode nJ('J');
TreeNode nK('K');
TreeNode nL('L');
nA.m_pLeft = &nB;
nA.m_pRight = &nC;
nB.m_pRight = &nD;
nD.m_pRight = &nG;
nC.m_pLeft = &nE;
nC.m_pRight = &nF;
nF.m_pRight = &nH;
nH.m_pLeft = &nI;
nH.m_pRight = &nJ;
nI.m_pLeft = &nK;
nI.m_pRight = &nL;
Stack st;
//Inorder traversal
TreeNode *pVal = &nA;
int iPopped = 0;
while(pVal!=0)
{
if(pVal->m_pLeft!=0 && iPopped==0)
{
st.Push(pVal);
pVal = pVal->m_pLeft;
iPopped = 0;
}
else if(pVal->m_pRight!=0)
{
printf("%c ", pVal->m_cVal);
pVal = pVal->m_pRight;
iPopped = 0;
}
else
{
printf("%c ", pVal->m_cVal);
if(0==st.Pop(pVal))
break;
iPopped = 1;
}
}
return 0;
}
代碼就那么一點(diǎn)，可第一次寫(xiě)的時(shí)候我還真覺(jué)得頗費(fèi)腦筋的。代碼中有些注釋顯示不太正常，這是因?yàn)檫@個(gè)博客的的代碼字體非等寬的緣故，拿到你的IDE下查看就正常了。
（未完待續(xù)……）