回顾下数据结构的八大类
- 数组
- 栈
- 队列
- 链表
- 树
- 散列表
- 堆
- 图
本篇文章就准备聊聊 树 的相关知识，废话不多说，开搞！
树的定义
树是一种 非线性 的数据结构，它是由n（n>=1）个有限节点组成一个 具有层次关系 的集合
把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的
树的特点
树通常具有以下特点
- 每个节点都只有 有限个 子节点或 无 子节点
- 没有父节点的节点称为 根节点
- 每一个非根节点 有且只有 一个父节点
- 除了根节点外，每个子节点可以分为多个不相交的子树
- 树里面 没有 环路，意思就是从一个节点出发，除非往返，否则不能回到起点
树的种类
树有许多种类，列举如下
- 无序树：树的任意节点的子节点之间没有顺序关系
- 有序树：树的任意节点的子节点之间有顺序关系
- 二叉树：树的任意节点至多包含两棵子树，它分为以下子类
- 满二叉树：叶子节点都在 同一层 并且除叶子节点外的所有节点 都有 两个子节点
- 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除第d层外的所有节点构成满二叉树，且第d层所有节点 从左向右连续地 紧密排列
- 完满二叉树：除了叶子节点，其余的所有节点都有两个子节点。与满二叉树不同的是，完满二叉树 不需要 叶子节点在同一层
- 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树
- 二叉搜索树
- 平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树
- 红黑树：红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色
- B-tree
- B+树
- 字典树
由此可见，树的种类多是由二叉树演变而来
结语
其实对于树这种数据结构，我自己都还不是掌握得特别熟练，也还是在一个学习的过程中，所以本篇文章与君共勉！
