圖解數(shù)據(jù)結(jié)構(gòu)6-樹及樹的遍歷

八、樹（Tree八、樹（Tree）樹，顧名思義，長(zhǎng)得像一棵樹，不過(guò)通常我們畫成一棵倒過(guò)來(lái)的樹，根在上，葉在下。不說(shuō)樹，顧名思義，長(zhǎng)得像一棵樹，不過(guò)通常我們畫成一棵倒過(guò)來(lái)的樹，根在上，葉在下。不說(shuō)那么多了，圖一看就懂：么多文字？關(guān)系不得出現(xiàn)交叉重疊區(qū)域，否則就不能用樹描述了，看圖：面試的時(shí)候我們經(jīng)常被考到的是一種叫“二叉樹”特點(diǎn)是除了葉以外的節(jié)點(diǎn)都有兩個(gè)子，圖：由此我們還可以推出“三叉樹”：當(dāng)然還有“四叉樹”，“五叉樹”，“六叉樹”……但太難畫了，節(jié)點(diǎn)太多，略過(guò)。九、樹的遍歷（Traversal）顛倒一下左右，就是不一樣的二叉樹了，所以左右是不能隨便顛倒的。在第三篇講到“隊(duì)”的時(shí)候，提及到了廣度優(yōu)先遍歷（Breadth-firsttraversal），除了廣度優(yōu)先遍歷之外，還有深度優(yōu)先遍歷（Depth-firstTraversal），深度優(yōu)先遍歷又可分為：前序遍歷（PreorderTraversal），后序遍歷（PostorderTraversal）和中序遍歷（InorderTraversal），其中中序遍歷只有對(duì)二叉樹才有意義，下圖解釋這幾種遍歷：好了，又到代碼階段，寫點(diǎn)代碼。我看過(guò)許多數(shù)據(jù)結(jié)構(gòu)的教材，二叉樹遍歷都是必不可少的歷。怎么辦？我給個(gè)提示：廣度優(yōu)先遍歷時(shí)候我們用了隊(duì)，中序遍歷，我們使用*棧*?？纯茨懿荒軐懗鰜?lái)，我也來(lái)寫：#include<stdio.h>//TreeNode//////////////////////////////////////////////////////////////////////////structTreeNode{charm_cVal;TreeNode*m_pLeft;TreeNode*m_pRight;TreeNode(charcVal);~TreeNode();};TreeNode::TreeNode(charcVal){m_cVal=cVal;m_pLeft=0;m_pRight=0;}TreeNode::~TreeNode(){}//Stack//////////////////////////////////////////////////////////////////////////classStack{public:Stack(intiAmount=10);~Stack();//return1meanssucceeded,0Pop(TreeNode*&pVal);intPush(TreeNode*pVal);intTop(TreeNode*&pVal);//1meansnotnull,0NotNull();private:TreeNode**m_ppData;intm_iCount;intm_iAmount;};Stack::Stack(intiAmount){m_ppData=newTreeNode*[iAmount];m_iCount=0;m_iAmount=iAmount;}Stack::~Stack(){deletem_ppData;}intStack::Pop(TreeNode*&pVal){if(m_iCount>0){--m_iCount;pVal=m_ppData[m_iCount];return1;}return0;}intStack::Push(TreeNode*pVal){if(m_iCount<m_iAmount){m_ppData[m_iCount]=pVal;++m_iCount;return1;}return0;}intStack::Top(TreeNode*&pVal){if(m_iCount>0&&m_iCount<=m_iAmount){pVal=m_ppData[m_iCount-1];return1;}return0;}intStack::NotNull(){if(m_iCount!=0)return1;return0;}intmain(intargc,char*argv[]){//Constructthetree.// A// / \// / \//B C// \ /\//DE F//\\//GH///\//I J///\//K LTreeNodenA('A');TreeNodenB('B');TreeNodenC('C');TreeNodenD('D');TreeNodenE('E');TreeNodenF('F');TreeNodenG('G');TreeNodenH('H');TreeNodenI('I');TreeNodenJ('J');TreeNodenK('K');TreeNodenL('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;Stackst;//InordertraversalTreeNode*pVal=&nA;intiPopped=0;while(pVal!=0){if(pVal->m_pLeft!=0&&iPopped==0){st.Push(pVal);pVal=pVal->m_pLeft;iPopped=0;}elseif(pVal->m_pRight!=0){printf("%c",pVal->m_cVal);pVal=pVal->m_pRight;iPopped