一、中序遍历

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

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

二、非递归实现

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

实现原理:

  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);
}
最后修改:2020 年 02 月 09 日
喜欢就给我点赞吧