1.前言

      除了传统的那些数据结构，例如，线性表，栈，队列，串，数组，链表这些数据结构，但是还有一些情况下，比如说查找，插入，另外一种数据结构会更有优势那就是树，这是一种最复杂的数据结构

2 普通的树

      一般用三种表示方式(存储方式)，分别是双亲表示法，孩子表示法，孩子兄弟表示法

        第一种，双亲表示法可用数组或者链表(其实链表肯定行的啦)表示，数组中每一个元素有俩个参数分别是本身的数据值，和双亲的位置

        第二种，孩子表示法，首先把元素放进数组中，数组每一项依旧是两个参数，如果有孩子，那么节点中的那个位置值(或者说指针)存放第一个孩子的位置，若还有第二                                个孩子，第一个孩子的位置值指向第二个孩子，直到没有为止，数组的下一项(第二个节点)也是，这是一个指向的孩子链

        第三种，孩子兄弟表示法，也就是一个节点有三个参数，一个是数据值个两个指针，指向第一个孩子和右兄弟，这样一来，就成了二叉树

3 二叉树

        二叉树是指有少于或者等于两个子树的树，每一个节点的下方不是一定都是两棵子树，有一颗或者一些节点没有子树也是可以的

树中的一个完美的特例是满二叉树，也就是每一行都满了，假如有n层，那么有2的n次-1个节点，2的n-1次方个叶子

        我们经常说的完全二叉树就是按照满二叉树的顺序填满或者没填满，编号从第一层开始从上到下，每一层从左到右编号，
第一层1二层23三层4567~~~ 完全二叉树由于其结构的特殊性，可以用数组(顺序存储)链表都可以表示，
不过普通的二叉树就不太适合，还是链表好，直接用指针指向下一个节点，清晰明了,  一般，节点的内容是，一个data和两个指针，分别指向两棵子树

        我们常说二叉树的前序遍历，中序遍历，后序遍历，还有一种叫层序遍历,(一层一层的遍历)，为什么要有这么多种遍历方法呢，是因为在编程的时候，程序要去访问二叉树，电脑只会循环，判断，因此研究出这些遍历方法，是为了帮助电脑遍历二叉树的

        简单说其中一种，中序遍历，这个中是访问根节点的顺序，中序遍历，那就是先访问左子树，再访问根节点，最后访问右子树，如果左孩子还有孩子节点，那么先访问左孩子节点，若还有下一层，那么就是递归了，左中右的顺序，（各种遍历的真正的意义：二叉排序树，左孩子比父亲小，有孩子比父亲大，如果使用中序遍历，那么出来的访问顺序就是，从小到大的顺序）

        二叉树的建立和遍历都是用递归的方式来做的，在建立一棵二叉树的时候，每个节点有三个成员，分别是数据，data，左右子树的指针，可以看出，每个叶子的这两个指针都荒废了，还有一些节点浪费了其中一个指针，对于追求效率的编程理念来说，这是不允许的，因此要把他利用起来

       这个时候，线索二叉树应运而生！！！我们知道，二叉树在其中一个节点要找到左右子树非常简单，但是如果像传统的双向链表那样找到前驱和后继，不容易，必须要再遍历一次，这样就不方便了，正好把叶子的浪费的这些空间给利用上，一举两得！！

       好的，那么就那中序遍历来说，如果指向右子树的指针为空，那么就把它指向后继，因为本来右子树就是他的后继(下一个要访问的位置)，把指向左子树的空指针指向他的前驱，这样的话，所有节点的前驱后继都可以马上找到了，(边界除外)，这样的话由于两个指针都有值了，其实线索二叉树就变成了双向链表！！！！！！
不过，还有一个问题，那就是所有节点的两个指针都有值了，那么就不知道他指向的是子树还是后继，这个时候，只要给节点增加两个标志位即可，ltag rtag，0表示子树，1表示后继

       由于二叉树的表示比普通的树要简单的多，因此人们想出了用二叉树表示普通树的想法，把普通树转化为二叉树，其步骤为：右兄弟变右孩子，如果一个节点有两个以上的孩子那么把这些孩子连起来，除了第一个孩子，其他孩子和双亲的连线断开，这样原来的非第一个孩子就变成了第一个孩子(左孩子)的右孩子，这样就把普通树转化成了二叉树，相反，二叉树还原为普通数，把右孩子变成右兄弟
接下来说说把森林转成二叉树，其实也不难，首先把森林中的每一棵树转成二叉树，再把第二棵树开始以后的那些树，把根节点看成第一棵树根节点的右兄弟，这样把右兄弟变右孩子，成功！！！！！若要把二叉树转回森林，那么根节点必须要有右孩子，从根节点开始，根节点的右孩子如果还有右孩子，那就可可分解成三棵树，以此类推

      森林的遍历也不难，也就是遍历里边的每一棵树，比如说先序遍历一个森林，就是先序遍历第一课树，再先序遍历第二棵树以此类推

      下面说说一些实际应用中常用到的树(好吧应聘的时候可能会考到的)

         第一种，二叉排序树，也称二叉查找树首先是树中的节点是有序的，一般的做法是，根结点A的大小比左孩子B大，比右孩子C小，左孩子B的大小又比其左孩子(B的左孩子)大，比其右孩子小，这样构造二叉树的话，查找的时候就很方便了，最多查找的次数就是数的高度，比普通的穷尽查找要高的多，那么很自然就想到如果每个根结点只有一个孩子，每个孩子也就只有一个孩子，那么就跟但链表差不多了，这个时候最坏的情况是N个节点要查找N次,为了解决这个问题，我们很自然想到，那就规定每个节点都要有两个孩子，而且他们的各个子树的高度有差不多，这就是所谓的平衡二叉树

        第二种：平衡二叉树，在查找二叉树（或者二叉排序树）的基础上，每个点的左子树和右子树的差别小于1，我们说这棵树处于平衡状态，在每次插入新节点的时候后，如果差别超过1，那么就要调整，直到平衡为止，调整的方法再另一篇博文中http://blog.csdn.net/dalleny/article/details/38680653  这个时候，很多人都会觉得，平衡条件是子树高度差小于等于1，那么新插入节点时，很容易出现不平衡的的情况，调整太频繁，这个时候，为了解决这个问题，人们又提出了一种新的树~~~~红黑树

        第三种：红黑树  红黑树是一种特殊的二叉树，

红黑树有5条规则：1，节点不是红色就是黑色，2根节点为黑色，3红色节点的孩子节点必须为黑色，4，插入的节点必须为红色，5从根节点到任意一个叶子节点的黑结点的个数是一样的

这5条规则确保了红黑树子树之间的高度差不会出现一个是另一个的两倍，这样既可以降低调整的次数（每次插入最多三次），又可以实现比较不错的平衡，局部平衡，有一个说法：红黑树出现了以后，平衡树就被扔进了博物馆

       用于压缩算法的一种树~~~~哈夫曼树，也称最优二叉树，使用哈夫曼编码，可以缩短普通的编码长度，因而达到压缩的目的