树一定满足一对多的关系吗？

[RingoTC]

学数据结构经常会听到：线性结构就是一对一，半线性结构就是一对多，非线性结构就是多对多。

树一般被认为是典型的半线性结构。

那下面这个有向图是有向树吗？

[kizunai]

显然不是
这是一个 DAG 图

[ipwx]

1 、首先这句话，“线性结构就是一对一，半线性结构就是一对多，非线性结构就是多对多”，我从未在任何一本经典的数据结构和算法教材上看见过。我甚至从未见过线性结构、半线性、和非线性这种分类方法。如果你见过，请给我一个准确的数学定义。
2 、说到数学定义，树有很多数学定义方式。比如一个定义：有 N 个节点和 N-1 条边的有向连通图。你仔细揣摩一下这个定义，是不是会发现它没有歧义？它定义出来的图，一定是树；同时，树一定属于它定义出来的图。这就是正规教材会出现的定义。
3 、所以定义一个概念是不能有歧义的。你这种“线性结构”的概念，歧义太多，根本就是想怎么理解就怎么理解。你有这种困惑，恰恰是因为，它根本不是一个合格的概念。

[ipwx]

抱歉上面我说错了一点。

“有 N 个节点和 N-1 条边的有向连通图” => “有 N 个节点和 N-1 条边的连通图”

而且这个定义只能定义一棵无序树。你可以找任何一个结构能作为根的节点当做根节点，而不影响其拓扑结构。有序树不符合这个定义。

[RingoTC]

@ipwx
在邓俊辉的《数据结构》里，有这样的划分。

至于线性结构是一对一，半线性结构是一对多，非线性结构是多对多的说法。的确在专业的教科书上很少有这样写，不过我也找到一些资料里面是这样写的：

[]( https://sbimg.cn/image/0gN1U)

这种知识也出现在面试题里。
我也赞同你说的需要一个明确的数学定义。没有定义谈划分，就会出现歧义。

[agagega]

数学上的严谨定义虽然晦涩不直观，但很准确。中学学物理的时候有些概念在一些书上就是用这类似是而非的概念表示的，其实可能适得其反。

[xyjincan]

树的每个节点最多只有一个入度

[newtype0092]

一片叶子只有一个梗连在枝上，你这个相当于一片叶子有两个梗分别连着两个树枝，不科学~
整棵树从根到叶子一定是不断发散分支的，这种结构叫树还是非常形象的。

[lithbitren]

说是一般认为也问题不大，就是做算法题的时候经常会碰见链树图互转的情况。
比如输出所有满二叉树这种题，其实可以通过共用子树大大减少建树的开销，实质结构就变成了多入多出的图结构。
也就是一般的结构体或对象定义出来的树，只要有两棵子树指向同一个节点，就不满足理论上所谓的树定义了，但算法题的操作里也不算罕见。

[Cielsky]

这是图，可以把树当成图的特殊形式

[sivacohan]

A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic.

所以这玩意是个森林吧。

[RingoTC]

@sivacohan 但我给的图是一个特殊的 polytree，连通的 polytree

[RingoTC]

@sivacohan 啊这，你这不是 polyforest 吗

[sivacohan]

@RingoTC 你是对的。
你给出的图按照定义来说是树。
我一直以为树必须有根，刚翻了定义才发现不是。