数据结构树--＞树基础
目录
树基础
1. 定义
树 是 n(n>=0) 个有限节点组成的具有层次关系的集合，当 n=0 时称为空树。树很多人有很多定义，其实满足树的特点就称之为树。
特点：
- 有且仅有一个特定的节点称为根节点。
- 每个节点有0个或多个子节点。
- 每一个非根节点有且只有一个父节点。
- 除根节点外，每个子节点可以分为多个不想交的子树。
如图：
如图明确几个名词：
- 节点：树的所有点称之为节点，如上图的圆圈。
- 根节点，头部第一个节点。
- 叶子节点： 4 5 6 7 处于树的末端，称为叶子节点。
- 孩子节点： 节点关系， 4节点属于2节点的孩子节点。
- 父节点：节点关系，对应孩子节点，2节点属于4节点的父节点
- 兄弟节点：节点关系，同一父节点的所有节点都是相互的兄弟节点。
- 叔叔节点：节点关系， 本身节点的父节点的兄弟节点为叔叔节点。
- 祖父节点：节点关系，父节点的父节点称之为祖父节点。
- 层： 途中 1行数据属于一层。 1 为1层， 2、3属于1层 ， 4、5、6、7属于一层。
- 节点深度：从根节点到该节点的层级数就是该节点的深度。
- 树的高度：叶子节点的最大深度就是树的高度。
2. 树的分类
3. 详解介绍
关于树的类型有很多中，我们在使用过程中常见的有。
- 一般二叉树
- 完全二叉树–满二叉树
- 二叉排序树
- 平衡二叉树、霍夫曼树(AVL树)
- 红黑树
- 二叉堆(最大堆，最小堆)
- B树 (B+树、B*树)
