树木简介

---

树是一种离散结构，表示各个元素或节点之间的层次关系。父树不超过两个子树的树称为二叉树。

树及其属性

定义- 树是一个连接的非循环无向图。$G$ 中的每对顶点之间都有一条唯一的路径。具有 N 个顶点的树包含 $(N-1)$ 条边。0度的顶点称为树的根。度为 1 的顶点称为树的叶节点，内部节点的度至少为 2。

示例- 以下是树的示例 -

树的中心和双中心

树的中心是偏心率最小的顶点。树 $G$ 中顶点 $X$ 的偏心率是顶点 $X$ 与树的任何其他顶点之间的最大距离。最大偏心率是树的直径。如果一棵树只有一个中心，则称为中心树；如果一棵树只有多个中心，则称为双中心树。每棵树要么是中心树，要么是双中心树。

查找树的中心和双中心的算法

步骤 1 - 从给定的树中删除所有 1 度的顶点，并删除它们的关联边。

步骤 2 - 重复步骤 1，直到留下单个顶点或由边连接的两个顶点。如果留下单个顶点，则它是树的中心，如果留下由边连接的两个顶点，则它是树的双中心。

问题1

找出以下树的中心/双中心 -

解决方案

首先，我们将删除所有 1 度的顶点，并删除它们的关联边，得到以下树 -

同样，我们将删除所有 1 度的顶点，并删除它们的关联边并得到以下树 -

最后我们得到了一个顶点“c”，我们停止了算法。由于只有单个顶点，因此这棵树有一个中心“c”，并且该树是一棵中心树。

问题2

找出以下树的中心/双中心 -

解决方案

首先，我们将删除所有 1 度的顶点，并删除它们的关联边，得到以下树 -

同样，我们将删除所有 1 度的顶点，并删除它们的关联边并得到以下树 -

最后，我们剩下两个顶点“c”和“d”，因此我们停止算法。由于留下了由边连接的两个顶点，因此该树具有双中心“cd”并且该树是双中心的。

标记树

定义- 带标签的树是一棵树，其顶点被分配了从 1 到 n 的唯一编号。我们可以手工对 n 值较小的树进行计数，从而推测出一个通用公式。n 个顶点的标记树的数量为 $n^{n-2}$。如果两个标记树的图是同构的并且两棵树的对应点具有相同的标记，则它们是同构的。

例子

未标记的树木

定义- 未标记的树是其顶点未分配任何数字的树。n 个顶点的标记树的数量为 $\frac {(2n)!}{ (n+1)!n! }$（第 n^个加泰罗尼亚语数字）

例子

有根的树

有根树 $G$ 是一个连通的无环图，具有称为树根的特殊节点，并且每条边都直接或间接源自根。有序有根树是每个内部顶点的子节点都是有序的有根树。如果有根树的每个内部顶点的子节点数不超过 m，则称为 m 叉树。如果有根树的每个内部顶点恰好有 m 个子节点，则称为满 m 叉树。如果$m = 2$，则有根树称为二叉树。

二叉搜索树

二叉搜索树是满足以下属性的二叉树 -

• 顶点 $V 的左子树中的 $X$，Value(X) \le Value (V)$
• 顶点 $V 的右子树中的 $Y$，Value(Y) \ge Value (V)$

因此，内部节点$V$的左子树的所有顶点的值都小于或等于$V$并且内部节点$V$的右子树的所有顶点的值大于或等于 $V$。从根节点到最深节点的链接数就是二叉搜索树的高度。

例子

在 BST 中搜索密钥的算法

BST_Search(x, k) 
if ( x = NIL or k = Value[x] ) 
   return x; 
if ( k < Value[x]) 
   return BST_Search (left[x], k); 
else  
   return BST_Search (right[x], k)  

二叉搜索树的复杂度