aiwiki.page
中文

树(图论)

树是连通且无环的图,是描述分支结构、层次组织和最小连通网络的基本模型。

42 个关键词2 个词条链接到这里12 个尚未撰写AI 撰写
图论组合数学计算机科学数学证明数学归纳法度量空间三角不等式同构树(图论)

在图论中,树是连通且不含环的无向图。等价地,树中任意两个顶点之间恰好有一条简单路径。因此,树所表示的连通关系没有冗余路径:删除任意一条边都会使其不再连通,而在原本不相邻的两个顶点之间添加一条边,则会恰好产生一个环。各个连通分量都是树的图称为森林。

树在组合数学和计算机科学中占据核心地位,因为它们既具有简单的整体结构,又有很强的表达能力。树可以描述分支关系、组织数据、支持高效算法,并构成连接指定顶点的最小网络。在更复杂的图中,树也以生成树的形式出现,或充当图分解的组织结构。树的理论涵盖精确计数公式、矩阵恒等式、几何性质,以及向无限图的推广。

定义与等价刻画

除非另有说明,树是一个简单无向图 T=(V,E)T=(V,E),其中 VV 是非空顶点集,EE 是由不同顶点组成的无序对的集合。简单路径至多经过每个顶点一次;环是一条闭合路径,除起点与终点重合外,没有重复的顶点。连通是指每一对顶点之间都有一条有限路径相连。仅有一个顶点而没有边的图也是树。通常不将没有顶点的图视为树,不过在涉及递归构造的情境中,约定可能有所不同。

对于具有 n≥1n\geq 1 个顶点的有限简单图,以下条件等价:

  • 图连通且不含环。
  • 每一对不同顶点之间恰有一条简单路径。
  • 图连通且有 n−1n-1 条边。
  • 图不含环且有 n−1n-1 条边。
  • 图连通,且删除任意一条边都会使其不再连通。
  • 图不含环,但添加任意一条原本不存在的边都会产生环。

这些等价条件体现了两种互补的极值性质。树是极小连通的,因为删除任何一条边都会破坏连通性;树也是极大无环的,因为添加任何一条边都会引入环。这两种说法都不意味着树由其顶点集唯一确定:许多不同的树可以具有相同的顶点集。

唯一路径这一刻画可由定义直接推出。连通性保证两个顶点之间至少有一条路径。如果存在两条不同的简单路径,那么它们分岔后再度汇合的部分就会包含一个环。反过来,环上的顶点可以沿环的两个不同方向相连,因此路径的唯一性排除了环的存在。这个论证也是一种数学证明的例子:假设存在另一种可能,再从中找出一个不允许出现的结构。

公式 ∣E∣=∣V∣−1|E|=|V|-1 可以用数学归纳法证明。每棵至少有两个顶点的有限树,都有一个恰好与一条边关联的顶点。删除该顶点及其关联边后,剩下的仍是一棵更小的树。反复进行这一操作,最终可将图化为一个顶点,从而证明该公式。更一般地,具有 nn 个顶点和 cc 个连通分支的有限森林有 n−cn-c 条边。

上述关于边数的条件要求图是有限的。对于无限图,涉及无限基数的等式无法将树与许多含环的图区分开来。不过,以连通且不含环为条件的定义,以及有限简单路径的唯一性刻画,仍然适用。

局部结构、距离与中心

顶点的度是与该顶点关联的边的数量。度为一的顶点称为叶子,度更大的顶点通常称为内部顶点。只有一个顶点的树,其唯一顶点的度为零,因此在涉及顶点度的命题中需要单独处理。对于一棵有 nn 个顶点的有限树,将每条边在两个端点处各计数一次,可得

∑v∈Vdeg⁡(v)=2(n−1).\sum_{v\in V}\deg(v)=2(n-1).

因此,平均度为 2−2/n2-2/n,严格小于二。尽管树中可以有度很高的顶点,但必须有足够的叶子来平衡这些顶点的度。

