今天看到了《算法导论（第三版）》第三部分中第十章内容，在10.4节遇到了一个题目，要求在O(n)（即上限渐进时间为线性）时间内非递归遍历二叉树，并且只能使用固定量的额外存储空间。

10.4-5 给定一个n结点的二叉树，写出一个O(n)时间的非递归过程，将该树每个节点的关键字输出。要求除该树本身的存储空间外只能使用固定量的额外存储空间，且在过程中不得修改该树，即使是暂时的修改也不允许。

部分理解需要联系上下文，比如说关键字是前文定义的一个树的结点通常具有的结构，包括一个关键字key、一个左孩子结点指针leftChild、一个右孩子结点指针rightChild以及一个父结点指针parent，另外带有可选的卫星数据。

在开始之前，给出一些基本的树结点定义，然后可以先看看二叉树常规的遍历方式。

定义

在下面的讨论中，对于树结点的定义都按照这个定义：

struct Node
{
    int key;
    Node *leftChild;
    Node *rightChild;
    Node *parent;
}

只包括主要的数据，至于可能存在的其它卫星数据之类的与讨论无关，就不包括了。
而按照上面的定义也知道，我们将假定二叉树是按照链式结构存储的，因此其迭代器类型可视为一个双向迭代器而非随机迭代器。

从定义中可以看出，每个结点还有一个指向其父结点的属性，对于根结点，该值为null。并非所有的二叉树结点定义中都需要这个属性，但是为了完成前面题目中的要求，我们这里的讨论中需要它；有这个属性，我们才可以在O(1)时间内从一个结点导航到它的父结点。

递归方式

遍历一颗二叉树，我们最容易想到的就是递归方式了。因为二叉树本身的定义也符合递归思想，而其实，一般书籍中对二叉树定义都是采用递归方式的。

二叉树T是定义在有限结点集上的结构，它

• 或者不包含任何结点，
• 或者包含三个不相交的结点集合：一个根结点，一颗称为左子树的二叉树，以及一颗称为右子树的二叉树。

因此我们在遍历的时候，也可以很容易根据定义来。下面给出二叉树先根递归方式遍历伪代码：

void visit(const Node *node)
{
    if (nullptr == node) return;

    cout << node->key;
    visit(node->leftChild);
    visit(node->rightChild);
}

首先输出根结点的值，然后分别输出其左右子树。当达到叶节点的时候，递归开始回升。

非递归&不限制存储空间

其实这也就是一般的将递归调用过程优化为迭代过程所使用的方法，一般思路就是我们使用一个栈来存储之前在递归过程中间产生的临时值，然后调整一下调用过程就行。

这里我们主要就是要将迭代过程中我们经过的根结点按照顺序依次保存起来，然后当到达叶节点的时候开始退栈。下面是非递归、使用栈作为辅助结构的二叉树先根遍历伪代码：

void print(const Node *node)
{
    std::stack<const Node*> stack;

    while (node || !stack.empty())
    {
        while (node)
        {
            stack.push(node);
            cout << node->key;
            node = node->leftChild;
        }
        node = stack.top();
        stack.pop();
        node = stack->rightChild;
    }
}

非递归过程用一个栈结构作为辅助，来存储在递归过程中函数参数中所传递的信息（函数参数通常也是通过栈传递的）。这里的基本过程也就是我们接下来讨论的基础。

非递归&常量额外存储空间

现在回到正题，按照题目要求，我们只能使用固定量的额外存储空间，因此，栈是不能使用了。但是我们在使用栈作为辅助结构的时候，其实目的是为了方便遍历过程的回退（即从孩子结点回到父结点），因此，这里我们也可以借用这个基本流程，但是需要改变的是回退方法。

没有了栈，我们就要自己想办法从孩子结点正确的回退到下一个需要被访问的祖先结点，按照先根遍历方式的话，我们就需要回退到下一个具有右孩子结点的祖先结点了。

• 如果我们当前位于一个左子树上，那么回退很简单，只需要不断的往父结点方向搜索直到找到第一个具有右子树的结点或者到达根节点的parent而结束遍历；
• 但是如果我们是从右子树遍历过来的，那么就不能简单的采用左子树回退方式了，因为那样会导致死循环（从右子树回退到其父结点，然后发现存在右子树，又遍历这个右子树），这时候我们就需要首先判断当前结点是否为其父结点的右孩子，如果是，就直接回退，一直到父结点为nullptr或者不是右孩子为止，也就是我们回退到了一个左子树路径上，这个时候，我们就可以按照左子树中回退方式，来寻找下一个合适的结点了。

上面提到的是回退，而向下的过程则很简单了，就是按照先序遍历顺序，对每个节点都沿着其左子树一直遍历到底即可。

按照上面的分析，可以写出代码：

void print(Node *p)
{
    while (p)
    {
        while (p->leftChild)
        {
            cout << p->key;
            p = p->leftChild;
        }
        cout << p;

        if (p.rightChild)
        {
            p = p.rightChild;
            continue;
        }

        // 到达叶节点，开始回退
        // 回退右子树路径上的结点
        while (p.parent && p.parent.rightChild == p)
        {
            p = p.parent;
        }
        // 回退左子树路径上的结点
        p = p.parent;
        while (p && !p.rightChild)
        {
            p = p.parent;
        }

        if (p) p = p.rightChild;
    }
}

上面过程中除了参数所占用的一个指针空间之外，没有使用其它额外的存储空间。而对过程的分析可以知道，在遍历过程中，我们会对所有的非叶子结点访问过两次，一次是向下遍历，一次是回退时候；而对所有的叶子结点，我们只需要访问一次，也就是输出它的信息。因此从这个非形式化的分析可以得知，上面代码中循环次数大约为3n/2，所以整个过程的时间复杂度为O(n)。

另一种思路

在这里再附加上另一种思路，更详细内容（代码）见此链接。

对于基本的遍历，我们按照下列规则进行：

• 如果我们从父结点出来，那么在访问其左孩子结点；
• 如果我们从一个左孩子结点出来，那么接下来访问那个对应的右孩子结点；
• 如果我们离开一个右孩子结点，那么接下来就将指针移到其父结点上。

而为了处理那些少于两个孩子结点的情况，当下列对应条件满足时，我们转移到相应的步骤：

• 如果一个结点只有右孩子，那么当访问完这个结点之后，接下来访问其右孩子结点；
• 如果一个结点只有左孩子，当我们访问完这个左孩子结点之后，返回其父结点；
• 如果一个结点没有孩子，返回其父结点。

注意上面所说父结点、孩子结点均是相对于当前正在被遍历的结点来说的。

只是在该页面最后附加的C代码好像有点问题，对于那个全局的额外占用的一个数组空间的使用，只有不断写入，却从没调用过那个重置方法。如果去掉那个store(key)的调用，然后在if分支中进行输出（if分支花括号之后，其它语句开始之前），也可以完成遍历。