树

定义

树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；

名词解析

结点的度：一个结点含有的子结点的个数称为该结点的度；
叶结点或终端结点：度为0的结点称为叶结点；
非终端结点或分支结点：度不为0的结点；
树的度：一棵树中，最大的结点的度称为树的度；
树的高度或深度：树中结点的最大层次；
森林：由m（m>=0）棵互不相交的树的集合称为森林；

种类

无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树;
有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树；
二叉树：每个节点最多含有两个子树的树称为二叉树；
满二叉树：叶节点除外的所有节点均含有两个子树的树被称为满二叉树
完全二叉树：有（2的k次方减一）个节点的满二叉树称为完全二叉树
哈夫曼树（最优二叉树）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

表示方法

图像表达法

符号表达法

用括号先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如前文树形表示法可以表示为

遍历表达法

遍历表达法有4种方法：先序遍历、中序遍历、后序遍历、层次遍历

其先序遍历（又称先根遍历）为ABDECF（根-左-右）
其中序遍历（又称中根遍历）为DBEAFC（左-根-右）（仅二叉树有中序遍历）
其后序遍历（又称后根遍历）为DEBFCA（左-右-根）
其层次遍历为ABCDEF（同广度优先搜索）

详解

无序树（自由树）

自由树就是一个无回路的连通图（没有确定根，在自由树中选定一顶点做根，则成为一棵通常的树）。从根开始，为每个顶点（在树中通常称作结点）的孩子规定从左到右的次序，则它就成为一棵有序树。

二叉树

二叉树是指满足以下要求的树：

• 它可以没有根结点，作为一棵空树存在
• 如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。如下图：

注意⚠️：在二叉树中，左右子树的位置是严格约定、不能交换的