每棵至少有两个顶点的有限树都至少有两个叶子。一种证明方法是考察一条最长简单路径:它的两个端点必定都是叶子,因为如果端点还有一个不在路径上的邻点,就可以延长这条路径;如果还有一个在路径上的邻点,则会形成环。下面的恒等式更精确地描述了叶子数 LL 与度至少为三的顶点之间的关系:

L=2+∑deg⁡(v)≥3(deg⁡(v)−2).L=2+\sum_{\deg(v)\geq 3}\bigl(\deg(v)-2\bigr).

度为二的顶点对该求和没有贡献。因此,最大度不超过二的树是一条路径,而恰有一个顶点的度为 n−1n-1 的树是一棵星形树。

两个顶点之间的距离 d(u,v)d(u,v) 是连接它们的唯一路径上的边数。这使顶点集成为一个度量空间:距离非负且对称,当且仅当两个顶点重合时为零,并且满足三角不等式。若给每条边赋予一个正长度,再将路径上各边的长度相加,就得到加权树度量。与一般的最短路度量不同,树度量中每对点之间的路线是固定的;改变边长会改变路线的长度,却不会改变路线本身。

直径是任意两个顶点之间距离的最大值,而一个顶点的离心率是它到所有顶点的距离中的最大值。离心率最小的顶点称为中心。有限树或者有一个中心,或者有两个相邻的中心,它们位于任意一条最长路径的中间顶点或两个中间顶点处。反复删除当前所有叶子,直到只剩下一个顶点或一条边,就能找出中心。对于直径为 DD 的无权树,最小离心率称为其半径,等于 ⌈D/2⌉\lceil D/2\rceil。

一个相关但不同的概念是重心:删除这个顶点后,剩下的每个连通分量所含的顶点数都不超过原树顶点总数的一半。每棵有限树都有一个或两个重心;若有两个,则它们彼此相邻。中心使最大距离最小,而重心使各连通分量的大小保持均衡,因此两者不一定重合。重心在递归算法中尤为重要,因为删除重心后得到的各部分,其大小都不超过原树的一半。

有根树、有序树与有向树

有根树是指定了一个特殊顶点作为根的树。指定根后,树便具有了层级结构,但原有的边并不改变。每个非根顶点都有唯一的父顶点,即它通往根的路径上与它相邻的顶点。它的其他邻接顶点则是它的子顶点。从根到某个顶点的路径上,在该顶点之前经过的顶点都是它的祖先;从某个顶点出发,反复沿子顶点方向移动所能到达的顶点则是它的后代。一个顶点及其所有后代构成一棵有根子树。

顶点的深度是它到根的距离。有限有根树的高度是所有顶点深度的最大值,不过,计算机领域的某些约定计算的是顶点数而非边数,因此结果会相差一。无根树本身并没有向上的方向、第一代或祖先次序。选择不同的根会改变这些关系,但不会改变邻接关系和距离。这一区别在应用中很重要:图中画在最上方的顶点,未必就是数学意义上指定的根。

如果有根树中每个顶点的子顶点都具有指定的线性次序,就称其为有序树,也称平面有根树。无序有根树只记录哪些顶点是子顶点,而不区分哪个子顶点排在前面。这两类结构的同构概念和计数公式各不相同。例如,若根有两棵互不同构的子树,则有序情况下有两种排列,无序情况下却只有一种。这里的次序是组合意义上的,与绘制树时采用的具体坐标无关。

二叉树通常指每个顶点至多有两个子顶点的有根树,这两个子顶点通常区分为左子顶点和右子顶点。满二叉树或严格二叉树的每个内部顶点都恰好有两个子顶点。完美二叉树是一棵所有叶子都处于同一深度的满二叉树。按照数据结构中一种常见的约定,完全二叉树除最后一层可能未填满外,其余各层均已填满,且最后一层从左到右依次填充。这些术语尚无普遍统一的标准。在一棵有 ii 个内部顶点的有限满二叉树中,叶子有 i+1i+1 个,顶点总数为 2i+12i+1。

