树¶
树一种抽象类型数据，用来模拟具有树状结构性质的数据集合。它是由多个有限节点组成一个层次关系的集合。特点：
- 每个节点有0个或者多个子节点
- 没有父节点的节点称之为根节点
- 每个非根节点有且只有一个跟节点
术语¶
- 节点的度：一个节点含有的
子树的个数称为该节点的度 - 树的度：
最大的节点的度称之为数的度 - 叶结点或终端节点：
度为零的节点 - 父节点：含有子节点的节点上级
- 子节点：一个节点还有的子树的根节点称为该节点的子节点
- 兄弟节点：具有相同父节点的节点
- 节点的层次：根节点为第一层，其子节点为第二层，类推
- 树的高度或者深度：节点最大层次
- 堂兄弟节点：父节点在同一层次的节点
- 森林：由多个树互不相交的树的集合称为森林
树的种类¶
- 无序树：任意节点的子节点之间没有任何的顺序关系，称之为无序树，也叫自由树
- 有序树：子节点之间由顺序关系
- 二叉树：每个节点最多含有两个子树的树
- 完全二叉树：若一棵树的深度为d，除去第d层外，其他各层的节点数目达到了最大值，且第d层所有节点从左向右连续紧密的排列的二叉树
- 满二叉树：所有层的节点数达到了最大数
- 平衡二叉树：当且仅当任何节点之间的
两颗子树的高度差不大于1的二叉树 - 排序二叉树：二叉搜索树，二叉查找树，性质：任何节点左边的数比节点上的数小，右边比节点上的数大
- 霍夫曼树：用于信息编码
-
