似乎计算机数据结构中存在一个明显的“技术断层”？

别闹了，树和图到处都是，你 new 一个稍微深点儿的 object，它不是图么？

结构理解起来简单，但是编程实现+各种操作，，，

99.9%的人只要知道怎么用就行了 能看懂文档会调用 api 就 ok

链表不也可以看作是个树嘛。。

互联网风口造成的，只要知道怎么用不需要知道原理，不需要知道原理，也不需要懂多高深的技术

写代码本质上跟搬砖没有什么不一样，可以说 99.9%的人都只是在搬砖罢了

我们不是出卖技术换钱，我们是出卖时间在换钱而已

@puncsky 你没看懂我在说什么

@ipoh 很显然，我这里不是要讨论你说的这点

复杂度和维度之间的关系本来也不是线性的

可能我的理解有错误，lz 是想表达在计算机体系中存在断层？

其实链表就是一种特殊的树，树就是一种特殊的图

我的理解是，楼主指树、图这类数据结构依靠指针、内存地址，和别的连续内存的数据结构不一样，这个意思吗？

这个断层中内容可能只存在于科学家的脑海中或者草图中

没有断啊，
点，线，立方体
单一数据单元，数组，图
一维，二维，多维关系
不知道比喻的恰当不。

数组、链表、Map(table)、队列、栈不都是线性表么。。。

然后图是“二维线性表”，树是个无环图

所以并不是什么存在前置科技，的的确确就是两个维度。。

链表一对一，树一对多，图多对多，这不是很自然的递进关系么....还少啥？建议楼主不要钻到奇怪的胡同里...

小学我第一次学除法也感觉特别突兀，咋也学不会，总不能说除法和加减法有“技术断层”吧。当然也不排除是教材问题，一本好的教材认真看的话应该不会特别突兀。

链表加个叉 -> 树，
分支判断 -> 决策树 -> 树，
大部分 O(lgN)算法的执行过程差不多都是一次砍掉半拉树，
树是特殊的一种图有向无环图，图的话大概社交关系、路由算法、科学计算？等等场景用的比较多，没啥需求的话简单了解就好，没必要难为自己。

我觉得主要是在 目前的计算机体系结构上要实现（表现）这些数据结构和算法比较麻烦吧，要考虑内存寻址、计算什么的。
另外链表里其实也有（实现或操作）比较复杂一些的数据结构吧，比如双向链表 /跳表之类的。

@dilu
@alphatoad
楼主的意思应该是链表、数组算法的难度和图、树算法的难度不在一个量级上，假如说链表算法的难度是:wq，那么树算法的难度就是 100@m 了（后边这个是寄存器，要我用错了别拍我）

@CEBBCAT 我寻思楼主写得挺明白的，我当时还想夸夸楼主行文挺不错呢。至少算是矮子里面拔将军

我也是这么觉得，树怎么都搞不懂。

@boileryao 除法不就是连续减嘛

@CEBBCAT 这有啥难的……

树和图 的前置科技 不就是 链表、栈这些吗？相对于一个单个的结构， 链表的复杂程度 不也算是数量级的提升吗

绝大多数的书是什么书？就我大三的数据结构教材和算法导论来说树和图都是平滑过渡的。
估计 lz 意思是绝大多数 csdn 博客吧

链表、树和图是递进关系楼上都已经说过了，想吐槽一下楼主的逻辑倒是有两个断层：根据身边的都「感觉」得到「技术断层」的猜想；希望给出这个猜想的「数学证明」。

这样的猜想恐怕只能用「我身边的人都不觉得难」来反证了吧。（逃）

数组 链表 Map(table) ，队列，栈 这些都是线性结构
树，图都是非线性结构
从线性结构 到 非线性结构，难度自然也是非线性增加的

我感觉有点像 算术 -> 数学 的进阶过程

抱歉，我真的没听懂你在说什么。

简单的都是一维的，难的都是二维甚至更高维度的。

不在一个维度，自然对抽象能力有更高的要求，正常情况。

歪个楼，前几天出于兴趣看了 CPU 的发展史，感觉发展得更突兀，要是有业内大佬指点两句就好了

数组链表的逻辑结构和存储结构相对来说比较相似。


树、图的逻辑结构和存储结构就存在比较大的差异了。

不都是链表？
队列、栈(存在数组形式)、树、图(存在数组形式)

按照我的理解可能就是从像数组这样的连续地址空间的结构到像链表这样的非连续地址空间的结构?按照这样的话,链表和树都可以算是图的一种简单形式了