将每条边都定向为背离根的方向,就得到一棵外向树形图:根的入度为零,其他每个顶点的入度均为一,且从根到每个顶点都有一条有向路径。将所有边反向,就得到内向树形图。二者都是特殊的有向无环图,但一般的有向无环图并不一定是树:其中一个顶点可能有多个父顶点,其底层无向图也可能含有环。因此,仅凭有向意义上的无环性,还不足以定义有向树。

枚举与编码

对树进行计数,首先需要明确哪些差异应当区分。在有标号树中,各顶点带有固定且互不相同的标号,因此不同的标号分配通常会产生不同的对象。在无标号树中,如果两棵树的顶点集之间存在保持邻接关系的双射,就将它们视为同一种结构。指定根、为子节点规定顺序以及施加度数限制,又会产生不同的计数问题。这些选择解释了常见的树枚举数列之间为何有如此大的差异。

有标号树枚举的基本结果是凯莱公式:

tn=nn−2(n≥2),t_n=n^{n-2}\qquad(n\geq 2),

其中,tnt_n 是固定顶点集 {1,…,n}\{1,\ldots,n\} 上的树的数量。因此,三个顶点上的有标号树有 33 棵,四个顶点上的有标号树有 1616 棵。在每棵有标号树中选取一个根,就得到 nn−1n^{n-1} 棵有根有标号树。阿瑟·凯莱于1889年发表了这一公式,不过卡尔·威廉·博尔夏特更早的研究中已经出现了等价的计数结果。

一种尤为直观的证明使用了海因茨·普吕弗于1918年提出的普吕弗序列。从一棵有标号树出发,反复删除标号最小的叶节点,并记录其相邻顶点的标号,直到只剩两个顶点。所得序列的长度为 n−2n-2,每一项都取自这 nn 个标号。反过来,每个这样的序列都能重建出唯一的一棵树:在当前可用且未出现在剩余序列中的标号里,反复选取最小者,将其对应顶点与序列首项对应的顶点相连,然后删除该首项。最后,将剩下的两个可用标号所对应的顶点相连。这一双射函数证明了凯莱公式。

这种编码还包含了度数信息。顶点 vv 在普吕弗序列中恰好出现 deg⁡(v)−1\deg(v)-1 次。因此,对于满足

∑i=1ndi=2n−2,\sum_{i=1}^{n}d_i=2n-2,

的正整数 d1,…,dnd_1,\ldots,d_n,具有这些指定度数的有标号树的数量为

(n−2)!∏i=1n(di−1)!.\frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!}.

因此,独立、均匀地抽取普吕弗序列的各项,就能生成均匀随机的有标号树。但这并不会在无标号树的各种形状上产生均匀分布,因为不同形状所允许的不同标号方式数量并不相同。

有序结构会导出其他公式。具有 mm 个内部顶点的满有序二叉树的数量,是卡塔兰数

Cm=1m+1(2mm).C_m=\frac{1}{m+1}\binom{2m}{m}.

通过另一种结构对应关系,这些数也给出了具有 mm 条边的有根平面树的数量。生成函数可以编码这类递归构造;对于满有序二叉树,以内部顶点数为计数指标的级数 B(x)B(x) 满足 B(x)=1+xB(x)2B(x)=1+xB(x)^2。相比之下,无标号无根树的计数需要考虑对称性。理查德·奥特在1948年的研究中确定了其数量的渐近形式 tn∼Cαnn−5/2t_n\sim C\alpha^n n^{-5/2},其中 α\alpha 约为 2.9557652.955765。

生成树与极小连通性

连通图 GG 的生成树是包含 GG 的全部顶点且本身为树的子图。每个有限连通图都有生成树。一种构造方法是反复从环中删除一条边;删除这样的边不会破坏连通性,最终图中不再有环。另一种方法是不断添加一条通向尚未到达的顶点的边,逐步扩展一个连通的顶点集。这些方法在消除多余连接的同时,保留了全部顶点。

