一、中序遍历

中序遍历过程：先访问左子节点，然后访问当前节点，最后访问右子节点。

以下试一次中序遍历过程：

二、非递归实现

非递归方式遍历依赖栈来实现，因为要先访问子节点，然后访问父节点，因此必须要有一个数据结构来保存已经父节点。

实现原理：

1. 每次遍历到一个节点，不访问它，先压栈，然后对左子树循环做这个操作。
2. 遍历左节点直到左节点为空时，取出栈顶元素，访问它。
3. 然后对这个栈顶元素的右节点重复执行第一个步骤。

大致的逻辑和前序遍历差不多，相对于前序遍历而言，中序遍历知识把访问节点的时机延后了一些。前序遍历可以参考二叉树的先序遍历。

代码描述：

/*
 * 中序遍历的非递归实现
 * @node 需要遍历的节点
 * @v 保存遍历结果的数组
 */
void in_order_traversal_by_stack(tree_node<T> *node, vector<T> &v) {
    stack<tree_node<T> *> st;
    tree_node<T> *p;

    p = node;
    while (p || !st.empty()) {
        // 左子树压栈
        while (p) {
            st.push(p);
            p = p->lchild;
        }

        if (!st.empty()) {
            // 取出栈顶元素
            p = st.top();
            st.pop();
            // 访问节点
            v.push_back(p->data);
            // 设置指针为右子节点
            p = p->rchild;
        }
    }
}

三、递归实现

递归实现很简单，不做详细描述：

/*
 * 中序遍历的递归实现
 * @node 需要遍历的节点
 * @v 保存遍历结果的数组
 */
void in_order_traversal(tree_node<T> *node, vector<T> &v) {
    if (node == nullptr)
        return;

    if (node->lchild)
        in_order_traversal(node->lchild, v);

    v.push_back(node->data);

    if (node->rchild)
        in_order_traversal(node->rchild, v);
}