人脑内存不够，族谱，亲戚称呼也难啊

你说断层的时候我第一反应也是链表……
话说，树本身不难理解吧，毕竟也是单向的数据结构，难的话只能说难在应用上，一个二叉树衍生出那么多应用

数据结构的前置课程是离散数学，如果把离散数学学透会对数据结构的学习和理解有非常大的帮助。

树图都需要一些递归思维

树本身简单，难的是那些神奇的应用

一个维度满了，就升维啊。而且，我觉得数据结构的算法，也不算难吧，就算你理解不了或者证明不了，但是怎么去写以及会产生什么样的效果还是很清楚的。

学不明白 大学的数据结构怎么过呀

你们这样就显得发帖的很菜

不，是你不够聪明

楼主头像不错

我觉得楼主想说的“技术断层”指的是实现难度的断层。
数据结构难度可能就是像台阶一样跃迁上升，没有那么平滑。

@Cabana 没说清楚：理解不了短除 [doge]

这只能说明你还没学明白

可是，函数调用栈展开了画就是一棵树啊。。。早就隐含了。最简单的斐波那契数列的求和式子，你把递推式展开了写，不也是一棵树么？ F(n) = F(n-1)+F(n-2)

所以不是你没接触过，而是你习以为常的东西，其实早就有了。另外树是一种特殊的图，n 个节点 n-1 条边的无向连通图都是树。

另外实名反对什么线性非线性的说法，线性有严格定义的，不要乱用。
----

图在数学中早有由来，最早能追溯到欧拉（就是那个一堆定理的欧拉）。引一下维基百科：

一般认为，欧拉于 1736 年出版的关于柯尼斯堡七桥问题的论文是图论领域的第一篇文章。此问题被推广为著名的欧拉路问题，亦即一笔画问题。而此论文与范德蒙德的一篇关于骑士周游问题的文章，则是继承了莱布尼茨提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的欧拉公式与图论有密切联系，此后又被柯西等人[4][5]进一步研究推广，成了拓扑学的起源。1857 年，哈密顿发明了“环游世界游戏”（ icosian game ），与此相关的则是另一个广为人知的图论问题“哈密顿路径问题”。

西尔维斯特于 1878 年发表在《自然》上的一篇论文中首次提出“图”这一名词。

欧拉的论文发表后一个多世纪，凯莱研究了在微分学中出现的一种数学分析的特殊形式，而这最终将他引向对一种特殊的被称为“树”的图的研究。由于有机化学中有许多树状结构的分子，这些研究对于理论化学有着重要意义，尤其是其中关于具有某一特定性质的图的计数问题。除凯莱的成果外，波利亚也于 1935 至 1937 年发表了一些成果，1959 年，De Bruijn 做了一些推广。这些研究成果奠定了图的计数理论的基础。凯莱将他关于树的研究成果与当时有关化合物的研究联系起来，而图论中有一部分术语正是来源于这种将数学与化学相联系的做法。

多说一句：就像你觉得从链表到图有“断层”，我还可以觉得从微积分到泛函分析有“断层”，几何到黎曼几何有“断层”呢？但是学的多了，就能从中发现联系，理解当时的数学家到底是怎么“过渡”到更高层次的抽象上面的。

你觉得有断层，有过渡被淹没在历史中，其实只是你学得不够多罢了。

复杂度本身就没有规定说是线性的啊，楼上有人说的好，一维二维三维，其复杂度上升很快。

断层只是楼主个人感觉而已吧 我个人感觉链表到树的跨度 不如树到图的跨度大 树特别是二叉树上的问题在数学上已经研究得很透彻了 衍生了很多分治和递归的算法 而图上面很多问题到目前是没有稳定快速解法的（ NP 问题）比如旅行商 背包 最小覆盖啥的

应该没有断层，因为树也有简单的树，图也有简单的图。

现实中之所以常见到复的的树和图，是因为现实中需要解决的问题 **本身** 很复杂。

我个人理解 目前 90%应用场景是二维数据结构就可以 cover 经常用 o1 on 啥熟记
而多维数据结构面对的场景更复杂，更多面向基础基础编程，这里面不过佼佼，不常用，所以感觉陌生

就好像 400 年前 人对小数感到陌生一样

mooc 浙大的数据结构课程，往树过度的时候，用的是链表。把二维链表横过来，就是二叉树了，可以参考这个链接的 ppt 最后一页。当然理解，还是得把那节课听一听。
链接附上： https://www.icourse163.org/learn/ZJU-93001?tid=1450069451#/learn/content?type=detail&id=1214143616&cid=1217772368

