图解数据结构6-树和树的遍历.doc

八、树（Tree） 树，顾名思义，长得像一棵树，不过通常我们画成一棵倒过来的树，根在上，叶在下。不说那么多了，图一看就懂： 当然了，引入了树之后，就不得不引入树的一些概念，这些概念我照样尽量用图，谁会记那么多文字？ 树这种结构还可以表示成下面这种方式，可见树用来描述包含关系是很不错的，但这种包含关系不得出现交叉重叠区域，否则就不能用树描述了，看图： 面试的时候我们经常被考到的是一种叫“二叉树”的结构，二叉树当然也是树的一种了，它的特点是除了叶以外的节点都有两个子，图： 由此我们还可以推出“三叉树”： 当然还有“四叉树”，“五叉树”，“六叉树”……但太难画了，节点太多，略过。 九、树的遍历（Traversal） 值得再提一下的是二叉树，因为它确实比较特别，节点有两个子，这两个子是有左右之分的，颠倒一下左右，就是不一样的二叉树了，所以左右是不能随便颠倒的。 在第三篇讲到“队”的时候，提及到了广度优先遍历（Breadth-first traversal），除了广度优先遍历之外，还有深度优先遍历（Depth-first Traversal），深度优先遍历又可分为：前序遍历（Preorder Traversal），后序遍历（Postorder Traversal）和中序遍历（Inorder Traversal），其中中序遍历只有对二叉树才有意义，下图解释这几种遍历： 好了，又到代码阶段，写点代码。我看过许多数据结构的教材，二叉树遍历都是必不可少的内容，而且我知道的全部都是用递归实现的，现在，我要求你不用递归，实现对二叉树的中序遍历。怎么办？我给个提示：广度优先遍历时候我们用了队，中序遍历，我们使用*栈*。看看能不能写出来，我也来写： #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_iCount0)????{????????--m_iCount;????????pVal?=?m_ppData[m_iCount];????????return?1;????}????return?0;}int?Stack::Push(TreeNode*?pVal){????if(m_iCountm_iAmount)????{????????m_ppData[m_iCount]?=?pVal;????????++m_iCount;????????return?1;????}????return?0;}int?Stack::Top(TreeNod