基本概念
树是一系列点组成的、具有层次结构的集合。
基本特点
- 每个节点有0或多个子节点
- 没有父节点的节点称为根节点（root）
- 每个非根节点有且仅有一个子节点
- 除了根节点，每个子节点可以分为多个不相交的子树
特定术语
- 节点的度：节点所含的子树个数（A-->3）
- 树的度：一棵树中，最大的节点的度（A-->3）
- 叶节点：子节点为0的节点（E、F、G、H、I、J）
- 兄弟节点：具有相同父节点的节点（BCD、EF、GH、IJ）
- 节点层次：从根节点开始，根为第一层，根节点的子节点为第二层，以此类推
- 深度：对于节点n，从根节点到n的唯一路径长（C-->1）
- 高度：对于节点n，从n到树叶节点的最长路径（A-->2）
- 森林：有n（n>0）棵互不相交的树组成的集合
image.png
树的分类
1、无序树
任意节点的子节点间是没有顺序的，也称自由树
2、有序树
任意节点的子节点间是存在顺序的
二叉树
每个节点中最多含有2个子节点的树称为二叉树。
2.1、完全二叉树
假设一棵树的深度为n（n>1），除了第n层以为，其余层数的节点数已达最大值，且若第n层有节点，则节点是从左到右依次排序的。
2.2、满二叉树
所有叶节点都在最底层的完全二叉树
2.3、平衡二叉树（AVL树）
当且仅当任何节点的两棵子树的高度差不大于2的二叉树
2.4、二叉查找树
具有以下特性的二叉树：
1.若任一节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
2.若任一节点的右子树不为空，则左子树上所有节点的值均大于它的根节点的值
3.若任一节点的子树也分别是二叉查找树
4.不存在键值相等的节点
2.4、红黑树
一种自平衡二叉树，典型的用途的实现关联数组。
哈夫曼树
带权路径最短的二叉树称为哈夫曼树或最优二叉树；B树
一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树