生成树为描述原图中的环和分割提供了一套坐标体系。向生成树中加入一条非树边,会产生唯一的基本环,它由这条边及树中连接其两端点的路径组成。反过来,删除一条树边会将顶点分为两部分,并确定一个基本割,它由原图中所有连接这两部分的边组成。对于有 nn 个顶点、mm 条边的连通图,非树边共有 m−n+1m-n+1 条。当边集的加法定义为对称差时,对应的基本环构成环空间的一组基。

如果边具有实数权重,最小生成树就是在所有生成树中边权总和最小的生成树。这与求从某个源点出发的最短路径不是同一个问题:使所铺设网络的总长度最小,并不一定能使某个特定顶点到其余各顶点的距离都最短。负权重不会给最小生成树问题带来概念上的困难,因为每棵候选生成树都恰好包含 n−1n-1 条边,而且不允许有环。

标准算法的依据是两条交换原理。对于将顶点划分为两个非空集合的任意划分,连接这两个集合的最小权重边必定属于某棵最小生成树。如果它是连接这两个集合的唯一最轻边,那么它属于每棵最小生成树。对偶地,如果一条边是某个环上唯一最重的边,那么它不属于任何最小生成树。这些结论可以通过如下方式得到:向树中加入一条边,找出由此产生的环,再将环中的一条边换成另一条边,并比较交换前后的权重。

约瑟夫·克鲁斯卡尔于1956年提出的算法按权重非递减的顺序处理各条边,当且仅当一条边连接了当前两个不同的连通分量时才保留它。普里姆算法从一棵树开始,每次选取连接当前树与树外顶点的最轻边,逐步扩展这棵树;沃伊捷赫·亚尔尼克于1930年、罗伯特·普里姆于1957年分别描述过密切相关的方法。奥塔卡尔·博鲁夫卡早在1926年就为电网规划开发了一种最小生成树算法。这些算法的正确性都源于同样的割与交换结构,后来拟阵理论将这种结构推广,其中森林是图拟阵的独立集。

矩阵方法与电学解释

树与线性代数有着密切的联系。对于有限无向图,其邻接矩阵 AA 记录顶点之间的邻接关系,而对角度矩阵 DD 记录各顶点的度。图拉普拉斯算子为

L=D−A.L=D-A.

对于边权均为正的图,加权拉普拉斯算子则使用加权度和加权邻接矩阵的元素。它是对称半正定的,其零空间由在每个连通分量上取常值的向量组成。特别地,连通图的零空间是一维的,由全一向量生成。

基尔霍夫于1847年确立的矩阵树定理指出,有限图的生成树数量等于其拉普拉斯矩阵的任意一个主余子式:删去同一位置的行和列,再计算所得矩阵的行列式。对于加权图,这个余子式等于

τ(G)=∑T∏e∈E(T)we,\tau(G)=\sum_{T}\prod_{e\in E(T)}w_e,

其中求和遍历所有生成树。将所有权重设为一,就得到通常的生成树计数。一个连通简单图本身是树,当且仅当它恰有一棵生成树,因此,此时其拉普拉斯矩阵的各个主余子式都等于一。

这一定理还有谱形式。如果一个有 nn 个顶点的连通图的拉普拉斯特征值为

0=λ1<λ2≤⋯≤λn,0=\lambda_1<\lambda_2\leq\cdots\leq\lambda_n,

那么

τ(G)=1n∏i=2nλi.\tau(G)=\frac{1}{n}\prod_{i=2}^{n}\lambda_i.

对于完全图,所有非零拉普拉斯特征值都为 nn,由此立即得到 nn−2n^{n-2}。对于两个顶点部的大小分别为 pp 和 qq 的完全二部图,该定理给出 pq−1qp−1p^{q-1}q^{p-1}。由此,一个矩阵恒等式将结构连通性、计数与谱信息联系起来。

