blocks|key|564972|text|树是显而易见的:它们是由带有子节点的节点组成的递归数据结构。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|564973|Map+(又称字典)是键/值对。给一个map一个键，它将返回相关的值。|564974|地图可以使用树来实现，我希望你不会感到困惑。|564975|更新:混淆"map“的"graph”是非常令人困惑的。|564976|图比树更复杂。树意味着递归的父/子关系。遍历树的方式有以下几种:深度优先、广度优先、层次顺序等。|564977|图可以在节点之间有单向或双向路径，可以是循环的或非循环的，等等。我认为图更复杂。|564978|我认为粗略地搜索任何像样的数据结构文本(例如“算法设计手册”)将提供比任何数量的SO答案更多和更好的信息。我建议你不要走被动路线，开始自己做一些研究。|564979|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|S|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|T|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|U|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|V|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|O|$]]

Trees are obvious: they're recursive data structures consisting of nodes with children.

Map (aka dictionary) are key/value pairs. Give a map a key and it will return the associated value.

Maps can be implemented using trees, I hope you don't find that confusing.

UPDATE: Confusing "graph" for "map" is very confusing.

Graphs are more complex than trees. Trees imply recursive parent/child relationships. There are natural ways to traverse a tree: depth-first, breadth-first, level-order, etc.

Graphs can have uni-directional or bi-directional paths between nodes, be cyclic or acyclic, etc. I would consider graphs to be more complex.

I think a cursory search in any decent data structures text (e.g. "Algorithms Design Manual") would give more and better information than any number of SO answers. I would recommend that you not take the passive route and start doing some research for yourself.

blocks|key|781400|text|树只是图的一种受限形式。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|781401|树有方向(父/子关系)，并且不包含循环。它们符合有向无环图(或DAG)的范畴。因此，树是具有限制的DAG，子代只能有一个父代。|781402|需要指出的重要一点是，树不是递归数据结构。由于上述限制，它们不能作为递归数据结构实现。但是也可以使用通常不是递归的任何DAG实现。我更喜欢的Tree实现是一个集中式的map表示，并且是非递归的。|781403|图的搜索通常是广度优先或深度优先。这同样适用于Tree。|781404|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

A Tree is just a restricted form of a Graph.

Trees have direction (parent / child relationships) and don't contain cycles. 
They fit with in the category of Directed Acyclic Graphs (or a DAG).
So Trees are DAGs with the restriction that a child can only have one parent.

One thing that is important to point out, Trees aren't a recursive data structure. 
They can not be implemented as a recursive data structure because of the above restrictions. But any DAG implementation, which are generally not recursive, can also be used.
My preferred Tree implementation is a centralized map representation and is non recursive.

Graphs are generally searched breadth first or depth first. The same applies to Tree.

blocks|key|565060|text|在数学中，图是一组对象的表示，其中一些对象对通过链接连接在一起。相互连接的对象由称为顶点的数学抽象表示，连接某些顶点对的链接称为边1。通常，图以图形形式描述为顶点的一组点，由边的直线或曲线连接。图是离散数学的研究对象之一。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|565061|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

In mathematics, a graph is a representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.[1] Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

blocks|key|781458|text|树中有一个根节点，并且一个子节点只有一个父节点。但是，没有根节点的概念。另一个区别是，树是层次模型，而图是网络模型。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|781459|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

one root node in tree and only one parent for one child. However, there is no concept of root node. Another difference is, tree is hierarchical model but graph is network model.

blocks|key|565136|text|在树中，每个节点(根节点除外)恰好有一个前置节点和一个或两个后继节点。可以使用In-order、Pre-order、Post-order和Breadth+traversals​遍历它。树是一类特殊的无圈图，因此被称为有向无环图(+DAG+)。树是一种分层模型。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|565137|在图中，每个节点都有一个或多个前导节点和后继节点。通过使用深度优先搜索(DFS)和广度优先搜索(BFS)算法来遍历图。图有圈，所以它比树更复杂。图是一种网络模型。有两种图:有向图和无向图。|565138|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

In tree, each node (except the root node) has exactly one predecessor node and one or two successor nodes. It can be traversed by using In-order, Pre-order, Post-order, and Breadth First traversals​. Tree is a special kind of graph that has no cycle so that is known as DAG (Directed Acyclic Graph). Tree is a hierarchical model.

In graph, each node has one or more predecessor nodes and successor nodes. The graph is traversed by using Depth First Search (DFS) and Breadth First Search (BFS) algorithms. Graph has cycle so it is more complex than tree. Graph is a network model. There are two kinds of graph: directed graphs and undirected graphs.

blocks|key|565186|text|树基本上是不含圈的无向图，所以我们可以说树是一种更有限制的图。然而，在编程中，树和图有不同的应用来实现各种算法。例如，图可以用于建模，路线图和树可以用于实现任何层次的数据结构。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|565187|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Tree is basically undirected graph which not contain cycle,so we can say that tree is more restricted form of graph.
However tree and graph have different application to implement various algorithm in programming.
For example graph can be used for model road map and tree can be used for implement any hierarchical data structure.

blocks|key|781619|text|TREE+:
+1.+Only+one+path+exist+between+two+vertices+(Nodes).
+2.+Root+node+is+the+starting+node+of+the+tree.
+3.+Tree+doesn't+have+loops.
+4.+Number+of+edges:+n-1+(where+n+is+number+of+nodes)
+5.+Tree+looks+like+Hierarchical
+6.+All+trees+are+graph.

GRAPH+:
+1.+More+than+one+path+is+allowed+between+two+vertices.
+2.+There+is+no+root+node+concept+(we+can+start+from+any+node).
+3.+There+can+be+loop+in+graph.
+4.+Number+of+edges+are+not+defined.
+5.+Graph+looks+like+Network.
+6.+All+graphs+are+not+tree.|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|781620|您可以在此视频中找到更详细的解释->+https://www.youtube.com/watch?v=KVHrjVTp9_w|unstyled|offset|length|781621|entityMap|0|LINK|mutability|MUTABLE|url|https://www.youtube.com/watch?v=KVHrjVTp9_w^0|0|J|17|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|R|8|@]|9|@$G|S|H|T|1|U]]|A|$]]|$1|I|3|-4|5|F|7|V|8|@]|9|@]|A|$]]]|J|$K|$5|L|M|N|A|$O|P]]]]

<pre><code>TREE :
 1. Only one path exist between two vertices (Nodes).
 2. Root node is the starting node of the tree.
 3. Tree doesn't have loops.
 4. Number of edges: n-1 (where n is number of nodes)
 5. Tree looks like Hierarchical
 6. All trees are graph.

GRAPH :
 1. More than one path is allowed between two vertices.
 2. There is no root node concept (we can start from any node).
 3. There can be loop in graph.
 4. Number of edges are not defined.
 5. Graph looks like Network.
 6. All graphs are not tree.
</code></pre>
More detailed explanation you can find in this video -&gt; <a href="https://www.youtube.com/watch?v=KVHrjVTp9_w" rel="nofollow noreferrer">https://www.youtube.com/watch?v=KVHrjVTp9_w</a>

Academically speaking, what's the essential difference between the data structure Tree and Graph? And how about the tree based search and Graph based search?

What's the difference between the data structure Tree and Graph?

从学术上讲，数据结构树和图的本质区别是什么？那么基于树的搜索和基于图的搜索又如何呢？

问数据结构树和图有什么不同？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问数据结构树和图有什么不同？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问数据结构树和图有什么不同？
EN