二叉树

二叉树是一种树形存储结构，每个节点最多有两个子节点，通常叫做左子树和右子树。

最顶部的节点称为根节点 ，在节点下方与该节点直接相连的节点叫做子节点，反过来称为父节点，没有子节点的称为叶子节点 ，从根节点到最底下的叶子节点经过的节点数就是树的高度，也就是树的最大层数。在上面的二叉树中，1是根节点，2和3是1的子节点，1是2的父节点，4，5，6，7是叶子节点，树的高度是3。

上面这个二叉树也称为满二叉树，因为它满足除最后一层以外，其它层的节点都有两个子节点，除了满二叉树，还有一种常提到的是完全二叉树，它的特点是除最后一层以外，其它层都是满的，最后一层要么是满的，要么就是右边缺若干个节点，下面这个就是完全二叉树。

还有一些经常能听到或者用到的二叉树，比如

• 二叉搜索树， 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值， 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值，它的左、右子树也分别为二叉排序树，是一种既能快速查找元素，又可以快速插入元素的数据结构，两种操作的平均时间复杂度为O(logN)。
• AVL树，一种高度自平衡的二叉搜索树，在树中任一节点对应的两棵子树的最大高度差为1，之所以要保持平衡，主要是防止二叉搜索树退化为链表，导致效率降低。
• 红黑树，也是一种自平衡的二叉搜索树，但是平衡度没有AVL树高，在红黑树中，从根节点出发到叶子节点的任何一条路径长度都不会超过其它路径的两倍。红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。红黑树在Java 中的TreeMap、HashMap、TreeSet中有应用。
• 哈夫曼树，又称最优二叉树，是一种带权路径长度最短的二叉树。树的带权路径长度（WPL）指的是，所有叶子结点的权值乘以该叶子结点到根节点的路径长度的总和。哈夫曼树的最主要应用是哈夫曼编码，一种能够实现编码总长度最短的二进制前缀编码。

还有一种树，虽然不是二叉树，但是也经常用到，那就是Trie树，又叫前缀树和字典树，可以用来高效的查找字符串。

关于二叉树，最基础的就是二叉树的遍历，二叉树常见的遍历有以下几种：

1. 前序遍历，先访问父节点，再访问左子节点，最后访问右子节点。
2. 中序遍历，先访问左子节点，再访问父节点，最后访问右子节点。
3. 后序遍历，先访问左子节点，再访问右子节点，最后访问父节点。
4. 层次遍历，从上到下，从左到右依次访问节点。

上面这棵树的几种遍历结果。

前序遍历：[1,2,4,5,3,6,7]
中序遍历：[4,2,5,1,6,3,7]
后序遍历：[4,5,2,6,7,3,1]
层次遍历：[1,2,3,4,5,6,7]

下面是二叉树几种遍历方式的Java代码实现，除了层次遍历外，都有递归和迭代的实现。