邻接表和树

Question

看到邻接表这里，感觉算法课上介绍树的结构就是邻接表的特殊情况？比如树有根节点，通过left, right把节点相连，类似于邻接表里的链表结构。不知道这样理解正确吗？谢谢您！

Answer 1

liuyubobobo 2022-03-18 01:43:50

树本身就是特殊的图没有错。但是我们一般实现的树结构和邻接表不同。

关键区别是：使用邻接表可以快速得到**任何**一个节点的所有相邻节点。但是我们一般实现的树结构不能快速拿到树上任意节点的相邻节点（左右孩子），只能拿到根节点，从根节点出发先要找到目标节点，再去找到这个目标节点的相邻节点（左右孩子。）

但我们完全可以用图的方式去存储一棵树，不管是邻接表还是邻接矩阵。实际试试看？然后实际用代码比较一下二者的异同？使用实际的代码去验证你的想法，这一点在计算机学习上至关重要。

继续加油！：）

• 提问者 讲武德的年轻人 #1

  谢谢您的问题。再问一个稍显功利的问题。如果我想通过学习这门课，帮助刷BFS/DFS的相关题目。是不是主要还是借鉴图论算法的思路呢？按您所说，图论主要用邻接表存储，而树则稍有不同，所以技术上实现BFS/DFS有不同的？谢谢！

• liuyubobobo 回复 提问者 讲武德的年轻人 #2

  首先，是的，在图上 bfs 和在树上 bfs 在代码层面是有区别的，但是这个区别也很 make sense，就是因为二者结构的不同，但是他们都是 bfs。其次，实际上，对于任何算法，本质都是在学习思路，而不是“具体的实现”。我们需要能用同样的思路去解决不同的问题，而不是只知道一种实现。知道一种实现是更深入理解这个思路的第一步。