二叉树的理论基础

二叉树的种类

满二叉树：如果一棵树只有度(表示节点拥有的子节点数)为0的结点和度为2的节点，并且度为0的节点在同一层上

完全二叉树：在完全二叉树中，除了底层节点可能没有填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若底层为第h层（h从1开始），则该层包含1~2^（h-1）个节点。

二叉搜索树：它是一个有序数。

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。left.val < root.val

若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值。right.val > root.val

它的左、右子树也分别为二叉排序树

二叉树的存储方式

链式存储使用指针，顺序存储使用数组

用数组存储如何遍历：

若父节点的数组下标是i,那么左孩子是 i*2+1,右孩子是1*2+2

二叉树的遍历方式

深度优先遍历

前中后指的是中间节点的位置

前序遍历（递归法，迭代法）：

中序遍历（递归法，迭代法）

后序遍历（递归法，迭代法）

广度优先遍历

层序遍历（迭代法）一般使用队列来实现

二叉树的定义

二叉树的定义和链表差不多，相对于链表，二叉树的节点里多了一个指针，其有两个指针，指向左右孩子。

二叉树的递归遍历

递归三要素：

1.确定递归函数的参数和返回值

2.确定终止条件

3.确定单层递归的逻辑

二叉树的前序遍历

递归遍历 迭代遍历 统一迭代

二叉树的后序遍历

递归遍历

前序遍历是中左右，后序遍历是左右中，把后序遍历反转一下，你发现是中右左，因此我们自遍历的时候按照前序遍历的那样，只不过先要将左孩子放入，再放右孩子，最终返回结果的时候直接反转

迭代遍历 统一迭代

二叉树的中序遍历

递归遍历 迭代遍历 统一迭代