有奖答题~【遍历二叉树系列】
NPC

出个小题目活跃下气氛~

题目描述

题目要求很简单:

用一趟遍历(包括但不限于递归),实现将二叉树中所有结点的值全部改为该二叉树中所有结点值的最小值。

传统的方法是先用一趟遍历获取最小值,再用一趟遍历将所有node的值改为这个最小值。我们这次要求完成目标,in just one pass

定义二叉树的结构为(Haskell表示,不过大家应该能看懂的,嗯):
data Tree = Leaf Int | Branch Int Tree Tree
解释:数据结构Tree可以由两种构造器构造而成,一种是Leaf,后面跟一个Int,代表叶节点,里面存储整数;另一种是Branch,后面跟一个Int和两个Tree结构(当然,每个Tree都既可以是Leaf也可以是Branch),代表值和两个分支。

样例输入输出:

[Input]
Branch 7 (Branch 4 (Leaf 5) (Leaf 3)) (Leaf (-99))
[Output]
Branch (-99) (Branch (-99) (Leaf (-99)) (Leaf (-99))) (Leaf (-99))
[Input]
Branch (-2) (Branch 7 (Leaf 3) (Leaf 5)) (Branch 2 (Leaf 4) (Branch 8 (Leaf 9) (Leaf 6)))
[Output]
Branch (-2) (Branch (-2) (Leaf (-2)) (Leaf (-2))) (Branch (-2) (Leaf (-2)) (Branch (-2) (Leaf (-2)) (Leaf (-2))))

(输入输出格式不限定,是二叉树就行,只写出来函数也行)

Bonus

用Functional Programming(如Haskell)实现:奖励价值HK$500的MacBook Coupon
用Imperative Programming (如C、Python的Non-functional approach)实现:奖励价值HK$240的iPad Coupon
两者均实现:以上两个优惠券+2年Kaspersky for Mac授权(感谢+7小朋友在不知情的情况下友情赞助~)
以上优惠券的有效期为2015年12月。仅有一张,先答先得。

Hint

(1)可以使用辅助空间,当然越少越好啦。
(2)结点的存储结构可以考虑适当修改。
(3)Circular programming

