1.二叉树的种类

题目类型主要分为满二叉树和完全二叉树

1.1 满二叉树

满二叉树：如果一棵二叉树只有度为0(没有子节点的结点，也称为叶子结点)的结点和度为2 （左子节点和右子节点）的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

深度为k，有2^k-1个节点的二叉树。 (如图所示，有 2^4 - 1 = 15 个节点)

1.2 完全二叉树

完全二叉树是指除最后一层外，其余各层节点数均达到最大值（即每层节点数为 2^(i−1)，i 为层数），且最后一层的节点全部集中在该层最左边的连续位置。若最底层为第 h 层，则该层节点数满足 1≤节点数≤2^(h−1)

1.3.二叉搜索树

满二叉树和完全二叉树是没有数值的，但是二叉搜索数存在数值，并且是一个有序的树

  • 特点：

    • 左子树不为空，则左子树上所有结点的值都小于根节点的值

    • 右子树不为空，则右子树上所有结点的值都大于根节点的值

    • 左右子树也分别为二叉排序树

1.4.平衡二叉搜索树 AVL（Adelson-Velsky and Landis）

性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

如图所示，第一棵树高度差为：左 2 - 右 1 = 1，第二颗树：左 2 - 右 2 = 0 ，第三棵数：左 2 - 右 0 = 2> 1

2.二叉树的存储方式

链式存储（指针）和顺序存储（数组）

链式存储如图：

顺序存储：

顺序存储中，如果父节点的数组下标是 i，那么它的左孩子就是 i*2 + 1，右孩子就是 i *2 + 2。

3.二叉树的遍历方式

3.1 深度优先遍历（递归）

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

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

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

3.2 广度优先遍历

层次遍历（迭代法）

4.二叉树的定义（Python）


class TreeNode:
    def __init__(self, x):
        self.val = x      # 节点存储的值
        self.left = None  # 左子节点，默认为 None
        self.right = None # 右子节点，默认为 None