<p>对于二叉树的遍历，最熟悉的就是递归遍历了，对二叉树的非递归遍历大致知道一些，但是不太熟悉，尤其是后续非递归遍历的实现，一直比较懵逼，于是上网查询了一下，果然大神无处不在，那个后序遍历的双栈法，简直让人拍案叫绝，下面总结下。</p>    <h3>1、先序遍历</h3>    <p>先序遍历即顺序为：根节点->左节点->右节点</p>    <p>递归版：</p>    <pre>  <code class="language-cpp">void PreOrderTraverse(BTree T)  {        if (T != NULL)        {            cout << T->val;            PreOrderTraverse(T->left);             PreOrderTraverse(T->right);        }  }</code></pre>    <p>非递归版：</p>    <p>根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问完其左子树后，再访问它的右子树。因此其处理过程如下：</p>    <p>对于任一结点P：</p>    <p>1)访问结点P，并将结点P入栈;</p>    <p>2)判断结点P的左孩子是否为空，若不为空，则将P的左孩子置为当前的结点P;若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1)</p>    <p>3)直到P为NULL并且栈为空，则遍历结束。</p>    <p>代码如下：</p>    <pre>  <code class="language-cpp">void PreOrderTraverse(BTree T)  {      std::stack<BTree> S;      while(T||!S.empty())      {          while(T)          {              S.push(T);              cout<<T->val;              T=T->left;          }          if(!S.empty())          {              T=S.top();              S.pop();              T=T->right;          }             }  }</code></pre>    <p>上面那个递归版是常规版，这个我觉得更好，思路是这样的，节点的右左节点分别入栈，根绝栈的“先进后出”特性，那么先输出的必然是左节点。这个方法代码简洁，思路独特。</p>    <pre>  <code class="language-cpp">void PreOrderTraverse(BTree T)     //先序遍历的非递归        {          if(!T)                return ;              stack<BiTree> s;          s.push(T);            while(!s.empty())          {              BiTree temp = s.top();              cout<<temp->data<<" ";              s.pop();              if(temp->rchild)                  s.push(temp->rchild);              if(temp->lchild)                  s.push(temp->lchild);          }      }</code></pre>    <h3>2、中序遍历</h3>    <p>中序遍历的顺序是：左节点、根节点、右节点</p>    <p>递归版：</p>    <pre>  <code class="language-cpp">void MidOrderTraaerse(BTree T)    {      if(T!=NULL)      {          MidOrderTraverse(T->left);          cout<<T->val;          MideOrderTraverse(T->right);      }  }</code></pre>    <p>非递归版：</p>    <p>根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点输出节点值，按相同的规则访问其右子树。</p>    <p>因此其处理过程如下：</p>    <p>对于任一结点P，</p>    <p>1)若节点p不为空，则将P入栈并将P的左孩子置为当前的P，然后对P再进行相同的处理；</p>    <p>2)若访问到左孩子为空后，则取栈顶元素并进行出栈操作，输出该栈顶结点值，然后将当前的P置为栈顶结点的右孩子；</p>    <p>3)直到P为NULL并且栈为空则遍历结束</p>    <p>代码如下：</p>    <pre>  <code class="language-cpp">void MidOrderTraverse(BTree T)    {      std::stack<BTree> S;      while(T||!S.empty())      {          while(T)          {              S.push(T);              T=T->eft;          }          T=S.top();          cout<<T->val;          S.pop();          T=T->ight;      }  }</code></pre>    <h3>3、后序遍历</h3>    <p>后序遍历的顺序是：左节点、右节点、根节点</p>    <p>递归版：</p>    <pre>  <code class="language-cpp">void BackOrderTraverse(BTree T)  {      if(T!=NULL)      {          BackOrderTraverse(T->left);          BackOrderTraverse(T->right);          cout<<T->val;      }  }</code></pre>    <p>非递归版：</p>    <p>1）版本1：</p>    <pre>  <code class="language-cpp">void PostOrder_Nonrecursive1(BTree T)  // 后序遍历的非递归        {            stack<BiTree> S;            BiTree curr = T ;           // 指向当前要检查的节点          BiTree previsited = NULL;    // 指向前一个被访问的节点          while(curr != NULL || !S.empty())  // 栈空时结束            {                while(curr != NULL)            // 一直向左走直到为空              {                    S.push(curr);                    curr = curr->lchild;                }                curr = S.top();              // 当前节点的右孩子如果为空或者已经被访问，则访问当前节点              if(curr->rchild == NULL || curr->rchild == previsited)                {                    cout<<curr->data<<"  ";                    previsited = curr;                    S.pop();                    curr = NULL;                }                else                  curr = curr->rchild;      // 否则访问右孩子          }        }</code></pre>    <p>2）版本2：</p>    <p>采用双栈法，这个真是神来之笔，对于想出这个办法的人，真是佩服的五体投地。为了解释原理，的看个实际例子，如下。</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/3ef649dadaa624f84df3140ba9eee393.jpg"></p>    <p>对于上面上面的二叉树，对树先左后右的将各个节点逐个放到栈1中,然后将栈1元素放到栈2中，过程如下：</p>    <p>栈1：A</p>    <p>栈1：空 | 栈2： A</p>    <p>栈1：B C -> B | 栈2：A C</p>    <p>栈1：B F G ->B F | 栈2：A C G</p>    <p>栈1：B F -> B | 栈2：A C G F</p>    <p>栈1：B -> D E | 栈2：A C G F B</p>    <p>栈1：D E -> D | 栈2：A C G F B E</p>    <p>栈1：空 | 栈2：A C G F B E D</p>    <p>最后输出栈2，就是D E B F G C A,你说6不6.</p>    <pre>  <code class="language-cpp">void PostOrder_Nonrecursive(BTree T)  // 后序遍历的非递归     双栈法      {            stack<BiTree> s1 , s2;            BiTree curr ;           // 指向当前要检查的节点          s1.push(T);          while(!s1.empty())  // 栈空时结束            {              curr = s1.top();              s1.pop();              s2.push(curr);              if(curr->lchild)                  s1.push(curr->lchild);              if(curr->rchild)                  s1.push(curr->rchild);          }          while(!s2.empty())          {              printf("%c ", s2.top()->data);              s2.pop();          }      }</code></pre>    <h3>4、深度优先遍历</h3>    <p>深度优先遍历，也就深入的遍历，沿着每一个分支直到走到最后，然后才返回来遍历剩余的节点。二叉树不同于图，图需要标记节点是否已经访问过，因为可能会存在环，而二叉树不会出现环，所以不需要标记。那么，我们只需要一个栈空间，来压栈就好了。因为深度优先遍历，遍历了根节点后，就开始遍历左子树，所以右子树肯定最后遍历。我们利用栈的性质，先将右子树压栈，然后在对左子树压栈。此时，左子树节点是在top上的，所以可以先去遍历左子树。</p>    <pre>  <code class="language-cpp">void DepthFirstTravel(BTree T)    {        stack<BTree> s;        s.push(T);        while(!s.empty())        {            T = s.top();            cout << T->data << " ";            s.pop();            if(T->rchild != NULL)            {                s.push(T->rchild);            }            if(T->lchild != NULL)            {                s.push(T->lchild);            }          }    }</code></pre>    <h3>5、广度优先遍历</h3>    <p>对于广度优先遍历二叉树，也就是按层次的去遍历。依次遍历根节点，然后是左孩子和右孩子。所以要遍历完当前节点的所有孩子，这样才是层次遍历嘛。此时我们就不能用栈这个数据结构了，因为栈只能在栈顶操作。在这里，我们需要根据左右孩子的顺序来输出，所以就是先进先出的原则，那么我们当然就想到了队列这个数据结构。可以在rear依次插入左右孩子，在front依次读取并删除左右孩子，这样就保证了层次的输出。</p>    <pre>  <code class="language-cpp">void BreadthFirstTravel(BTree T)    {        queue<BTree> q;        q.push(T);        while(!q.empty())        {            T = q.front();            cout << T->data << " ";            q.pop();            if(T->lchild != NULL)            {                q.push(T->lchild);            }            if(T->rchild != NULL)            {                q.push(T->rchild);            }        }    }</code></pre>    <h2>参考</h2>    <p>【1】 <a href="/misc/goto?guid=4959737443832084374" rel="nofollow,noindex">遍历二叉树的各种操作~~（非递归遍历）</a></p>    <p> </p>    <p>来自：http://blog.csdn.net/yixianfeng41/article/details/55228458</p>    <p> </p>