PS: 输入(Leaf 8)会变成(Leaf 8)。。我也是醉了。。

  • 1
  • Blogspace Alpha

    大手笔啊
    不给我们这些菜的解释一下什么是Circular programming吗。。

  • 0
  • NPC

    Circular programming: https://wiki.haskell.org/Circular_programming
    貌似只是Haskell里面的概念,知不知道都可以做啦~

  • 1
  • NPC

    circular programming是元循环编程吧, 自己编译/解释自己

  • 2
  • NPC

    Interesting question, but I think it rather a trick than something brilliant. In fact, spuriously, it could be done easier in the imperative approach. By imperative approach I mean, the variables are mutable, you can change the state of the variables, as a contrast to the functional one, in which you could not use set! , set-car!, set-cdr! or something equivalent.

    By imperative one, the idea is so simple to come up with, i just show how to construct the data structure. I believe the algorithm and pseudocodes are quite easy to our brilliant readers, the detail is remained to the readers:

    Idea: we could't get the minimal number of the whole tree until the one-pass recursion traverse done, so instead of change the value of every node to the minimal one, we point the value field to somewhere hold the minimal, after the entire traverse done, we change the state of that field, thus, all nodes' value point to the minimal of the tree.

    the data structure is shown as follows, the tag field is required due to the lack of algebra data type in C:

    struct tree {
      char tag;  // the day without (abstract) algebra data type.
      union {
        struct leaf {
           int *value; // how to deal with the space? alloc() then free()?
        };
        struct branch {
           int *value;
           struct tree *left;
           struct tree *right;
        }
      }
    }
    

    Now, we have to face the real challenge, because what we have is immutable data. By this I mean, which I had to emphasize, not only change the state in programming language level, but also in interpreter or compiler level. This is important, cause some language may using imperative approach to implement functional features which we should considered as cheating for this very quiz.

    I found some pieces of interesting Haskell code online [2], which is the answer to this quiz:

    data Tree = Leaf Int
              | Node Tree Tree
    
    minTree :: Tree -> Tree
    minTree t = t'
    where minTree' (Leaf n) = (n, Leaf n')
          minTree' (Node t1 t2) = let (m1, t1') = minTree' t1
                                      (m2, t2') = minTree' t2
                                  in (min m1 m2, Node t1' t2')
          (n', t') = minTree' t
    

    If you considered this in a eager evaluation approach, you may get confused about the n', it seems that we use it before we really get it! In a more intuitively way to think is that, n' appears in both sides of the functional equation, thus we have to considered the n' as some value unknown then to solve the equation. It seems that require a higher-order way such as fixed-point combinator, but in a programming language with Call-By-Name/Call-By-Need setting (lazy evaluation), value recursion seems quite possible and easy.

    I found this paper [1] may help for further study if somebody is getting into this field, but unfortunately it requires some monads background which is not an easy case for us imperative programmers.

    As a conclusion, i just show some ideas or the essence about this quiz, although I never put any actual code, i think it's enough. For somebody really want to challenge this, there may be a much more difficult one:

    How to solve this question using a functional programming language with eager evaluation settings(Call-by-value)?

    Reference

    [1] : Erkök L. Value recursion in monadic computations[D]. Oregon Health and Science University, 2002.
    [2] : http://calculist.blogspot.com/2005/07/circular-programming-in-haskell.html

    最后由DeathKing编辑
  • 0
  • NPC

    @DeathKing 格式如此严谨, 颇具学术论文风范, 这孩子没救了...

  • 0
  • NPC

    @ran 入教以后才发现,不刷几篇Paper,不敢说自己懂函数式……事实上刷完也未必见得懂……

  • 0
  • NPC

    @DeathKing 你们教主是约翰*麦卡锡吧

  • 0
  • NPC

    @DeathKing I must say, your answers are exactly what I learned in class. The idea of using a pointer in C was adopted by the lecturer to make it easier for us to understand that haskell implementation. However, since we cannot use a variable before knowing its exact value in call-by-value, I can't figure out a way to solve your more difficult problem. Maybe we have to use some trick to make the nodes work like pointers? Anyway, it would be best if you are willing to share your answer to us. BTW, you can message me if you want the coupons and licence now.
    Thanks again for your elegant answer!

  • 0
  • MSC

    一个很挫的方法,也只是为了活跃下气氛,求轻喷。

    #define ALLOC_SIZE 100
    
    typedef struct NodeBase{
    	int data;
    	NodeBase* left_node;
    	NodeBase* right_node;
    } Node;
    
    int** data_ptr;
    int data_ptr_size;
    int data_ptr_index;
    int min_data;
    
    void Iteration(Node* node)
    {
    	if (node != NULL)
    	{
    		if (data_ptr_index == data_ptr_size) 
    			data_ptr = (int**)realloc(data_ptr, sizeof(int*) * (data_ptr_index + ALLOC_SIZE));
    		data_ptr[data_ptr_index] = &node->data;
    		data_ptr_index++;
    		if (node->data < min_data) min_data = node->data;
    		Iteration(node->left_node);
    		Iteration(node->right_node);
    	}
    }
    
    void SetMin()
    {
    	for (int current_index = 0; current_index < data_ptr_index; current_index++)
    	{
    		*data_ptr[current_index] = min_data;
    	}
    }
    

    确实只用了一趟递归,但是比起 @DeathKing 的方法简直挫爆了。本来说不发了,想想既然写都写了就贡献个发帖量吧。
    @DeathKing 给的修改指针指向的地址的方法确实很巧,学习了......
    感觉有点班门弄斧......嘛随便了......

    最后由xieaoran编辑
  • 0
  • NPC

    @xieaoran 服了服了。。题目漏洞,怪我。。

  • 0
  • NPC

    @Xivid 买不起,给有需要的人吧。这种小Quiz以后可以多发点,开拓开拓思路还是挺好的。

  • 13
    帖子
  • 14190
    浏览
  • 登录后回复