# 二叉树

### 树的基本概念

1. **父节点**：在树结构中，每一个节点只有一个前件，称为父节点，没有前件的称为根节点，简称树的根。
2. **子节点和叶子节点**：在树结构中每一个结点可以有多个后件，称为该结点的子节点，没有后件的节点称为叶子节点。
3. **度**：在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。
4. **深度**：定义一棵树的根结点所在的层次为1，其他结点所在的层次等于它的父结点所在的层次加1。树的最大层次称为树的深度。
5. **子树**：在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。

### 二叉树的6个重要性质

1. 二叉树（Binary Tree）：是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两棵互不相交的左、右二叉子树构成；
2. 二叉树的特点是：（1）二叉树可以为空，空的二叉树没有结点，非空二叉树有且只有一个根结点；（2）每个结点最多有两棵子树，即二叉树中不存在度大于2的结点。（3）二叉树的子树有左右之分，其次序不能任意颠倒；

### 满二叉树和完全二叉树

满二叉树：指除了最后一层外，每一层上的所有结点都有两个子结点的二叉树；

满二叉树在其第i层上有2(i-1)（上角标）个结点，即每一层上的结点数都是最大结点；

一棵深度为K的满二叉树，整颗二叉树共有2（K）（上角标）-1个结点；

完全二叉树：指除最后一层外，每一层上的结点树均达到最大值，在最后一层上只缺少右边的若干结点。

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树；

完全二叉树的叶子结点只可能在最后两层出现；

对于任一结点，若其右子树的深度为m，则该结点左子树的深度为m或为m+1；

### 二叉树的基本性质

1. 在二叉树的第K层上，最多2^(k-1)（k>=1）个结点。
2. 深度为K的二叉树中，最多有2^(k-1)个结点；
3. 对任何一颗二叉树，度为0的结点总是比度为2的结点多一个；
4. 具有n个结点的二叉树，其深度至少为\[log2 n]+1，其中\[log2 n]表示取其中的整数部分；
5. 具有n个结点的完全二叉树的深度为\[log2 n]+1；
6. 设完全二叉树共有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2，3……n给结点进行编号，有以下结论：
   1. 若i=1，则该结点为根结点，它没有父结点；若i>1,则该结点的父节点编号为\[i/2]，其中结果只取整数部分；
   2. 若2i>n，该结点无左子结点也无右子结点；若2i<=n,则编号为i的结点的左子结点编号为2i；
   3. 若2i+1>n,则该结点无右子结点；若2i+1<=n,则编号为i的结点的右子结点编号为2i+1；

注意：性质5和性质6是完全二叉树和满二叉树特有的；

### 二叉树的存储结构

左指针域+数据域+右指针域

由于二叉树每一个存储结点有两个指针域，因此二叉树的链式存储结构也称为二叉链表。对于满二叉树和完全二叉树可以按层次进行顺序存储；

### 二叉树的遍历

二叉树的遍历是指不重复地访问二叉树（非线性结构）中的所有结点。在先左后右的原则下，根据访问根结点的次序不同，二叉树的遍历可以分为3种：前序遍历、中序遍历、后序遍历。

1. 前序遍历（DLR）：若二叉树为空，则空操作，否则访问根节点，然后前序遍历左子树，前序遍历右子树。（“前”的含义是，访问根结点在访问子树之前；）
2. 中序遍历（LDR）：访问根结点在访问左子树和访问右子树两者之间；
3. 后序遍历（LRD）：最后访问根结点；

注意：

已知一颗二叉树的前序遍历序列和中序遍历序列，可以唯一确定这棵二叉树；

已知后序和中序也可以，**但已知前序和后序则不行**；

{% tabs %}
{% tab title="First Tab" %}

{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}