Please enable JavaScript to view the comments powered by Disqus.

二叉树的遍历-无栈

  • 发布日期
  • ·
  • 修改日期
  • ·
  • 编程
  • ·
  • 次点击

一个在数据结构领域被艹了又艹的话题。本文只涉及使用指向父节点的指针parent来遍历二叉树（不包含层次遍历），并将其包装为迭代器。

UPDATE 2016/06/22: 将不使用栈的部分从原来的大文章中分离出来

UPDATE 2016/10/28: 文章名从“二叉树的遍历-迭代器”改为“二叉树的遍历-无栈”，并将使用栈的迭代器移到对应文章

直接遍历

有关约定

树节点定义如下：

1
2
3
4
5
6
struct TreeNode {
    int data;
    TreeNode *left,*right,*parent;
    
    TreeNode(int x):data(x),left(nullptr),right(nullptr),parent(nullptr) {}
};

代码中的Func是函数类，也可以用函数指针/std::function替换之。

不使用栈

由于我的迭代器中不包含栈，所以首先要讨论这种不使用栈的方法，将循环的主体提取出来就是迭代器自增的逻辑。

为了达到回溯的目的，必须给节点添加上父节点的指针，否则遍历无法进行。虽然这种方法无需额外的辅助工具，但相比使用栈的算法，由于每个节点都多了一个parent指针，额外空间就相当于变成了$O(n)$（只是相比使用栈的，实际讨论起来这是个$O(1)$的算法）。

在这一类算法中，必须要用到各种遍历前后相邻节点的关系。

前序遍历

设当前节点为node, 父节点为parent. 在访问node之后，可有如下几种去向：

  1. 向左进发；

  2. 左边已经访问过（或为空）时向右进发；

  3. 都访问过时向上回溯。

前两个都很好理解，只是第三个需要进行一番讨论。从node向上回溯时，根据前序遍历特性可以认为以node为根的子树已经遍历完毕，其父节点parent也已访问过。回溯至parent, 如果node是parent的左子树，则对parent来说是左子树已经遍历完毕了，应该向parent的右子树进发；如果node是parent的右子树，此时parent的情况与node相同，此时令node=parent, parent=parent->parent, 循环处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <class Func> void preorder(TreeNode *root,Func visit){
    while(root!=nullptr){
        visit(root->data);
        if(root->left!=nullptr)
            root=root->left;
        else if(root->right!=nullptr)
            root=root->right;
        else{
            auto parent=root->parent;
            while(parent!=nullptr){
                if(root==parent->left && parent->right!=nullptr){
                    root=parent->right;
                    break;
                } else /* if(root==parent->right) */ {
                    root=parent;
                    parent=parent->parent;
                }
            }
            if(parent==nullptr)
                root=nullptr;
        }
    }
}

中序遍历

设当前节点为node, 父节点为parent. 在访问node之后，考虑到中序遍历特点我们可以认为node的左子树已经遍历完毕。因此，node可有如下几种去向：

  1. 向右进发；

  2. 若右已经访问过（或为空），向上回溯。

回溯至parent之后，如果node是parent的左子树，对parent来说要向右进发；如果node是parent的右子树，则对parent来说左右都已访问完毕，情况同node，即可令node=parent, parent=parent->parent, 循环处理。

由于中序遍历不是直接从树的根开始，因此要找到遍历的起始节点。

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
TreeNode* inorder_first(TreeNode *root){
    if(root==nullptr)
        return nullptr;
    while(root->left!=nullptr)
        root=root->left;
    return root;
}

template <class Func> void inorder(TreeNode *root,Func visit){
    root=inorder_first(root);
    while(root!=nullptr){
        visit(root->data);
        if(root->right!=nullptr)
            root=inorder_first(root->right);
        else{
            auto parent=root->parent;
            while(parent!=nullptr){
                if(root==parent->left){
                    root=parent;
                    break;
                } /* else if(root==parent->right) */
                root=parent;
                parent=parent->parent;
            }
            if(parent==nullptr)
                root=nullptr;
        }
    }
}

后序遍历

设当前节点为node, 父节点为parent. 在访问node之后，考虑到后序遍历特点我们可以认为node的左右子树均已遍历完毕。因此，node只能向上回溯。

回溯至parent之后，如果node是parent的左子树，对parent来说接下来要遍历右子树；如果node是parent的右子树，则对parent来说左右已经访问完毕，情况同node，即可令node=parent, parent=parent->parent, 循环处理。

