srcmini本文概述
没有循环的图称为非循环图。树是无环图或没有循环的图。
一棵树或一棵普通树被定义为称为顶点或节点的元素的非空有限集合, 其具有以下属性：每个节点可以具有最小度1和最大度n。可以将其划分为n + 1个不相交的子集, 以使第一个子集包含树的根, 其余n个子集包含n个子树的元素。
定向树
有向树是无环有向图。它具有一个度数为1的节点, 而所有其他节点的度数为1, 如图所示：
外部度为0的节点称为外部节点或终端节点或叶。外部度大于或等于1的节点称为内部节点。
有序树
如果在每个级别的树中定义了顺序, 那么这种树称为有序树。
示例：图中显示的树代表同一棵树, 但顺序不同。
树木的特性
- 一棵树的每对顶点之间只有一条路径。
- 如果图G, 则在每对顶点G之间只有一个路径是一棵树。
- 具有n个顶点的树T具有n-1个边。
- 图是一棵树, 当且仅当它是最小连接时。
植树
如果有向树恰好具有一个称为根的节点或顶点, 其传入度为0, 而所有其他顶点的传入度为1, 则该树称为根树。
注意：1.没有节点的树是根树（空树）2.没有子节点的单个节点是根树。
顶点的路径长度
根树中顶点的路径长度定义为从根到顶点的路径中的边数。
示例：找到节点b, f, l, q的路径长度, 如图所示：
解决方案：节点b的路径长度为1。节点f的路径长度为2。节点l的路径长度为三。节点q的路径长度为四。
评论前必须登录！
注册