木鸟杂记

分布式系统，数据库，存储

数据结构与算法（一）：二叉树的非递归遍历

发表于 分类于

概述

最近在琢磨关于树的非递归遍历的一些思路和对应的实现，写在这里，聊以备忘。

作者：木鸟杂记 https://www.qtmuniao.com, 转载请注明出处

直接迭代写法

基本思路是，一路往左走，撞了南墙（碰到NULL）就回头；回头摆到右（子树的根），接着往左走（循环）。

基本代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
void traversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* current = root;

    while (!s.empty() || current) {
        if (current) {
            s.push(current); //(1)
            current = current->left;
        } else {
            current = s.top()->right; // (3)
            s.pop(); // if we pop the node, then we do not have (5)
        }
    }
}

对应的完整遍历路径如下：

1
2
3
4
      (1) root (5?)
         / (3)  \
        /        \
(2)l-subtree   (4)r-subtree

对于某个节点root来说，有三次访问机会：

  1. 从父亲节点过来(1)
  2. 访问完左子树后回来(3)
  3. 访问完右子树后回来(5)

对应的，按照二叉树遍历的定义，

  1. 如果在(1)访问节点，就是前序遍历：先根(1)，然后左子树(2)，最后右子树(4)。
  2. 如果在(3)访问节点，就是中序遍历：先左子树(2)，然后根(3)，最后右子树(4)。
  3. 如果在(5)访问节点，就是后序遍历：先左子树(2)，然后右子树(4)，最后根(5)。

由于访问完左子树需要继续访问右子树，故需要保存root的指针，即stack在这里的作用。随着访问的深入，stack不断入栈节点，最大长度即为树的深度。这里需要着重说明的是，随着访问左子树归来，将会不断的退栈，因为在获得右子树指针后，已经不需要再保存root的指针了。因此如果不做特殊处理，步骤(5)是没有的。

所以对于二叉树前序遍历和中序遍历的非递归代码，可以直接给出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// preorder traversal:
void preorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* current = root;

    while (!s.empty() || current) {
        while (current) {
            s.push(current); 
            cout << current->val << endl;//(1)
            current = current->left;
        }

        current = s.top()->right; 
        s.pop();
    }

    return ans;
}

// inorder traversal:
void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* current = root;

    while (!s.empty() || current) {
        while (current) {
            s.push(current);
            current = current->left;
        }

        current = s.top()->right; 
        cout << s.top()->val << endl;//(3)
        s.pop();
    }
}

对于后序遍历的代码，会稍微复杂一点，所需要做的改动主要为：不能在第二次访问（即图中(3)）后退栈，而需要在阶段(5)退栈。这就牵扯出如何判断阶段(5)的问题。这里我的做法是引入一个prev指针，标记访问序列中前一个二叉树节点，如果root->right即为prev，或者root->right为NULL，就可以判断已经从右子树访问返回，即为阶段(5)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void postorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* current = root, *prev = NULL;

    while (current || !s.empty()) {
        while (current) {
            s.push(current);
            current = current->left;
        }

        TreeNode* now = s.top();
        if (now->right == NULL || now->right == prev) {
            // stage (5)
            cout << now->val;
            prev = now; // update the prev
            s.pop();
            current = NULL; // let the stack keep popping
        } else {
            // stage (4)
            current = now->right;
        }
    }
}

递归翻译写法

我们知道，可以用栈来模拟函数调用，或者说函数调用本来就是函数栈帧的入栈和退栈。由于二叉树遍历足够简单，也让我们的模拟变的相对容易实现。

比如，对于先序遍历，由于栈会使访问反序，因此先压入右子树。

1
2
3
4
5
6
7
8
9
10
11
12
void preorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    if (root) s.push(root);
    while (!s.empty()) {
        TreeNode* now = s.top();
        cout << now->val;
        s.pop();

        if (now->right) s.push(now->right);
        if (now->left) s.push(now->left);
    }
}

如果先压入左子树呢，就成了逆后序遍历，这样只需要再加一个栈，就能得到后序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
void inversePostorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    if (root) s.push(root);
    while (!s.empty()) {
        TreeNode* now = s.top();
        cout << now->val;
        s.pop();

        if (now->left) s.push(now->left);
        if (now->right) s.push(now->right);
    }
}

Morris中序遍历

以上遍历方法，不论递归还是非递归，其额外的空间复杂度都为O(h)即O(lgn)，因为栈开销最大为树的深度。那么有没有一种不借助额外空间的方法来实现树的遍历呢？聪明的你可能会想到线索二叉树，Bingo！这就是Morris中序遍历。

闲话少说，先上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void inorderTraversal(TreeNode* root) {
    TreeNode* current = root;
    while (current != NULL) {
        if (current->left == NULL) {
            cout << current->val;
            current = current->right;
        } else {
            TreeNode* prev = current->left;
            while (prev->right != NULL && prev->right != current) {
                prev = prev->right;
            }

            if (prev->right == NULL) {
                prev->right = current;
                current = current->left;
            } else if (prev->right == current) {
                cout << current->val;
                current = current->right;
                prev->right = NULL;
            }
        }
    }
}

基本思路是：

1
2
3
4
5
6
7
8
9
1. Initialize current as root 
2. While current is not NULL
   If current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as right child of the rightmost node in current's left subtree
      b) Go to this left child, i.e., current = current->left

好吧，其实这就是伪代码，出处见这里。核心要点就是，当我们一头扎向南墙时，为了能无痛返回，需要在南墙打个洞，通回原路，并且过了洞之后将洞补上。但是打洞是需要时间的，这就是典型的用时间换空间–每次都得在找左孩子最右边那个元素的时候多浪费点时间。

小结

使用栈进行二叉树遍历的本质是：利用栈保存访问时路径（即从根节点到当前节点的路径），这样就可以在左子树无法前进时，进行回溯，去访问右子树。

我是青藤木鸟，一个喜欢摄影、专注大规模数据系统的程序员，欢迎关注我的公众号：“木鸟杂记”，有更多的分布式系统、存储和数据库相关的文章，欢迎关注。 关注公众号后，回复“资料”可以获取我总结一份分布式数据库学习资料。 回复“优惠券”可以获取我的大规模数据系统付费专栏《系统日知录》的八折优惠券。

我们还有相关的分布式系统和数据库的群，可以添加我的微信号：qtmuniao，我拉你入群。加我时记得备注：“分布式系统群”。 另外，如果你不想加群，还有一个分布式系统和数据库的论坛（点这里），欢迎来玩耍。

wx-distributed-system-s.jpg

不妨一读