二叉树相关知识

1.二叉树的种类

二叉树有两种形式：满二叉树和完全二叉树

2.满二叉树

如果一棵二叉树只有度为0的结点和度为2的结点，且度为0的结点在同一层，则这棵树称为满二叉树。

满二叉树深度为k，结点有2^k-1个。

3.完全二叉树

在完全二叉树中，除最底层没有填满外，其余各层结点数都达到了最大值，并且最下面一层的结点都集中在左边。

完全二叉树最底层为h层，则该层包括 1 - 2h 个结点。

堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

4.二叉搜索树

二叉搜索树是一个有序树。

• 若左子树不为空，则左子树的所有结点的值均小于根结点的值；
• 若右子树不为空，则右子树的所有结点的值均大于根结点的值；
• 左右子树也都是二叉排序树。

5.平衡二叉搜索树（AVL）

平衡二叉搜索树是一棵空树或它的左右子树的高度差的绝对值不超过1，并且左右子树均为平衡二叉树。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn；unordered_map、unordered_map底层实现是哈希表。

6.二叉树的存储方式

二叉树可以链式存储也可以顺序存储。

链式存储使用指针，通过指针把分布在各个地址的结点连在一起，其存储结构如下图所示：

 顺序存储使用数组，存储的元素在内存中连续分布，其存储结构如下图所示（可从0开始）。

 数组遍历二叉树：如果从1开始，父节点为i，他的左孩子就是2*i，右孩子就是2*i+1；如果从0开始，父节点为i，他的左孩子就是2*i+1，右孩子就是2*i+2。

7.二叉树的遍历方式

二叉树有两种遍历方式：深度优先遍历和广度优先遍历。

• 深度优先遍历：先往深处走，遇到叶子节点在往回走。
• 广度优先遍历：一层一层进行遍历。

深度优先遍历和广度优先遍历进行拓展，有以下遍历方式：

深度优先遍历：

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

 广度优先遍历：

• 层次遍历（递归法，迭代法）

 深度优先遍历使用递归比较方便，而栈又是一种递归结构，所以使用栈实现深度优先遍历。

广度优先遍历一般使用队列来实现，这是由队列先进先出的特点决定的。

8.二叉树的定义

//链表方法定义
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL){}
};