整理自浙江大学数据结构MOOC
1. 树的定义
树：n(n≥0)个结点构成的有限集合。
n=0，称为空树
对于任意一颗非空树（n>0），具有以下性质：
- 树中有一个称为跟（Root）的特殊节点，用r表示
- 其余节点可分为m（m>0）个互不相交的有限集T1,T2,···,Tm, 其中每个集合本身优势一棵树，称为原来树的子树（SubTree）
树
2. 树的一些基本术语
- 节点的度（Degree）：节点的子树个数
- 树的度：树的所有节点中最大的度数
- 叶节点（Leaf）：度为0的节点
- 父节点（Parent）：有子树的节点是其子树的根节点的父节点
- 子节点（Child）：若A节点是B节点的父节点，则称B节点是A节点的子节点
- 兄弟节点（Sibling）：具有同一父节点的各个节点彼此是兄弟结点
- 路径和路径长度：从节点n1到nk的路径为一个节点序列n1，n2，···，nk，ni是ni+1的父节点。路径所包含边的个数为路径的长度
- 祖先节点（Ancestor）：沿树根到某一节点路径上的所有节点都是这个节点的祖先节点。
- 子孙节点（Descendant）：某一节点的子树中的所有节点是这个节点的子孙节点
- 节点的层次（Level）：规定根节点在1层，其他任一节点的层数是其父节点的层数+1
- 树的深度（Depth）:树中所有节点中最大层次。
3. 树的表示法
-
儿子-兄弟表示法
采用链表实现，每个节点有两个指针，第一个指针指向第一个子节点，第二个指针指向下一个子节点
儿子-兄弟表示法
将该图形旋转四十五度，可形成二叉树
二叉树链表
4. 二叉树的基本概念
- 二叉树T是一个有穷的节点集合。这个集合可以为空，若不为空，则它由根节点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。
-
二叉树的五种基本形态
image.png - 二叉树的子树有左右顺序之分
- 特殊二叉树
- 斜二叉树：每个节点均只有左子树或均只有右子树
-
完美二叉树（Perfect Binary Tree）或满二叉树（Full Binary Tree）：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
完美二叉树 -
完全二叉树（Complete Binary Tree）：满二叉树缺失倒数k项
完全二叉树
- 二叉树的几个重要性质
- 一个二叉树第i层的最大节点数为：2i-1 , i ≥1
- 深度为k的二叉树有最大节点总数为：2k-1 ,k≥1
- 对任何非空二叉树T，若n0表示叶节点的个数、n2是度为2的非叶节点的个数，那么两者关系满足：n0=n2+1
（可以用一个等式推导该结论，等式两边均为二叉树的边数，左边用所有节点-1表示，即除了跟节点，每个节点头上都有一个边；右边用不同节点对边数的贡献表示，即n0贡献为0，n1贡献为1，n2贡献为2）
n0+n0+n0-1=0n0+1n1+2*n2
5. 二叉树的存储结构
-
顺序存储结构
image.png
image.png -
链表存储
image.png
6. 二叉树的遍历
个人见解：1. 理解递归的顺序很重要！！！ 2. 先中后说的是根的位置
1. 先序遍历（根左右）
image.png
2. 中序遍历（左根右）
image.png
3. 后序遍历（左右根）
image.png
技巧
image.png
7. 层序遍历
image.png
image.png
