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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2029 天前的主题，其中的信息可能已经有所发展或是发生改变。

我的意思是
二叉树这种特殊的数据结构,决定了它天然的递归性,所以很多问题能用递归解决,其原因在于二叉树的构造

二叉树

递归性

构造

巧合

6 条回复 • 2019-05-03 14:48:14 +08:00

ywcjxf1515

2019-05-03 14:05:08 +08:00 via iPad

也能用递归来遍历数组元素。大概是一个数据结构，由多个同类元素组成，都能用递归吧。处理多个相似的子问题，用递归？

Mutoo

2019-05-03 14:08:58 +08:00

1 ）任何图结构都可以用递归来解。
2 ）树是图的一种特例。
3 ）二权树是树的一种特例。

另外，递归和迭代算法可以相互传化。
不是什么巧合，只是不同的工具而已。
递归的概念来自数学。

carlclone

2019-05-03 14:12:21 +08:00 via Android

因为每个子节点都可以看成是一颗子树，递归常用于缩小问题规模，将问题分解为多个子问题

tlriavsihd

2019-05-03 14:18:55 +08:00

@ywcjxf1515
@carlclone
@Mutoo
学习了

aijam

2019-05-03 14:21:17 +08:00

lz 的直觉是对的。Nat/List/Tree 本身都是递归定义的，很多问题用递归就很自然。稍微写过一点 Haskell 应该会有体会。

geelaw

2019-05-03 14:48:14 +08:00

先定义什么叫“巧合”。

我个人更喜欢管那种定义方式叫归纳定义：一个 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 是自然数。

另外二叉树和通常的树也不太一样，通常的树不一定有根，且即使有根，也通常没有子树顺序的区别；二叉树总是有根，且总是有左右的分别。