估计 lz 没有发现 linked list 和 tree 的联系。

树相当多，基础的也很简单，比如二叉树，但是不实用，最终进化成了各种平衡树。

图其实跨度大点，但是数学上其实就是图论。

我是自己学的，深有体会，自学到 BST，以及大小堆，都比较直观，但是一旦到自平衡的二叉树，我就学不下去了。可能是我没有什么压力吧。图恰好跟在后面所以我也没学。

知识本身一般性的是没有断层的
个人的学识那可能有
而且一般不是断层，是个人知识的边界，类似悬崖的感觉，到此为止、没了

我说另一个看法，我觉得现在大环境里很多人死抠数据结构算法的行为有点走歪了。
计算机编程本身就是实用技术，其目的就是方便易用，给用户使用提高效率。
优秀的程序应该是利用现有资源最巧妙的，而不是算法最优的。现代计算机的硬件能力，不是特殊情况谁用的完？不够再堆硬件就行了。同时，从程序的结果来看，应该是不管白猫黑猫，只要准确稳定运行的程序就是好程序。

你需要学习离散数学，就觉得不那么突兀了，算是数据结构的先导课程。

国内大多教材基本都是直接给你结论，所以显得很突兀。
去找一些国外的好教材，好的入门级的教材都会给你一个非常好的过渡，下一节的内容是慢慢引出来的，引导读者自己思考，自己平滑过渡到下一节；或者有一些会把过渡放到某一节的课后习题中，先让读者自己思考，然后引导出下一节。逻辑链很清楚，也很容易让读者建立自己的逻辑链，这样知识容易成体系，而不是零散的。

国内部分教材会直接抄国外的教材（毕竟落后就要借鉴先进），把很多内容省略了（所谓的废话），但是让读者阅读时就容易逻辑断链，容易迷惑。

我们知道 1+1=2，定义了加法。对于任意的 x，x+0=x，得到零元：0 。
我们知道 2*2=4，定义了乘法。 对于任意的 x，x*1=x，得到幺元：1 。
再加上分配率、交换律和结合律。（上面都是小学学过的），再补充点初中学过的映射。

好了，现在你就可以直接推导：群、环、域和代数的大量定理了。要说难度断层，数学才是真正的难度断层。

而数据结构：图去除环路就成了树；树去除分支就成了链表。看起来难度曲线还是挺随和的。

还有一些比较深奥难以理解的知识（非入门级教材），其实是理论的创造者经过好几年的摸索得到的知识，有时作者都很难说清自己的方法逻辑链（偶然有的灵感），这些东西需要慢慢消化了，毕竟人家几年时间创造的理论或者算法，不可能一两个小时被别人就弄的很清楚（尤其是逻辑链）

@RubyJack 线性表的定义也是递归的。链表一样是很典型的递归结构，只不过是尾递归，所以简单一点。

@nicebird 树只要不旋转就都很简单，无非一点递归，但是一旦涉及到旋转的自平衡，我就自学不下去了。。。

树和图你都觉得难以理解，那纯粹是你不愿多花功夫去学习……哪有啥断层和“前置科技”啊。
别和身边差的人比，这一行里理解树、图并觉得非常自然的大有人在。
也别为自己找花里胡哨的借口，这完全是多花时间就能学会的东西。

可能学了离散数学好理解一点？

我觉得很多人就是学得太少想得太多。树和图的基础定义确实比线性表难一点，但充其量也就是 1 和 5 的区别而算导前中期的难度就可以达到 50 。

尾队列有点绕的

不是很理解楼主的意思；按照前驱后继来理解：
1 前驱 1 后继：线性表
1 前驱 n 后继：树
n 前驱 n 后继：图

数组和链表只是线性表的实现方式，队列或者栈只是线性表的特异型；
图可能退化成树，树也可能退化成线性表
线性表可以用树表示，树也可以用图来表示

是说学习曲线在某个地方特别陡吧。

emmm，数据结构没觉得，算法我认为是动态规划.... 非科班，leetcode 中等遇到 dp，真的是来回放弃了十余次，多年后才啃下来。

我觉得 cs 里很多概念和算法都是取材抽象于人类历史的智慧。诸如几种 IO 模型，同步异步，你提到的这些数据结构自然也是。族谱图不就是最典型的树么？只要是对 cs 发展有帮助的都可以拿来用，无非是模型转换的难度大小。

队列，链表属于一维，树属于二维，图属于多维

