这是一个创建于 1404 天前的主题，其中的信息可能已经有所发展或是发生改变。
学数据结构经常会听到：线性结构就是一对一，半线性结构就是一对多，非线性结构就是多对多。
树一般被认为是典型的半线性结构。
那下面这个有向图是有向树吗？
第 1 条附言 · 2020-06-15 09:08:45 +08:00
取屈婉玲版《离散数学》中对无向树的定义，连通无回路的无向图称为无向树。且这些命题是等价的：
（1）G是树
（2）G中任意两个顶点之间存在唯一的路径
（3）G中无回路且m = n - 1
（4）G是连通的且m = n - 1
（5）G是连通的且任何边均为桥
（6）G中没有回路，但在任何两个不同的顶点之间加一条新边后所得图中有唯一一个含新边的圈。
同时，屈婉玲版《离散数学》对有向树做了定义如下：
若有向图的基图是无向树，则称这个有向图为有向树。
因此，我认为，上图是一棵有向树。
二叉树中对度的确有明确规定，即除空树外每个节点至多有两个子树，除根节点外每个节点有且仅有一个前驱。但这并非树的定义。
所以树并非一定满足一对多的关系，图中的有向树实际是 Polytreee。
第 2 条附言 · 2020-06-16 18:39:45 +08:00
之所以存在这样的差异，是因为《图论》和《数据结构》两个学科对树的定义不同。《数据结构》中的树实际指有根树。有根树满足除根节点外，其余节点有且仅有一个前驱。这才有所谓“一对多”的关系。
但在《图论》和《离散数学》里，往往不会要求树一定是有根树。
特别是在和数学、信计的同学交流的时候，就不得不注意这个差异。
这意味着我们在《数据结构》中学到的树的诸多结论，在《图论》的定义下并不一定成立。
（我在学《离散数学》，《图论》，《数据结构》三门课时并未注意到这个差异，也是近期和数学系的同学讨论相关的话题，才意识到自己忽略了这样基础且重要的差异。）
但在《图论》和《离散数学》里，往往不会要求树一定是有根树。
特别是在和数学、信计的同学交流的时候，就不得不注意这个差异。
这意味着我们在《数据结构》中学到的树的诸多结论，在《图论》的定义下并不一定成立。
（我在学《离散数学》，《图论》，《数据结构》三门课时并未注意到这个差异，也是近期和数学系的同学讨论相关的话题，才意识到自己忽略了这样基础且重要的差异。）
第 3 条附言 · 2020-07-02 20:43:12 +08:00
 |
1
kizunai 2020-06-14 21:30:05 +08:00
显然不是
这是一个 DAG 图 |
 |
2
ipwx 2020-06-14 21:41:57 +08:00  1
1 、首先这句话，“线性结构就是一对一，半线性结构就是一对多，非线性结构就是多对多”，我从未在任何一本经典的数据结构和算法教材上看见过。我甚至从未见过线性结构、半线性、和非线性这种分类方法。如果你见过，请给我一个准确的数学定义。
2 、说到数学定义，树有很多数学定义方式。比如一个定义：有 N 个节点和 N-1 条边的有向连通图。你仔细揣摩一下这个定义，是不是会发现它没有歧义？它定义出来的图，一定是树；同时，树一定属于它定义出来的图。这就是正规教材会出现的定义。 3 、所以定义一个概念是不能有歧义的。你这种“线性结构”的概念，歧义太多，根本就是想怎么理解就怎么理解。你有这种困惑，恰恰是因为，它根本不是一个合格的概念。 |
|
3
ipwx 2020-06-14 21:44:35 +08:00 1
抱歉上面我说错了一点。
“有 N 个节点和 N-1 条边的有向连通图” => “有 N 个节点和 N-1 条边的连通图” 而且这个定义只能定义一棵无序树。你可以找任何一个结构能作为根的节点当做根节点，而不影响其拓扑结构。有序树不符合这个定义。 |
 |
4
RingoTC OP @ipwx
在邓俊辉的《数据结构》里，有这样的划分。  至于线性结构是一对一，半线性结构是一对多，非线性结构是多对多的说法。的确在专业的教科书上很少有这样写，不过我也找到一些资料里面是这样写的： []( https://sbimg.cn/image/0gN1U) 这种知识也出现在面试题里。 我也赞同你说的需要一个明确的数学定义。没有定义谈划分，就会出现歧义。 |
 |
5
agagega 2020-06-14 23:56:47 +08:00 via iPhone
数学上的严谨定义虽然晦涩不直观，但很准确。中学学物理的时候有些概念在一些书上就是用这类似是而非的概念表示的，其实可能适得其反。
|
 |
6
xyjincan 2020-06-15 00:27:51 +08:00 via Android
树的每个节点最多只有一个入度
|
 |
7
newtype0092 2020-06-15 00:37:50 +08:00
一片叶子只有一个梗连在枝上，你这个相当于一片叶子有两个梗分别连着两个树枝，不科学~
整棵树从根到叶子一定是不断发散分支的，这种结构叫树还是非常形象的。 |
 |
8
lithbitren 2020-06-15 05:52:14 +08:00
说是一般认为也问题不大，就是做算法题的时候经常会碰见链树图互转的情况。
比如输出所有满二叉树这种题，其实可以通过共用子树大大减少建树的开销，实质结构就变成了多入多出的图结构。 也就是一般的结构体或对象定义出来的树，只要有两棵子树指向同一个节点，就不满足理论上所谓的树定义了，但算法题的操作里也不算罕见。 |
 |
9
Cielsky 2020-06-15 06:59:51 +08:00
这是图，可以把树当成图的特殊形式
|
 |
10
sivacohan 2020-06-15 10:25:38 +08:00
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.
所以这玩意是个森林吧。 |
Select Language