二叉树-遍历终极版
tielimu
8年前
<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>