<commit_before>---
layout: post_layout
title: ﻿二叉树的后序遍历
time: 2015年10月20日
location: 长春
pulished: true
excerpt_separator: "##"
---

在学习数据结构的过程中，二叉树的遍历是必学的，而二叉树的非递归遍历又是其中的难点之一，我在查阅书籍和浏览blog的时候，看见的方法往往是在结点上加一个标志位作为辅助，以判断根结点的左右子树是否均遍历过，而且过程比较繁琐。
## 利用双栈来实现后根遍历
现在我们换一种思路，当我们用递归实现后序遍历的时候，是很简单的:
```
void PostOrder(BiTreeNode *t){
    if(t ==NULL)
        return;
    PostOrder(t->left);
    PostOrder(t->right);
    visit(t);
}
```
访问左子树->右子树->根，简单明了。
如果非递归后序遍历也采用这种思想，访问某个结点时，它的左右子树一定均访问过，那么就不需要标志位了。
```
//二叉树后根遍历
void PostOrder(BiTreeNode * t){
    stack S1,S2;
    if (t ==NULL)
        return;
    S1.push(t);
    while(!S1.isEmpty()){
        t=S1.pop();
        S2.push(t);
        if(t->left!=NULL)
            S1.push(t->left);
        if(t->right!=NULL)
            S1.push(t->right);
    }
    while(!S2.isEmpty()){
        t=S2.pop();
        visit(t);
    }
}
```
这里用栈来模拟递归。
## 如有错误和不当之处，感谢批评指出！
<commit_msg>Update 2015-10-20-二叉树的后序遍历.md<commit_after>---
layout: post_layout
title: ﻿二叉树的后序遍历
time: 2015年10月20日
location: 长春
pulished: true
excerpt_separator: "##"
---

在学习数据结构的过程中，二叉树的遍历是必学的，而二叉树的非递归遍历又是其中的难点之一，我在查阅书籍和浏览blog的时候，看见的方法往往是在结点上加一个标志位作为辅助，以判断根结点的左右子树是否均遍历过，而且过程比较繁琐。
## 利用双栈来实现后根遍历
现在我们换一种思路，当我们用递归实现后序遍历的时候，是很简单的:
```c++
void PostOrder(BiTreeNode *t){
    if(t ==NULL)
        return;
    PostOrder(t->left);
    PostOrder(t->right);
    visit(t);
}
```
访问左子树->右子树->根，简单明了。
如果非递归后序遍历也采用这种思想，访问某个结点时，它的左右子树一定均访问过，那么就不需要标志位了。
```c++
//二叉树后根遍历
void PostOrder(BiTreeNode * t){
    stack S1,S2;
    if (t ==NULL)
        return;
    S1.push(t);
    while(!S1.isEmpty()){
        t=S1.pop();
        S2.push(t);
        if(t->left!=NULL)
            S1.push(t->left);
        if(t->right!=NULL)
            S1.push(t->right);
    }
    while(!S2.isEmpty()){
        t=S2.pop();
        visit(t);
    }
}
```
这里用栈来模拟递归。
## 如有错误和不当之处，感谢批评指出！

{'fraction_non_alphanumeric': 0.17367853290183388, 'fraction_numerical': 0.023732470334412083, 'mean_word_length': 3.1779279279279278, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2002722', 'n_tokens_mistral': 1109, 'n_tokens_neox': 1248, 'n_words': 101}