二叉树的中序遍历

马谦马谦马谦

615
文章

17
评论

2020年2月9日11:20:23数据结构和算法评论306字数 348阅读1分9秒阅读模式

一、中序遍历

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

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

二叉树的中序遍历

二、非递归实现

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

实现原理：

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

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

代码描述：

/*
 * 中序遍历的非递归实现
 * @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_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);
}