主要记录一下对于二叉树，进行遍历的几种方式，包括： 前序遍历 中序遍历 后序遍历 深度优先遍历 广度优先遍历 我们以下面的这个二叉树结构为例，分别描述一下这几种遍历的方式有什么不同，以及给出java实现的代码。

基于《算法》一书的红黑树的插入和删除。看过不同的教材，也有不同的实现方式，但是最终的结果也大致相同，感觉这个比较容易理解，就采用这种的方式来进行简单实现。 定义树节点的实体类型 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 private static final boolean RED = true; private static final boolean BLACK = false; /** * 红黑树的节点结构 * 保存的值，左节点，右节点以及颜色(true为红色，false为黑色) * 默认添加一个红节点 * * @param <E> */ static final class RedBlackTreeNode<E extends Comparable<E>> { E val; RedBlackTreeNode<E> left; RedBlackTreeNode<E> right; boolean color = RED; RedBlackTreeNode(E val) { this.val = val; } } 这里简单的定义了一下红黑树，并且只有节点，并不是map这样的k-v结构。如果定义k-v结构到时比较的时候比较k即可。 用了泛型，并且要支持比较(继承自Comparable)，不然无法比较大小进行插入。 然后定义了一个值，左节点和右节点，然后颜色默认为红色。 再增加一个构造函数即可

题目来源 今天做了个题： 将一个链表里的数据组装树形结构，链表里的数据已经满足树形结构要求 这道题描述的很简单，但是有很多种情况。他只说了链表数据满足树形结构要求，并没有说明数据到底是什么样的，也就是题目参数具有多样性，这样其实我们给出一种解决方案就可以。而且也只要求将链表转换为树，并没有说是什么树。所以这道题说难也难，说简单也简单。 解题思路 最近也将平衡二叉树的原理看了一下，正好借着这道题将代码手写一下。 我写了一个平衡二叉树的插入方法。我们不管链表里面的数据是如何排序的，我们只要调用树的插入方法即可。在插入方法内部实现树的平衡。 所以我们这道题也就转换成了手写平衡二叉树的插入过程。

二叉树 定义 二叉树由节点的有限集合构成 这个有限集合或者为空集 或者为由一个根节点(root)及两棵互不相交、分别称为这个根的左子树和右子树的二叉树组成的集合 在 java 中用代码定义为： 1 2 3 4 5 6 7 8 class TreeNode { Object val; TreeNode leftNode; TreeNode rightNode; ... } 性质 在二叉树中，第 i 层上最多有2^i^ 个节点(i>=0) 深度为 k 的二叉树至多有2^k+1^-1个节点(k>=0) 有 n 个节点的完全二叉树的高度为 log2(n+1) 它主要有五种基本形态： 满二叉树 定义：除最后一层无任何子节点外，每一层上的所有节点都有两个子节点的二叉树。 大体的意思就是：一颗二叉树的节点要么是叶子节点（也就是最后一层），要么它就要有两个子节点。如果这个二叉树的层数为 k，且节点总数是(2^k^-1)，则它就是满二叉树。 完全二叉树 定义：设二叉树的深度为 k，除第 k 层外，其他各层(1~(k-1)层)的节点都都达到最大值，其第 k 层所有的节点都连续集中在最左边，这样的树就是完全二叉树 这些是二叉树的一些基本定义以及变形，它对于数据的存储并没有要求，只是要求了结构。所以对于实际应用中还存在很多的不足，比如对于一个 n 个节点的树，判断一个节点是不是在树里面，它的复杂度还是 o(n)。所以我们下面介绍几种对于存储有要求的树。