由于后序遍历不是直接从树的根开始，因此也要找到它起始节点。

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
TreeNode* postorder_first(TreeNode *root){
    if(root==nullptr)
        return nullptr;
    for(;;){
        if(root->left!=nullptr)
            root=root->left;
        else if(root->right!=nullptr)
            root=root->right;
        else 
            return root;
    }
}

template <class Func> void postorder(TreeNode *root,Func visit){
    root=postorder_first(root);
    while(root!=nullptr){
        visit(root->data);
        auto parent=root->parent;
        if(parent!=nullptr){
            if(root==parent->left && parent->right!=nullptr)
                root=postorder_first(parent->right);
            else /* if(root==parent->right) */
                root=parent;
        } else 
            root=nullptr;
    }
}

迭代器遍历

有关约定

迭代器有关接口声明如下：

1
2
3
4
5
6
7
8
9
10
11
12
class iterator{
    public:
        iterator(TreeNode *root); // 待实现
        iterator(const iterator &o):m_cursor(o.m_cursor) {}
        
        int& operator*() const {return m_cursor->data;}
        int* operator->() const {return &operator*();}
        iterator& operator++(); // 待实现
        iterator operator++(int) {auto i=*this; operator++(); return i;}
    private:
        TreeNode *m_cursor;
};

注意：

  1. operator++()所实现的操作是找到在遍历序列中，当前节点的下一个节点。我们应该认为当前节点已经访问过了。

  2. 在下文中，虽然三种遍历算法的迭代器都叫iterator, 但实际上是三种不同的类型。为描述简单起见我共用一个名称。

  3. 在这里operator->()是非必须的，如果使用会导致编译错误。但设计成泛型迭代器的话那么就是必须要重载的一个重要运算符了。

  4. 如果想和STL接轨，迭代器实现起来不会如此简单，还要定义一大堆类型别名，设置迭代器种类等。该迭代器由于只能自增，因此属于ForwardIterator.

具体实现

比起有栈的版本，不使用栈的版本更好拆分。我们可以认为while循环之前的部分是迭代器初始化，while循环之内除去visit的部分是一次operator++().

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
iterator::iterator(TreeNode *root):m_cursor(root) {}

iterator& iterator::operator++(){
    if(m_cursor==nullptr)
        return *this;
    if(m_cursor->left!=nullptr)
        m_cursor=m_cursor->left;
    else if(m_cursor->right!=nullptr)
        m_cursor=m_cursor->right;
    else{
        auto parent=m_cursor->parent;
        while(parent!=nullptr){
            if(parent->right==nullptr || m_cursor==parent->right){
                m_cursor=parent;
                parent=parent->parent;
            } else {
                m_cursor=parent->right;
                return *this;
            }
        }
        m_cursor=nullptr;
    }
    return *this;
}

中序遍历

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
iterator::iterator(TreeNode *root):m_cursor(root){
    if(m_cursor==nullptr)
        return;
    while(m_cursor->left!=nullptr)
        m_cursor=m_cursor->left;
}

iterator& iterator::operator++(){
    if(m_cursor==nullptr)
        return *this;
    if(m_cursor->right!=nullptr){
        m_cursor=m_cursor->right;
        while(m_cursor->left!=nullptr)
            m_cursor=m_cursor->left;
    } else {
        auto parent=m_cursor->parent;
        while(parent!=nullptr){
            if(m_cursor==parent->left){
                m_cursor=parent;
                return *this;
            }
            m_cursor=parent;
            parent=parent->parent;
        }
        m_cursor=nullptr;
    }
    return *this;
}

后序遍历

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
// 辅助用函数
TreeNode* next(TreeNode *root){
    if(root==nullptr)
        return nullptr;
    for(;;){
        if(root->left!=nullptr)
            root=root->left;
        else if(root->right!=nullptr)
            root=root->right;
        else 
            return root;
    }
}

iterator::iterator(TreeNode *root):m_cursor(next(root)) {}

iterator& iterator::operator++(){
    if(m_cursor==nullptr)
        return *this;
    auto parent=m_cursor->parent;
    if(parent!=nullptr){
        if(m_cursor==parent->left && parent->right!=nullptr)
            m_cursor=next(parent->right);
        else 
            m_cursor=parent;
    } else 
        m_cursor=nullptr;
    return *this;
}
作者:Dr. A. Clef
发布日期:2016-06-22
修改日期:2017-06-10
发布协议: BY-SA