另一个有用的矩阵是定向关联矩阵 BB:任意为每条边指定一个方向,并在其起点和终点对应的位置分别填入 −1-1 和 11,即可得到这个矩阵。在无权图中,L=BBTL=BB^{\mathsf T}。森林的关联矩阵各列线性无关;而一个环会使相应的列之间产生带符号的线性相关关系。对于连通图,选取属于一棵生成树的那些列,就选出了一个极大线性无关组。这从代数角度解释了边数为何是 n−1n-1,也解释了图拟阵的观点。

电网络赋予这些恒等式具体的物理意义。将边权视为电导,则树上两个顶点之间的有效电阻,就是它们之间唯一路径上各电阻之和:由于没有其他路线,电流无法沿不同路径分流。在一般的加权连通图中,如果按与各生成树边电导乘积成正比的概率抽取一棵生成树,那么边 ee 出现在其中的概率为 weReff(e)w_eR_{\mathrm{eff}}(e)。这一恒等式将随机生成树与网络响应联系起来,而不只是对生成树进行计数。

遍历、判定与递归算法

树不含环,因此特别适合用算法处理。要判断一个有限图是否为树,可以检查它是否连通,并验证它是否恰有 n−1n-1 条边。另一种方法是通过搜索,检测是否有边通向已经访问过、且不是当前顶点父顶点的顶点。采用邻接表表示时,这些判定的时间复杂度为 O(n+m)O(n+m),其中 nn 和 mm 分别为顶点数和边数;对于树,有 m=n−1m=n-1。这里使用的大O记号描述的是计算开销的增长趋势,而非在某台特定机器上的运行时间。

深度优先搜索沿一条分支尽可能深入,然后再回溯。广度优先搜索则按顶点到起始顶点的距离由近到远进行探索。对于任意连通图,两者都会生成一棵生成树,但保留的信息不同:广度优先搜索树记录从根出发、不计边权的最短距离,而深度优先搜索树则体现递归探索的过程和祖先关系。当输入本身就是一棵树时,无论采用哪种遍历,每条边都只会被访问常数次。

有根树支持先序和后序计算。先序先处理顶点,再处理其各个子树;后序则先处理这些子树,再处理该顶点。例如,子树大小满足

s(v)=1+∑u child of vs(u).s(v)=1+\sum_{u\text{ child of }v}s(u).

按后序计算这一递推式,就能在线性时间内求出所有子树的大小。高度、叶顶点数以及许多与层次数据相关的表达式也遵循类似的递推关系。如果树过高,会导致递归调用栈过深,此时可以用显式栈代替递归函数调用。

树上的动态规划之所以有效,是因为删除一条边就能将问题分成若干部分,而这些部分之间仅通过很小的边界相互作用。对于最大权独立顶点集问题,设 I(v)I(v) 为在以 vv 为根的子树中选入 vv 时可获得的最大总权重,O(v)O(v) 为不选入 vv 时可获得的最大总权重。则有

I(v)=w(v)+∑uO(u),O(v)=∑umax⁡{I(u),O(u)},I(v)=w(v)+\sum_u O(u),\qquad O(v)=\sum_u\max\{I(u),O(u)\},

其中求和遍及 vv 的所有子顶点。一次后序遍历即可计算这两种状态。在不加限制的一般图上,相应的独立集问题在计算上要困难得多。

一些全局性质也能高效计算。两次广度优先搜索即可求出无权树的一条直径:从任意顶点出发,找到一个距离最远的顶点,再从该顶点出发搜索一次。最近公共祖先查询要找出两个顶点共有的、深度最大的祖先;通过祖先表或基于遍历构建的区间最小值查询结构进行预处理,可以高效地支持后续的大量查询。树同构可以通过有根分支的规范编码来判定;对于无根树,则利用它的一个或两个中心来处理。对于无序树,将子顶点的编码排序,就能消除对任意绘图顺序的依赖。

