二叉树

解题时的二叉树分类：满二叉树和完全二叉树。

满二叉树：只有度为0和度为2的结点，且所有度为零的结点都在二叉树的同一层。而对于深度为k的满二叉树，其结点个数为2^k-1。

完全二叉树：只有最底层可能没有被填满，其余每层的结点数都达到了最大值，而最底层(第k层)可能包含的结点数为1-2^(k-1)。而完全二叉树中最底层的结点必须是从左到右添加的，若最底层的叶子节点的位置中，某个位置没有结点，而该位置的右侧仍然有叶子节点，则表明该树不是完全二叉树。

二叉搜索树：二叉搜索树中的每个结点都是有数值的，所以二叉搜索树是一个有序树。

根节点的左子树上的结点的值均小于根节点的值，根节点的右子树上的结点的值均大于根节点的值。而这个原则在二叉搜索树的左右子树上仍然递归成立。

平衡二叉搜索树(AVL)：它是一个空树或其左右两个子树的高度差的绝对值小于等于1。且其左右子树也递归满足这一要求。

二叉树的存储方式：既可以通过链式存储(指针)实现，也可以通过顺序存储(数组)实现。使用顺序存储实现时，若父节点的下标为i，则其左孩子结点的下标为2*i+1，其右孩子节点的下标为2*i+2。而链式存储二叉树是更常见的方法。

二叉树的遍历方式：二叉树的遍历方式包括：深度优先遍历和广度优先遍历两种。而前序中序后序遍历属于深度优先遍历，层序遍历属于广度优先遍历。前序中序后序遍历的区别在于，遍历时中间结点相对于其左右孩子节点的位置。中左右为前序遍历，左中右为中序遍历，左右中为后序遍历。

二叉树的递归遍历：

在写递归算法时需要注意的三要素：①确定递归参数和返回值，②确定终止条件，③确定单层递归的逻辑。

二叉树的迭代遍历：利用了栈对二叉树进行遍历。