二叉树迭代器算法

二叉树迭代器算法

(感谢 @文艺复兴记(todd) 投递此文)

二叉树(Binary Tree)的前序、中序和后续遍历是算法和数据结构中的基本问题,基于递归的二叉树遍历算法更是递归的经典应用。

假设二叉树结点定义如下:

// C++
struct Node {
    int value;
    Node *left;
    Node *right;
}

中序递归遍历算法:

// C++
void inorder_traverse(Node *node) {
    if (NULL != node->left) {
        inorder_traverse(node->left);
    }
    do_something(node);
    if (NULL != node->right) {
        inorder_traverse(node->right);
    }
}

前序和后序遍历算法类似。

但是,仅有遍历算法是不够的,在许多应用中,我们还需要对遍历本身进行抽象。假如有一个求和的函数sum,我们希望它能应用于链表,数组,二叉树等等不同的数据结构。这时,我们可以抽象出迭代器(Iterator)的概念,通过迭代器把算法和数据结构解耦了,使得通用算法能应用于不同类型的数据结构。我们可以把sum函数定义为:

int sum(Iterator it)

链表作为一种线性结构,它的迭代器实现非常简单和直观,而二叉树的迭代器实现则不那么容易,我们不能直接将递归遍历转换为迭代器。究其原因,这是因为二叉树递归遍历过程是编译器在调用栈上自动进行的,程序员对这个过程缺乏足够的控制。既然如此,那么我们如果可以自己来控制整个调用栈的进栈和出栈不是就达到控制的目的了吗?我们先来看看二叉树遍历的非递归算法:

// C++
void inorder_traverse_nonrecursive(Node *node) {
    Stack stack;
    do {
        // node代表当前准备处理的子树,层层向下把左孩子压栈,对应递归算法的左子树递归
        while (NULL != node) {
            stack.push(node);
            node = node->left;
        }
        do {
            Node *top = stack.top();
            stack.pop(); //弹出栈顶,对应递归算法的函数返回
            do_something(top);
            if (NULL != top->right) {
                node = top->right; //将当前子树置为刚刚遍历过的结点的右孩子,对应递归算法的右子树递归
                break;
            }
        }
        while (!stack.empty());
    }
    while (!stack.empty());
}

通过基于栈的非递归算法我们获得了对于遍历过程的控制,下面我们考虑如何将其封装为迭代器呢? 这里关键在于理解遍历的过程是由栈的状态来表示的,所以显然迭代器内部应该包含一个栈结构,每次迭代的过程就是对栈的操作。假设迭代器的接口为:

// C++
class Iterator {
    public:
        virtual Node* next() = 0;
};

下面是一个二叉树中序遍历迭代器的实现:

//C++
class InorderIterator : public Iterator {
    public:
        InorderIterator(Node *node) {
            Node *current = node;
            while (NULL != current) {
                mStack.push(current);
                current = current->left;
            }
        }
        virtual Node* next() {
            if (mStack.empty()) {
                return NULL;
            }
            Node *top = mStack.top();
            mStack.pop();
            if (NULL != top->right) {
                Node *current = top->right;
                while (NULL != current) {
                    mStack.push(current);
                    current = current->left;
                }
            }
            return top;
         }
    private:
        std::stack<Node*> mStack;
};

下面我们再来考察一下这个迭代器实现的时间和空间复杂度。很显然,由于栈中最多需要保存所有的结点,所以其空间复杂度是O(n)的。那么时间复杂度呢?一次next()调用也最多会进行n次栈操作,而整个遍历过程需要调用n次next(),那么是不是整个迭代器的时间复杂度就是O(n^2)呢?答案是否定的!因为每个结点只会进栈和出栈一次,所以整个迭代过程的时间复杂度依然为O(n)。其实,这和递归遍历的时空复杂度完全一样。

