图解数据结构6-树及树的遍历

八、树（Tree八、树（Tree）树，顾名思义，长得像一棵树，不过通常我们画成一棵倒过来的树，根在上，叶在下。不说树，顾名思义，长得像一棵树，不过通常我们画成一棵倒过来的树，根在上，叶在下。不说那么多了，图一看就懂：么多文字？关系不得出现交叉重叠区域，否则就不能用树描述了，看图：面试的时候我们经常被考到的是一种叫“二叉树”特点是除了叶以外的节点都有两个子，图：由此我们还可以推出“三叉树”：当然还有“四叉树”，“五叉树”，“六叉树”……但太难画了，节点太多，略过。九、树的遍历（Traversal）颠倒一下左右，就是不一样的二叉树了，所以左右是不能随便颠倒的。在第三篇讲到“队”的时候，提及到了广度优先遍历（Breadth-firsttraversal），除了广度优先遍历之外，还有深度优先遍历（Depth-firstTraversal），深度优先遍历又可分为：前序遍历（PreorderTraversal），后序遍历（PostorderTraversal）和中序遍历（InorderTraversal），其中中序遍历只有对二叉树才有意义，下图解释这几种遍历：好了，又到代码阶段，写点代码。我看过许多数据结构的教材，二叉树遍历都是必不可少的历。怎么办？我给个提示：广度优先遍历时候我们用了队，中序遍历，我们使用*栈*。看看能不能写出来，我也来写：#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