V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
tlriavsihd
V2EX  ›  问与答

二叉树能用递归来解是因为巧合吗?

  •  
  •   tlriavsihd · 2019-05-03 13:51:45 +08:00 · 2032 次点击
    这是一个创建于 1120 天前的主题,其中的信息可能已经有所发展或是发生改变。
    我的意思是
    二叉树这种特殊的数据结构,决定了它天然的递归性,所以很多问题能用递归解决,其原因在于二叉树的构造
    6 条回复    2019-05-03 14:48:14 +08:00
    ywcjxf1515
        1
    ywcjxf1515  
       2019-05-03 14:05:08 +08:00 via iPad   ❤️ 1
    也能用递归来遍历数组元素。大概是一个数据结构,由多个同类元素组成,都能用递归吧。处理多个相似的子问题,用递归?
    Mutoo
        2
    Mutoo  
       2019-05-03 14:08:58 +08:00   ❤️ 5
    1 )任何图结构都可以用递归来解。
    2 )树是图的一种特例。
    3 )二权树是树的一种特例。

    另外,递归和迭代算法可以相互传化。
    不是什么巧合,只是不同的工具而已。
    递归的概念来自数学。
    carlclone
        3
    carlclone  
       2019-05-03 14:12:21 +08:00 via Android   ❤️ 1
    因为每个子节点都可以看成是一颗子树,递归常用于缩小问题规模,将问题分解为多个子问题
    tlriavsihd
        4
    tlriavsihd  
    OP
       2019-05-03 14:18:55 +08:00
    aijam
        5
    aijam  
       2019-05-03 14:21:17 +08:00   ❤️ 1
    lz 的直觉是对的。Nat/List/Tree 本身都是递归定义的,很多问题用递归就很自然。稍微写过一点 Haskell 应该会有体会。
    geelaw
        6
    geelaw  
       2019-05-03 14:48:14 +08:00   ❤️ 2
    先定义什么叫“巧合”。

    我个人更喜欢管那种定义方式叫归纳定义:一个 0-二叉树是 A,一个 1-二叉树是 B,且满足 A 不等于 (B,B) 且 B 不等于 (A,A) 且 A 不等于 B ;一个 k-二叉树是一个 pair (L,R),其中 L 和 R 分别是 s-、t-二叉树,其中 s,t < k, k > 1 ;一个二叉树是一个 k-二叉树,其中 k 是自然数。

    另外二叉树和通常的树也不太一样,通常的树不一定有根,且即使有根,也通常没有子树顺序的区别;二叉树总是有根,且总是有左右的分别。
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2157 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 91ms · UTC 01:25 · PVG 09:25 · LAX 18:25 · JFK 21:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.