除了上面显式利用栈控制代码执行顺序外,在支持yield语义的语言(C#, Python等)中,还有更为直接的做法。下面基于yield的二叉树中序遍历的Python实现:

// Python
def inorder(t):
    if t:
        for x in inorder(t.left):
            yield x
        yield t.label
        for x in inorder(t.right):
            yield x

yield与return区别的一种通俗解释是yield返回时系统会保留函数调用的状态,下次该函数被调用时会接着从上次的执行点继续执行,这是一种与栈语义所完全不同的流程控制语义。我们知道Python的解释器是C写的,但是C并不支持yield语义,那么解释器是如何做到对yield的支持的呢? 有了上面把递归遍历变换为迭代遍历的经验,相信你已经猜到Python解释器一定是对yield代码进行了某种变换。如果你已经能够实现递归变非递归,不妨尝试一下能否写一段编译程序将yield代码变换为非yield代码。


关注CoolShell微信公众账号可以在手机端搜索文章

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——
好烂啊有点差凑合看看还不错很精彩 (16 人打了分,平均分: 4.06 )
Loading...

二叉树迭代器算法》的相关评论

  1. Python使用了”spagetti stack”。每个frame都是动态分配的,frame之间用prev指针连接。普通的调用只是创建frame,连接,跳转,返回,断开,析构frame。而“调用”generator的时候,只创建frame;send的时候连接并跳转;yield的时候返回,断开,但不析构frame;再次send时,连接旧的frame并从yield处继续。实际上,不管是call还是send,Python做的都是在新的frame上递归地调用eval,只是连接关系不同。

    这也解释了为什么一个generator不能嵌套地send两次,因为frame的prev指针是唯一的。

    Python中,generator只是一个frame,在被send时借用调用者的栈;它本身没有栈。这也就解释了为什么你必须for x in inorder(t.left): yield x,而不是直接调用inorder(t.left)并递归地yield。(相反,ruby的fiber是有栈的,但ruby更喜欢callback而不是coroutine)

    iterator里面存的信息和coroutine是一样的,只是在用Stack模拟栈,用next函数的起始地址模拟yield点。

  2. 做个优化,可以省去几个不必要的栈操作。

        do {
            while (NULL != node) {
                // 对于左子树不存在的节点不需要压栈而直接处理。
                if (!node->left) {
                    dosomething(node);
                    node = node->right;
                } else {
                    stack.push(node);
                    node = node->left;
                }
            }
            while (!stack.empty()) {
                Node *top = stack.top();
                stack.pop();
                do_something(top);
                if (NULL != top->right) {
                    node = top->right;
                    break;
                }
            }
        }
        while (!stack.empty());
    
  3. 线索树是非递归inorder遍历树的一种方法, 笼统点讲其实就是利用NULL指针指向当前node的后继(inorder序列中的下一个)或者前驱(inorder序列中的前一个), 所以中序遍历也有非stack实现的方法, 貌似这边也可以用来做通用的迭代器吧, 还请博主指点:P@Tim

  4. C++ 里边有 NULL 这种东西?还是作者在用 C 写 C++ 代码?就算是赶 C++11 的时髦用 nullptr 也好啊。

  5. 栈保存的是从根节点到某个叶节点的一条路径,所以空间复杂度不是O(n)而是O(log n)。
    前中后序遍历迭代解法是北美各大IT公司面试常考的基本题,谈不上有难度。
    用generator调戏面试官的话,万一被追问python是怎么实现generator的,基本没人能答出来吧。

  6. 皓哥,我咋记得递归是这么写的
    // C++
    void inorder_traverse(Node *node) {
    if (NULL != node) {
    inorder_traverse(node->left);
    do_something(node);
    inorder_traverse(node->right);
    }
    }
    }
    }

  7. 皓哥,我咋记得递归是这么写的
    // C++
    void inorder_traverse(Node *node) {
    if (NULL != node) {
    inorder_traverse(node->left);
    do_something(node);
    inorder_traverse(node->right);
    }

  8. 顺带提一句, 我觉得generator的实现和coroutine(非抢占式线程, 用户空间线程, 协程, fiber)很像, 即在两段代码里来回跳(比如生产者消费者模型). 非抢占式中让出调度器的原语正是yield. 而在generator中`让出`调度器, 即意味着将控制权暂时转移到调用者; 调用者在适当的时候会yield回来. 这样的好处是既实现了lazyness又不用付出过多调度开销.

    纯属臆测, 若有偏差, 概不负责…

  9. @prettykernel
    更喜欢你的做法,在函数里检查参数合法性。

    估计作者的习惯是在调用函数之前检查参数,
    这样加上assert会比较好,但还是调用次数越多,检查的代码就越多,重复劳动。

  10. 偶然看到这段代码,感觉面试的时候碰到过,但是越看感觉越不大对,貌似是错的啊,感觉应该是下面这样的,请各位指正
    do
    {
    while(0 != node)
    {
    mStack.push(node);
    node = node->left;
    }
    do
    {
    Node *top = mStack.top();
    mStack.pop();
    Printv(top);
    if(0!=top->right)
    {
    node = top->right;
    break;
    }
    }while(!mStack.empty());

    }while(!mStack.empty() || node!=0);

  11. 看见标题立马就想到了python的yield生成器
    相比C/C++,现在的语言越来越强调高阶抽象了。。

  12. 第一个“二叉树遍历的非递归算法:”的最后一个 “while (!stack.empty()); ”判断条件不行啊,因为 栈为空并不表示就要退出,这时如果 node 指向了有效了 上一个node.right 的话,是需要继续的。 否则的话,如果 root 节点的左子树为null的情况下,那访问root节点后node指向root.right然后此时栈为空,退出…
    我试了下,改成 while (!stack.isEmpty() || node !=null ); 就可以了(Java语句)

  13. @colin
    本来我想第一时间回复“ 哭你妹啊,能不能不要这么sb的来秀优越感,最烦这种纯秀优越感毫无信息量的sb回复 ”,后来看见
    @ttt 推荐了个帖子。
    于是把结论部分摘下来告诉你,希望你以后秀优越感之前先去问问Google,不济也去问问baidu。
    1、NULL 并不是 C++ 的关键字,是一些类库中定义的一个宏,可能这个库是 Windows SDK,也可能是 C++ 为了兼容 C 而在 cstdio、cstddef 中定义的宏;
    2、新的 C++ 标准中出现了关键字 nullptr 用来给指针赋空值;
    3、写程序要看具体的环境,可能不同的厂家、公司、开发团队不同的编码规范中会有不同的要求;
    4、大师的某个推荐也不一定是最优的,需要在具体的上下文中理解,不可望文生义;

  14. 另外,有关迭代器的问题,其实如果只是希望在递归的这个过程当中完成一些操作,类似sum这样的函数,其实可以考虑另一种做法。 把文中第二段的代码里面的doSomething的部分换成一个接口指针:
    // C++
    void inorder_traverse(Node *node,Traveller* traveller) {
    if (NULL != node->left) {
    inorder_traverse(node->left);
    }
    traveller->do_something(node);
    if (NULL != node->right) {
    inorder_traverse(node->right);
    }
    }
    不使用doSomething函数,而是使用这样的一种方式,写一些实现这个特定接口的子类,就可以做到在遍历的过程中做一些特定的事情,同时记录一些状态了;

    实际上,如果是动态语言的话,把后面的部分改成闭包,就更灵活了。

  15. @colin
    你应该尊重下别人,说得有点难听了。C++从C继承而来,当然是有NULL的。但是NULL本身有很多问题,毕竟它仅仅是个宏,展开以后就是0,而0可以被理解为很多类型(int, int*等等)。C++11标准引入了nullptr来专门用来表示空指针,也就避免了相关的问题。@hollic的说得虽然不是那么准确,但建议使用nullptr是没错的。

  16. C++11之前用啥??原话是“C++ 里边有 NULL 这种东西?”, 我想知道。。在C++11之前,NULL又不是C++的东西的话,为了表示空指针,应该怎么表示?@lucifer545

  17. 澄渊 :
    偶然看到这段代码,感觉面试的时候碰到过,但是越看感觉越不大对,貌似是错的啊,感觉应该是下面这样的,请各位指正
    do
    {
    while(0 != node)
    {
    mStack.push(node);
    node = node->left;
    }
    do
    {
    Node *top = mStack.top();
    mStack.pop();
    Printv(top);
    if(0!=top->right)
    {
    node = top->right;
    break;
    }
    }while(!mStack.empty());
    }while(!mStack.empty() || node!=0);

    支持下,我也发现外层的条件不能是简单的判断栈是否为空,否则,在循环体里面根节点出栈后,循环就继续不下去了,也就是整个右子树没被访问到。

  18. @Todd
    貌似是投递本人?函数“inorder_traverse_nonrecursive”里面,15~16行的代码是有问题的,当树的结构如下:
    root->val = 1, root->left = NULL, root->right = new TreeNode(2) 的时候(表示为{1,#,2}),这段代码不能得出正确的结果,因为在访问了节点1之后,栈已经空了(节点2只是赋值给了node,但是并没有入栈),循环条件不成立,节点2就没有被访问

  19. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    // C++
    void inorder_traverse_nonrecursive(Node *node) {
    Stack stack;
    do {
    // node代表当前准备处理的子树,层层向下把左孩子压栈,对应递归算法的左子树递归
    while (NULL != node) {
    stack.push(node);
    node = node->left;
    }
    do {
    Node *top = stack.top();
    stack.pop(); //弹出栈顶,对应递归算法的函数返回
    do_something(top);
    if (NULL != top->right) {
    node = top->right; //将当前子树置为刚刚遍历过的结点的右孩子,对应递归算法的右子树递归
    break;
    }
    }
    while (!stack.empty());
    }
    while (!stack.empty() || null != node);
    }
    这样似乎更合理些!!!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*