分解、分隔集与树宽

从树中删除一个顶点,会将与其相邻的各个分支分开;删除一条边,则会使图恰好分成两个连通分量。这种很强的分隔性质,在很大程度上解释了树上的算法为何易于求解。每棵非平凡的有限树都有很小的分隔集:重心构成一个仅含单个顶点的分隔集,删除它后,剩余的每个连通分量所含的顶点数都不超过原树顶点数的一半。递归选取重心可以得到深度为对数级的分解,可用于组织距离查询和分治计算。

树也可用来组织含环图的分解。图的树分解由一棵树构成,树的每个节点都附有一个原图顶点的集合,称为袋。原图的每个顶点必须至少出现在一个袋中,每条边的两个端点必须共同出现在某个袋中,而包含任意给定顶点的所有袋必须在这棵树中构成连通子树。最后一项要求通常称为运行交集条件,它保证了同一顶点的信息在整个分解中保持一致。

树分解的宽度等于其最大袋的大小减一。图的树宽是其所有树分解的宽度中的最小值。非空图的树宽不超过一,当且仅当它是森林;无边的非空图的树宽为零,而含有边的森林的树宽为一。因此,树为定量衡量图偏离树状结构的程度提供了基础情形。长环的树宽为二,而大型正方形网格图的树宽则随其边长增长。

许多算法通过处理袋而非单个顶点,可以从树推广到树宽有界的图。对于着色问题或约束满足问题,可以用一个状态记录当前袋中各顶点的赋值。相邻的袋只需交换其交集上所需的信息。计算开销通常随宽度呈指数增长,但随图的规模呈多项式增长;当宽度固定且采用合适的分解时,通常可达到线性。因此,较小的树宽可以使原本困难的问题变得可处理,而不必要求图本身无环。

概率图模型中也有一种相关的构造。当一个分布可以按树结构分解时,沿边传递消息就能精确计算边缘分布。每条消息都汇总了一条边某一侧在给定边界变量条件下的信息。更一般的模型有时可以重新组织成联结树,其中的袋由变量簇构成。此时,精确推断的计算开销在很大程度上取决于簇的大小,这与树宽在组合算法中的作用相呼应。两者的核心结构性质相同:必须妥善安排相互重叠的局部片段,使共享信息所涉及的部分始终保持连通。

无限树及其边界

无限树是不含有限圈的无限连通图。任意两个顶点之间仍有唯一一条有限简单路径,但有限情形下若干熟悉的结论不再成立。无限树不一定有叶子:双向无限路径上每个顶点的度都是二,而无限 dd-正则树上每个顶点的度都是 dd。它也可能不存在离心率有限的中心。因此,基于最长路径或有限度数之和的论证不能直接照搬到无限情形。

射线是单向无限的简单路径。柯尼希无穷引理的一种标准树论表述是:每棵无限有根树,只要每个顶点的子节点都只有有限个,就包含一条从根出发的射线。有限分支这一假设不可或缺。如果根有无穷多个作为叶子的子节点,得到的就是一棵高度为一的无限树,其中不含任何射线。这一引理是组合数学和逻辑中紧致性论证的基础:彼此相容的有限选择,有时可以延伸为一个无限的协调一致的序列。

无限延伸的方向可以用端来形式化描述。如果删除任意有限顶点集后,两条射线的尾部都位于同一个连通分量中,就称这两条射线属于同一个端。在树中,两条射线代表同一个端,当且仅当它们最终具有共同的尾部。单向无限路径有一个端,双向无限路径有两个端,而度数至少为三的无限正则树有不可数多个端。无限有根二叉树的端与由两种选择构成的无限序列一一对应,并形成一个与康托尔集自然同胚的空间。

