树的介绍

---

---

树是一种离散结构，它表示各个元素或节点之间层次结构的关系。其中父节点最多只有两个子节点的树称为二叉树。

树及其性质

定义 - 树是一个连通的无环无向图。图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) ≤ Value(V)
• 顶点V的右子树中的Y，Value(Y) ≥ 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)  

二叉搜索树的复杂度