数据结构树--＞树基础_除尾节点,每一个节点有且只有一个

目录

1. 数据结构树–>树基础
2. 数据结构树–>二叉树
3. 数据结构树–＞二叉查找树\二叉排序树
4. 数据结构树–＞平衡二叉树
5. 数据结构树–＞霍夫曼树
6. 数据结构树–＞红黑树
7. 数据结构树–＞二叉堆
8. 数据结构树–＞B树
9. 数据结构树–＞B+树

树基础

1. 定义

树 是 n(n>=0) 个有限节点组成的具有层次关系的集合，当 n=0 时称为空树。树很多人有很多定义，其实满足树的特点就称之为树。

特点：

1. 有且仅有一个特定的节点称为根节点。
2. 每个节点有0个或多个子节点。
3. 每一个非根节点有且只有一个父节点。
4. 除根节点外，每个子节点可以分为多个不想交的子树。

如图：

如图明确几个名词：

1. 节点：树的所有点称之为节点，如上图的圆圈。
2. 根节点，头部第一个节点。
3. 叶子节点： 4 5 6 7 处于树的末端，称为叶子节点。
4. 孩子节点： 节点关系， 4节点属于2节点的孩子节点。
5. 父节点：节点关系，对应孩子节点，2节点属于4节点的父节点
6. 兄弟节点：节点关系，同一父节点的所有节点都是相互的兄弟节点。
7. 叔叔节点：节点关系， 本身节点的父节点的兄弟节点为叔叔节点。
8. 祖父节点：节点关系，父节点的父节点称之为祖父节点。
9. 层： 途中 1行数据属于一层。 1 为1层， 2、3属于1层 ， 4、5、6、7属于一层。
10. 节点深度：从根节点到该节点的层级数就是该节点的深度。
11. 树的高度：叶子节点的最大深度就是树的高度。

2. 树的分类

3. 详解介绍

关于树的类型有很多中，我们在使用过程中常见的有。

1. 一般二叉树
2. 完全二叉树–满二叉树
3. 二叉排序树
4. 平衡二叉树、霍夫曼树(AVL树)
5. 红黑树
6. 二叉堆(最大堆，最小堆)
7. B树 (B+树、B*树)