因为逻辑和抽象思维能力，前面回复里说了，链表数组，树是一对一或一对多，而图却是多对多，在数学维度上是递增，但是对个人的逻辑和抽象能力是指数级的上升

还是链表没学透，链表实验写多了，你自己就会想要是一个节点可以指向多个节点就好了。

是你的理解能力不够。

其实就是从一维跨越到了二维乃至多维

一维到二维到多维，难度不是线性增长，而是指数增长

单纯学不下去...然后找了个借口....666

一个类里面塞一个自己类的指针不就是链表么？
一个类里面塞 2 到 n 个自己类的指针（数组）不就是树么？
有啥断层的？
抽象和实践距离很短，终究只是没学好，只学到了抽象的概念而已

这个不是断层，这和学数学差不多，都是先学习特例，然后进行抽象的更一般的推广。

学数学的时候基本都是这样的套路。比如先学习一次函数和二次函数的倒数，然后就不会不停的学三四五六次函数的倒数了，而是先把基本函数的倒数学了，然后直接推广到一般函的倒数性质，在更一般的层面的学习。当学习一般函数的倒数时，计算的复杂度就会极速上升，然后会发现有的函数甚至没有倒数，现有的求倒方法也不是在所有函数上都适用。这也就像数据结构中简单的数据结构其“配套”的算法也很简单，更抽象一般的数据结构其“配套”的算法也就更复杂。这样的复杂本质数学带来的，这可能是你觉得难度突然上升的原因，本质只是抽象程度提高了。而人类的大脑并不擅长理解抽象的东西。

数据结构也是一样的，数组链表这样的一纬线性表，是可以通过图论定义的，可以看作特殊的图，数据结构中的树（树也是一个有向无环图，数据结构中接触到的多半是二叉结构，这样的结构在图论中可以精确定义）和图（多半是无环图）也只是图的几个特殊结构，还没有推广到很一般的“图”。图论是离散数学的一个分支，数据结构和算法很多都可以在离散数学里面找到影子。其本质还是一个从特殊到一般的过程。从小到大的数学也基本都是这样教的。

一个节点未发生分叉的树，就是链表

