树
- 定义
- 树：是一种抽象数据类型或是视作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。
- 特点
- 每个节点有零个或多个子节点
- 没有父节点的节点称为根节点
- 每一个非根节点有且只有一个父节点
- 除根节点外，每一个子节点可以分为多个不相交的树
- 树的术语
- 节点的度：该节点上直接子节点的个数
- 树的度：一颗树中，最大节点的度称为树的度
- 叶节点或终端节点：度为零的节点
- 父节点：若该节点含有子节点，那么这个节点就是子节点的父节点
- 子节点：意义同上
- 兄弟节点：具有相同父节点的子节点的节点称为兄弟节点
- 节点的层次：从根节点开始定义，根节点的子节点为第一层，根节点的子节点的子节点为第二层
- 树的高度：树中节点的最大层次
- 堂兄弟节点：在同一层次上的节点
- 节点的祖先：从根节点开始到该节点所经过的所以节点
- 子孙：该节点下的所有的节点
- 森林：由m(m>=0)棵互不相交的树的集合称为森林
- 树的种类
- 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树
- 有序树：树中任意节点的子节点之间由顺序关系，这种树称为有序树
- 二叉树：每个节点最多含有两个子节点的树称为二叉树
- 完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其他各层的节点数目均已达到最大值。且第d层所有的节点从左到右连续紧密排列，这样的二叉树被称为完全二叉树
- 平衡二叉树(AVL树)：当且仅当任何节点的两颗子树的高度不大于1的二叉树，称为平衡二叉树。
- 排序二叉树：二叉查找树；二叉搜索树
- 霍夫曼树(用于信息编码)：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
- B树：一种对读写操作进行优化的自平衡的二叉树，能够保持数据有序，拥有多余两个子树
- 二叉树：每个节点最多含有两个子节点的树称为二叉树
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 zoubinbf@163.com
