1. 为什么需要树这种结构？

数组存储方式解析：

1. 优点：通过下标方式访问元素，速度快，对于有序数组还可以使用二分查找提高检索速度。
2. 缺点：如果要检索具体某个值，或者插入值会整体移动，效率较低。

树的存储方式分析： 能提高数据存储，读取的效率，比如可以使用二叉树既可以保证数据检索速度，同时也可以保证数据的插入，删除，修改的速度。

2. 二叉树

2.1 二叉树概念

二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能由两颗子树，而且由左右之分。

2.2 树示意图

常用术语：

• 节点
• 根节点
• 父节点
• 子节点
• 叶子节点(没有子节点的节点)
• 节点的权(节点值)
• 路径(从root节点找到目标节点的线路)
• 层
• 子树
• 树的高度(最大层数)
• 森林(多个子树构成森林)

2.3 二叉树介绍

1. 树有很多种，每个节点最多只能有两个子节点的一种形式称之为二叉树。
2. 二叉树分为左节点和右节点。

3. 如果该二叉树的所有叶子节点都在最后一层，并且节点总数是 2^n-1，n 是层数，则我们称之为满二叉树。

4. 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称之为完全二叉树。

2.4 二叉树应用案例

可以使用前序，中序，后序对下面的二叉树进行遍历

1. 前序遍历：先输入父节点，再遍历左子树和右子树
2. 中序遍历：先遍历左子树，再遍历父节点，再遍历右子树
3. 后续遍历：先遍历左子树，再遍历右子树，最后遍历父节点

结论：看父节点输出顺序即使某序遍历。

3. 顺序存储二叉树

3.1 顺序存储二叉树概念

二叉树的顺序存储就是用一组连续的存储单元(数组)存放二叉树中的节点元素，一般按照二叉树节点自上向下，自左向右的顺序存储。

顺序存储二叉树的特点：

1. 顺序二叉树通常只考虑完全二叉树
2. 第 n 个元素的左子节点为 2*n + 1
3. 第 n 个元素的右子节点为 2*n + 2
4. 第 n 个元素的父子节点为 (n-1)/2
5. n 表示二叉树中第几个元素，按编号从 0 开始

4. 线索化二叉树

在二叉树的节点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式(如前序，中序，后续等)进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。

对于 n 个节点的二叉树，在二叉链存储结构中有 n+1 个空链域，利用这些空链域存放在某种遍历次序下该节点的前驱节点和后继节点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

这种加上了线索的二叉链表称为线索链表，相应的二叉树成为线索二叉树。根据线索性质的不同，线索二叉树可分为前序线索二叉树，中序线索二叉树后后续线索二叉树三种。

一个节点的前一个节点，称之为前驱节点，一个节点的后一个节点称之为后继节点。