( 链表就是一个树阿，把链表呈 45 倾斜放置 就是一个节点未发生分叉的树

你可以说 你学的从来就是树：不分叉的树 (数组 链表 队列 栈) 、分叉的树 (二叉 平衡 旋转)

我咋觉得很多人理解错了，楼主不是觉得树和图难以理解（这些本来就是日常生活中和常见的东西），而是觉得“其上的计算行为”（算法）难以理解。我觉得这很正常啊，有些本来就不是很直观，否则凭啥最先写出来人还能把名字加到前面。在写出来这些最终的算法前，是不是还有一些更直观但是更低效的算法，又是如何一步一步发展到现在的，我想这才是楼主想知道的，我觉得这个问题挺有趣，有没有资料是讲这个内容的？

举个例子，比如微积分，我们现在学到的都是有严格定义的，也是极其抽象也难以理解。但并非一开始就是这样，牛顿搞微积分的时候是相对直观但不严谨的，他处理无穷大无穷小的时候都是极其简单粗暴的，发展到现在这样是无数天才的数学家不断改进的结果。一来就是ε～δ这套东西，就能马上理解不感到困惑才是少数吧。现在很多算法就相当于直接就是ε～δ，难以理解也是正常的。

79 和 81 楼 才是理解楼主问题的回答，其他的答主都没有理解楼主要问的。

@oshio +1

很棒的问题，归因到最后或许是人脑在宇宙中的局限性。

@oshio
@BlackBerry999 看我的回帖啊。图论的第一篇论文是欧拉 18 世纪发表的，早在计算机出现前就出现“图”和“树”了。计算机时代只不过是把人家的方法变成了程序而已。“算法”是不过是计算机中的应用数学。

如果你要看怎么一步步推出来的，去追溯以前的论文呀？从图论一直到拓扑，够你体会揣摩前人怎么一步步完善“图”的概念的 www

当然我没有看过图论的一系列论文，计算机算法经典教材上的内容够我用了。我也不觉得有啥需要追本溯源的，算法已经是非常贴近直观的东西了，没有追本溯源的必要。

说到拓扑，我倒是一直很想学，但是一直没有充分的时间去做这件事情……

我觉得这个东西要从物理上对状态只能二进制保存和处理来解释
除非有一种别的物质可以物理的存储更多的状态且能控制一定的成本
而一切数学和数据结构的行程的确也是为这种物理结构服务的
这一些都要从存储物理结构的 01 状态和 cpu 物理结构的 01 处理方式
所有数据结构都是从 01 上抽象出来的
也就是说包括数和图都是从简单数据结构抽象，简单的从物理 01 来

我是这么理解的

没感觉是断层的，可能理解角度不同，个人理解最基本的存储结构就是连续的和不连续的，一个对应数组，另一个对应链表，然后剩下的所有的数据结构都是基于二者之上的，例如使用数组表达的队列和使用链表表达的队列，使用数组表达的树状结构和使用链表表达的树状结构…… 难于理解是肯定的，因为不直观啊……

再多说一句，教材是很难把“怎么一步步推出来这东西”给你呈现出来的。别的不说，几百年的智慧积累，期间主流思考方法不知道换了多少茬。数学理论也是个不断修正的过程，比如三次数学危机以及后续改变：

1 、第一次为了解决等腰直角三角形斜边长的问题，诞生了无理数；
2 、第二次为了解决微积分中“无穷小量”定义不清晰的问题，诞生了实分析（也就楼上提到的 ε～δ 语言）。
3 、第三次为了解决罗素悖论（理发师悖论：理发师只为小镇上不给自己理发的人理发，请问理发师是不是应该给自己理发？），从朴素集合论发展出了现代集合论。

楼上提过一上来就说 ε～δ 语言让人无法理解，没错这很正确，我刚学微积分也为之愤慨。但是啊，你一个学期的内容，教材不可能从 18 世纪牛顿的微积分开始讲，然后告诉你这个时代的微积分有什么问题，后续遇到了什么问题，以及实分析的发展过程，最后是测度论的完善。近一点来说，一百多年前康托尔提出实数不可数的时候，同时代的数学家都在嘲笑他呢。

工科学个皮毛，懂点前几百年数学家总结出来的最精炼的内容（ε～δ 语言），省点功夫去学怎么写代码，岂不美哉？如果对于糊里糊涂感到不满、感到困惑，抽出业余时间自己学习一个呗。学的多了，自然理解这个中来龙去脉了。我也是在不断学习，试图懂得更多，满足自己的求知欲罢了。

我觉得哈数组、链表、队、栈都算是一维数据结构。
树、图都属于二维数据结构，只是说树是图的一种。
所有的一维数据结构都是二维数据结构的一种特例。
所有的一维数据结构也都能用二维数据结构所表示。
所以哪有什么断层啊。只是多维数据结构变化复杂。


以上，纯粹只是个人的观点。

至于前面有大佬说 树是二维，图是三维，不敢苟同。

@ahaxzh 其实我觉得你用一维二维来分类，我也不敢苟同。。。

话说没有树和图的章节，来个 KMP 算法，你就觉得简单了？？？

@besto KMP 算法和 BM 算法，hhh 。图算法至少是直观的，这俩字符串比较算法，OMG 就是个极限优化版自动机，从来都记不住，临时查资料也要看半天的那种。

书里和教程里的确可能没写，但是上课的时候老师肯定教了吧。至少我们老师开始教树的时候先拿了个二维链表出来，然后竖了起来。

KMP 也可以认为是一种自动机 所以到头来还是一种图

@gggxxxx 不同意

另外有人提到用维度来类比树 /图。
可能是因为虽然说树是一种特殊的图，但是树的性质实在是很特殊。
很多一维数据结构问题迁移到树上 往往不需要增加复杂度或者只需要增加一个 log 的复杂度(树链剖分 /欧拉序之类的算法)。

但是我觉得吧，这个观点是搞反了，以下谈谈我的观点。
图是一种应用广泛的模型，几乎所有问题都可以用图来建模。
树是一种特殊的图(无环)。
序列(也就是数组)可以理解为一种特殊的树(单链)。

我明白你的意思，这个问题是计算机模型造成的。
内存是图灵机纸带的具体实现，它本质上是一维的数据存储器。对计算机的操作可以抽象成对纸带的读写，也就是一维的操作，越接近底层的语言越是如此。
你觉得数组、链表、队列和栈比较简单，是因为你把它们理解成一维结构，这种结构和纸带是简单对应的。
而树和图，为了方便学习，人需要把它们理解成二维结构。你在纸上画出树和图很容易，但计算机看不懂二维的画。所以你说的附加其上的复杂的计算行为，是二维结构向纸带降维投影的过程。树和图实现起来复杂度上了个台阶，是因为要在一维空间保留二维结构的全部信息；显得突兀是因为它们比计算机模型高一个维度，确实是塞进耗子窝里的大象。

还有很重要的一点，编程实现时，不像画在纸上的那种点线连接，没有直观结构了