数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学树的定义和性质
树是一种离散结构，表示各个元素或节点之间的层次关系。其中父节点最多只有两个子节点的树称为二叉树。
树及其性质
定义 − 树是一个连通的无环无向图。图G中每对顶点之间都存在一条唯一的路径。具有N个顶点的树包含(N-1)条边。度为0的顶点称为树的根。度为1的顶点称为树的叶子节点，内部节点的度至少为2。
示例 − 下面是一个树的示例：
树的中心和双中心
树的中心是偏心率最小的顶点。树G中顶点X的偏心率是顶点X与树的任何其他顶点之间的最大距离。最大偏心率是树的直径。如果一棵树只有一个中心，则称为中心树；如果一棵树有多个中心，则称为双中心树。每棵树要么是中心树，要么是双中心树。
带标签的树
定义 − 带标签的树是指其顶点被分配了从1到n的唯一编号的树。我们可以手动计算n较小值时的此类树的数量，以便推测一个通用公式。具有n个顶点的带标签树的数量是nn-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)
二叉搜索树的复杂度
| 平均情况 | 最坏情况 | |
|---|---|---|
| 空间复杂度 | O(n) | O(n) |
| 搜索复杂度 | O(log n) | O(n) |
| 插入复杂度 | O(log n) | O(n) |
| 删除复杂度 | O(log n) | O(n) |
更新于：2019年8月23日
14K+ 次浏览
广告