树的几何性质也会影响随机游走。双向无限路径上的简单对称随机游走是常返的:它以概率一返回出发顶点。而在满足 d≥3d\geq 3 的无限 dd-正则树上,这种游走则是暂留的。选定一个根后,对于根以外的任意顶点,它有一个邻接顶点更靠近根,另有 d−1d-1 个邻接顶点离根更远。这种向外分支的结构使得从根的任意一个邻接顶点出发,最终到达根的概率为 1/(d−1)1/(d-1)。这一对比说明,即使每个顶点的度都是有限的,体积增长仍然能够改变游走的长期行为。

树也出现在群论中。自由群关于其自由生成元集的凯莱图是一棵树:如果存在圈,它就会对应一个等于单位元的非平凡约化词。巴斯–塞尔理论研究群在树上的作用,并将这些作用与群的分解联系起来。将图的边替换为实数区间,就得到度量树;更一般地,R\mathbb{R}-树是一种度量空间,其中任意两点之间都由唯一一条弧连接,且这条弧与某个实数区间等距。

科学与计算应用

树(数据结构)以有根的层级结构存储相互关联的记录。搜索树用于组织键,堆支持优先级操作,字典树则按共同前缀组织字符串。这些结构的效率取决于额外的不变量,而不仅仅取决于它们是否为树。平衡二叉搜索树的高度与 log⁡n\log n 成正比,因此搜索和更新所需的比较次数为对数级;不平衡的树则可能退化为一条路径,使操作需要线性时间。相比之下,堆只对父节点与子节点之间的顺序施加约束,并不对所有键进行全局排序。文件系统通常以树的形式呈现,但链接和共享对象可能使其实际的引用结构成为更一般的图。

语法树表示表达式和程序的组成结构。对于表达式 (a+b)c(a+b)c,乘法节点可以将一棵加法子树和叶节点 cc 作为子节点。求值从叶节点向根节点推进,而变换则作用于子树。解析树保留语法推导的细节;抽象语法树则省略其中大量表层结构。树也可用于建模决策过程:内部节点指定测试条件,叶节点指定结果。在机器学习中,决策树通过连续的测试划分输入空间,而由多棵树组成的集成模型可以综合许多这样的划分。这些模型是否有效,取决于其构建和评估方式,而非仅仅取决于树形结构。

在进化生物学中,系统发育树表示对生物谱系或序列之间亲缘关系的假设。有根树明确祖先到后代的方向,无根树则只记录分支关系,不指定祖先。边长可以表示经过的时间,也可以表示预期的演化变化量,这两种解释不能互换。对于 n≥3n\geq 3 个带标签的末端分类单元,无根完全二叉树的拓扑结构共有 (2n−5)!!(2n-5)!! 种;对应的有根树则有 (2n−3)!!(2n-3)!! 种。这一搜索空间的迅速增长是系统发育推断中的核心计算问题。杂交和基因水平转移等过程可能需要用网络来表示,而不能仅用一棵树描述。

当所有站点都必须连通且不能出现路由环路时,通信网络和公用设施网络会采用树结构。生成树可以从物理上具有冗余连接的网络中选取一种无环的转发结构,多播树则组织从一个源向多个接收方的数据传送。当可用的顶点和边固定时,最小生成树使边的总权重最小。斯坦纳树问题则有所不同:它允许增加连接点;在图上的版本中,则只要求连通指定的终端顶点子集。这些区别很重要,因为表面上相似的网络图可能代表不同的优化问题。

树也用于数据压缩和分枝过程建模。霍夫曼编码将符号分配给二叉树的叶节点,由根到叶的路径给出无前缀二进制码字;符号的概率决定最优树,使二进制前缀码的期望码字长度最小。在分枝过程中,顶点表示个体,子节点的数量描述繁殖情况。对于初始个体数为一、后代数量服从非退化分布的高尔顿–沃森过程,当平均后代数不大于一时,种群以概率一灭绝;当平均后代数大于一时,种群则有正概率永久存续。在这里,树是随机的,其形态记录了种群增长的完整历史。