图形与树
数据结构中使用了图和树。图和树之间肯定有一些区别。一组具有二元关系的顶点称为图,而树是一种数据结构,其中有一组相互链接的节点。
图形
图是由边连接起来的一组项,每个项称为节点或顶点。换句话说,一个图可以定义为一组顶点,这些顶点之间存在二元关系。
在图的实现中,节点被实现为对象或结构。边可以用不同的方式表示。方法之一是每个节点都可以与一个入射边阵列相关联。如果要将信息存储在节点而不是边中,那么数组充当指向节点的指针,也表示边。这种方法的优点之一是可以向图中添加额外的节点。可以通过向数组添加元素来连接现有节点。但是有一个缺点,因为需要时间来确定节点之间是否存在边。
另一种方法是保持二维数组或矩阵M具有布尔值。从节点i到j的边的存在由条目Mij指定。这种方法的一个优点是可以找出两个节点之间是否存在任何边。
树
树也是计算机科学中使用的一种数据结构。它类似于树的结构,并且有一组相互链接的节点。
树的节点可以包含条件或值。它也可以是自己的树,也可以表示单独的数据结构。树数据结构中存在零个或多个节点。如果一个节点有一个子节点,那么它被称为该子节点的父节点。一个节点最多只能有一个父节点。从节点到叶的最长向下路径是节点的高度。节点的深度由到其根的路径表示。
在树中,最上面的节点称为根节点。根节点没有父节点,因为它是最顶层的。从该节点开始所有树操作。通过使用链接或边,可以从根节点访问其他节点。最底层的节点称为叶节点,它们没有任何子节点。具有子节点数的节点称为内部节点或内部节点。
图与树的区别:•树可以描述为没有自循环和回路的图的特例。•树中没有环,而图可以有环。•图中有三个集合,即边,顶点和表示它们之间关系的集合,而树由相互连接的节点组成。这些连接称为边缘。 |