二叉树

一、二叉树种类

• 满二叉树 二叉树只有度为2和0的节点，并且度为0的节点在同一层上，则这个二叉树是满二叉树。也就是每一层都是满的。
• 完全二叉树 除了最底层没填满，每一层都填满，并且优先填满最后一层的左节点。
• 完满二叉树 除了叶节点以外所有的节点都具有两个子节点。区别于上述两种二叉树
• 二叉搜索树（BST） 一个有序树，左子树上的所有数值一定小于根节点，右子树则反之所有节点都大于根节点。
• 平衡二叉搜索树（AVL） 一颗空树或者，他的左右两个子树的高度差绝对值不超过1，左右子树也分别是平衡二叉树。

二叉树可以采用链式存储结构也可以使用数组存储，使用数组进行表示适用于完全二叉树，别的二叉树会造成空间浪费

• 链式存储就是一个节点同时存储左子树和右子树。
• 数组存储用数组下标表示节点的序列，如果数组下标是i，其左孩子的序号就是2*i+1，右孩子的序号是2*i+2，父节点的序号是（i- 1）/2。

二、二叉树的遍历