一颗二叉树被构造函数（数组创建一棵树）、拷贝构造函数或者拷贝赋值函数创建以后，我们现在要对这棵树进行一些遍历操作，找出这棵树上的所有节点。

二叉树的搜索策略已经看过了，共有4种

• 前序遍历
• 中序遍历
• 后序遍历
• 层次遍历

二叉树的前序、中序和后序遍历都需要借助栈stack这种结构，而层次遍历需要借助队列queue

2.1 前序遍历

框架

框架如下

template<typename T>
void binary_tree<T>::print_pre_order(void) const {
}

遍历过程

前序遍历规则：根—>左—>右，现在根据这个规则走一遍下面这棵树

走一遍的结果为：a -> b -> d -> e -> f -> c

代码

实现上述过程代码为

template<typename T>
void binary_tree<T>::print_pre_order(void) const {
    stack<tree_node*> node_stack;
    if (root_ != 0) {
        node_stack.push(root_);
        tree_node* sorc_node;
        while(!node_stack.empty()) {
            sorc_node = node_stack.top();
            node_stack.pop();
            if (sorc_node->rchild != 0) {
                node_stack.push(sorc_node->rchild);
            }
            if (sorc_node->lchild != 0) {
                node_stack.push(sorc_node->lchild);
            }
        }  // while
    }    // if
}

上面的这几行代码虽然很少，但是非常重要，即便是以后在图结构中要使用到的深度优先搜索（DFS）以及其各种衍化体型都是在这个遍历过程的基础上进行改变的，建议好好理解这个实现的过程

2.2 中序遍历

框架

框架如下

template <typename T>
void binary_tree<T>::print_in_order(void) const {
}

遍历过程

中序遍历规则：左—>根—>右，现在根据这个规则走一遍下面这棵树

走一遍的结果为：d -> e -> b -> f -> a -> c

代码

相比于前序遍历，中序遍历的实现就复杂了一点，因为它不是从根节点开始的，而是从左子节点开始的，所以需要先遍历根节点的所有左子节点

template <typename T>
void binary_tree<T>::print_in_order(void) const {
    stack<tree_node*> node_stack;
    tree_node* lft_node = root_, tmp_node;
    while (lft_node->lchild != 0) {            // 遍历找左子节点
        node_stack.push(lft_node);
        lft_node = lft_node->lchild;
    }
    if (!node_stack.empty()) {
        tmp_node = node_stack.top();
        node_stack.pop();
        if (tmp_node->rchild != 0) {
            node_stack.push(tmp_node->rchild);
            tmp_node = node_stack.top();
            node_stack.pop();
            while (tmp_node->lchild != 0) {        // 注意：遍历找右节点的左子节点
                node_stack.push(tmp_node);
                tmp_node = tmp_node->lchild;
            }
        }  
        else {
            cout << tmp_node->data << endl;            // 访问的元素
        }
    } 
}

上面有一个需要注意的事情，就是该二叉树的右节点有左子节点的情况下，需要做遍历将左子节点放进去，这个过程就是之前的遍历找左子节点的过程。

2.3 后序遍历

框架

框架如下

template <typename T>
void binary_tree<T>::print_post_order(void) const {
}

遍历过程

后序遍历规则：左—>右—>根，现在根据这个规则走一遍下面这棵树

走一遍的结果为：e -> d -> f -> b -> c -> a

代码

后序遍历的规则比较好玩：对每个根节点判断是否有左子节点，如果有的话

template<typename T>
void binary_tree<T>::print_post_order(void) const {
    // 后续序序遍历输出一颗树的全部结点值2,3,1
    // 广度优先遍历
    cout << "print_post_order : ";
    typedef pair<tree_node*, bool> multinode;
    stack<multinode> tempstack;
    if (root_) {
        tempstack.push(make_pair(root_, false));
    }
    while (!tempstack.empty()) {
        multinode m = tempstack.top(); tempstack.pop();
        if (m.first->lchild == NULL && m.first->rchild == NULL) {// 叶子节点直接输出
            cout << m.first->data << " ";
        }
        else if (m.second == true) {                // 所有孩子都遍历完了才会到这一步
            cout << m.first->data << " ";
        }
        else {                                        // 非终结点，并且孩子还没遍历完。
            m.second = true; tempstack.push(m);
            if (m.first->rchild != NULL) {
                tempstack.push(make_pair(m.first->rchild, false));
            }
            if (m.first->lchild != NULL) {
                tempstack.push(make_pair(m.first->lchild, false));
            }
        }
    }
    cout << endl;
}

因为栈是先进后出的，所以会对之前的每个节点进行判断是否有右子节点，左->右 ->根的顺序其根必然有右节点，此时就会陷入死循环。所以需要一个外力帮助它打破这个死循环。

这个外力就是typedef pair<tree_node*, bool> multinode;中的bool类型的判断值，用来判断这个根是否可以被弹出。