Tree
树是一种数据结构，由n(>=0)个有限节点Node组成的一个具有层次关系的集合。
树的特点
- 每个子节点都只有有限个子节点或无子节点。
- 没有父节点的节点称为
根节点(root)。 - 每一个非根节点
有且仅有一个父节点。 - 除了根节点每个子节点可以分为多个
不相交的子树。 - 树里面没有环路。
术语
- 节点的度(Degree):
For a given node, its number of children. A leaf is necessarily degree zero.
给定节点的子树的个数。 - 树的度(Degree)
树中最大节点的度称为树的度 - 兄弟节点
具有相同父节的节点互称兄弟节点 - 堂兄弟节点
父节点在同一层次的节点
树的种类
1.无序树(又称自由树)：树中任意节点的子节点之间没有顺序关系。
自由树就是一个无回路的连通图，没有确定根，在自由树种选取一个顶点做根，成为一个通常的树。
2.有序树：树中任意节点的子节点之间有顺序关系。
- 有序树
-
二叉树 Binary tree：每个节点最多含有两个子树的树称为二叉树。
- 完全二叉树：一个二叉树的深度为d,除了d层外，其他各层的节点数目均达到最大值。
- 满二叉树：所有叶节点都在最底层的完全二叉树
- 平衡二叉树（ALV树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树。
- 排序二叉树（又称二叉查找树、二叉搜索树，有序二叉树）
- 霍夫曼树（Huffman Coding又称哈夫曼树或最优二叉树）：带权路径最短的二叉树。霍夫曼编码使用变长编码表对源符号进行编码，典型应用图文压缩。
- B树 一种对写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。典型应用mysql索引。
- 红黑树，应用于jdk TreeSet中，是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
-
