二叉树理论

一、满二叉树与完全二叉树

在我们解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树。

二、二叉搜索数与平衡二叉搜索树

1、二叉搜索树

二叉搜索树是一种节点值之间具有一定数量级次序的二叉树，对于树中每个节点：

• 若其左子树存在，则其左子树中每个节点的值都不大于该节点值；
• 若其右子树存在，则其右子树中每个节点的值都不小于该节点值。

2、平衡二叉搜索树(AVL树)

AVL树满足以下要求：

• 左子树与右子树高度之差的绝对值不超过1
• 树的每个左子树和右子树都是AVL树
• 每一个节点都有一个平衡因子（balance factor），任一节点的平衡因子是-1、0、1（每一个节点的平衡因子 = 右子树高度 - 左子树高度）
  

三、二叉树的存储方式

二叉树的存储方式分为两种，链表存储和数组存储。一般是用链式存储二叉树。

1、链表存储

2、数组存储

在数组存储中，对于编号为i的节点，那么它的左孩子就是i * 2 + 1，右孩子就是i * 2 + 2。

四、二叉树的遍历方法

二叉树的遍历方法可以分为深度优先遍历和广度优先遍历两种。

• 深度优先遍历：先往深走，遇到叶子节点再往回走。
• 广度优先遍历：一层一层的去遍历

1、深度优先遍历

深度优先遍历分为：

• 前序遍历（递归法，迭代法）：按照中左右遍历
• 中序遍历（递归法，迭代法）：按照左中右遍历
• 后序遍历（递归法，迭代法）：按照左右中遍历
  这里的左中右分别指的是左子树，右子树，根节点；而x序遍历中的x即中在左，中，右中的排序位置。
  

2、广度优先遍历

即层次遍历 ：从上到下，一层一层的遍历二叉树
广度优先遍历一般使用队列来实现。

五、二叉树的定义

链式存储二叉树定义：

struct TreeNode {
	//数据结构
    int val;
    TreeNode *left;
    TreeNode *right;
    //构造函数
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};