数据结构树和图之间有什么区别? [英] What's the difference between the data structure Tree and Graph?

问题描述

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

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?

推荐答案

树只是图的一种受限形式.

A Tree is just a restricted form of a Graph.

树具有方向(父/子关系)，并且不包含循环. 它们适合有向无环图(或DAG)类别. 因此，树是DAG，其限制是一个孩子只能有一个父母.

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.

需要指出的一件事很重要，树不是递归数据结构. 由于上述限制，它们不能实现为递归数据结构.但是，也可以使用通常不是递归的任何DAG实现. 我首选的Tree实现是集中式地图表示，并且是非递归的.

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.

这篇关于数据结构树和图之间有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！