2.11.1树
“树”这种数据结构，很像现实生活中的“树”，这里的每个元素叫做“节点”，用来连接相邻节点之间的关系，叫做“父子关系”。
如图，A节点就是B节点的父节点，B节点就是A节点的子节点，B、C、D节点的父节点是同一个节点，所以他们之间称为兄弟节点，E这种没有父节点的节点叫做根节点，像G这种没有子节点的叫做叶子节点（叶节点）。
节点的高度：节点到叶子节点的最长路径（边数）
节点的深度：根节点到这个节点所经历的边的个数
节点的层数：节点的深度+1
树的高度：根节点的高度
2.11.2二叉树
二叉树每个节点最多两个“叉”，也就是有两个子节点，分别书左子节点和右子节点。有的节点只有左子节点，有的只有右子节点
编号2这种二叉树，所有的叶子节点都在底层，而且每个节点都有左右两个子节点，这样的二叉树叫作满二叉树，编号3这种二叉树，叶子节点都在最底下两层，最后一层子节点都靠左排列，并且除了最后一层，其他层节点个数要达到最大，这种二叉树叫做完全二叉树。
存储一棵二叉树，有两种方法，一种是基于指针或引用的二叉链式存储法，一种是基于数组的顺序存储法。
如下是链式存储法，每个节点中有三个字段，其中一个存储数据，另外两个指向左右子节点的指针。只要拎住根节点就可以通过左右子节点的指针，把整棵树都串起来，一般都是用这种存储方法来实现二叉树的。
如下是顺序存储法，如果根节点A的位置存储在i=1的位置，那么B就在2*i=2的位置，C就在2*i+1=3的位置，以此类推即可，通过这种方式，只要知道根节点的位置，通过下标计算，就可以把整棵树串起来。
而上面这是一棵完全二叉树，所以只浪费一个下标为0的存储位置，但是如果是非完全二叉树，就会浪费很多的数组存储空间。所以如果是完全二叉树，用数组存储是最节省内存的一种方式。因为数组存储不需要像链表法那样存储额外的左右子节点的指针。（堆和堆排序其实就是一种完全二叉树，最常用的存储方式就是数组）。
2.11.3二叉树的遍历（常见面试题）
要对二叉树进行遍历，将他所有的子节点都遍历打印出来，经典的方法有三种“前序遍历”“中序遍历”“后序遍历”前中后表示的是节点与左右子节点遍历打印的先后顺序。
前序遍历：对于树中任意节点来说，先打印这个节点，再打印左子树，最后打印右子树。
中序遍历：对于树中任意节点来说，先打印左子树，然后打印它本身，最后打印右子树。
后序遍历：对于树中任意节点来说，先打印左子树，再打印右子树，最后打印节点本身。
因为每个节点都会访问两次，所以二叉树的时间复杂度是O(n)。
2.11.2二叉树查找树
二叉查找树又叫二叉搜索树，是为了实现快速查找而生，它不仅仅支持快速查找一个数据，还支持快速插入、删除数据。二叉查找树要求，在树中任意一节点，在树中任意一个节点，其左子树的每个节点的值，都要小于这个节点的值，而右子树节点的值都要大于这个节点的值。
1）二叉查找树的查找操作
先取根节点，如果他等于我们要查找的数据，就把它返回，如果要查找的数据比根节点的值小就在左子树中递归查找，如果要查找的数据比根节点的值大，就在右子树中递归查找。
2）二叉查找树的插入操作
二叉树的插入操作类似于查找操作，新插入的数据一般都在叶子节点上，所以从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且右子节点为空，就插入到右子节点，如果不为空，就再递归遍历右子树，查找插入位置。小的情况同理。
3）二叉查找树的删除操作
三种情况：第一种情况是要删除的节点没有子节点，只需要将父节点中，指向要删除的节点的指针置为null，比如要删除的节点55。第二种情况是如果要删除的节点只有一个子节点，就将要删除的节点的父节点删除节点的指针，指向要删除节点的子节点。比如图中删除13。第三种情况是如果要删除的节点有两个子节点，就比较复杂，需要找到这个节点右子树下的最小节点（因为这个点一定是最接近原来被删除节点，而且比左子树里面每个值都大的点），把它替换到要删除的节点上。然后在删除这个最小节点，最小节点肯定没有左子节点（不然就不是最小节点了），可以利用上面那两个规则来删除这个最小节点，比如删除图中18。
4）二叉查找树的其他操作
二叉查找树除了支持上面几个操作外，还可以支持快速查找最大、最小字节、前驱结点和后继节点。除了支持上面几个操作还有一个重要的特性，中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是O(n)。
支持重复数据的二叉查找树，很多时候，在二叉查找树中存储的，是一个包含很多字段的对象，利用对象的某个字段作为key值来构建二叉查找树，把对象中其他数据叫做为卫星数据。前面考虑的都是不存在键值重复的情况，那如果存储的两个对象键值相同，该如何考虑。
两种解决方法：
一、可以通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储到同一个节点上。
二、每个节点仍然只存一个数据，当插入数据的值与遇到相同值的节点的时候，就将这个要插入的数据插入到这个节点的右子树，也就是把这个值相同的节点当做，大于的节点来处理。当要查找数据的时候，遇到相同的节点，继续在右子树中查询，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值得所有节点都查找出来。删除数据时，也要找到每个要删除的节点，然后按照上面的删除方法，一一删除。
5)二叉查找树的时间复杂度分析
以上三图，图一是最差情况，二叉树已经退化成链表了，这时查找的时间复杂度就退化成O(n)了，对于二叉查找树的操作，不管是插入删除还是查找，时间复杂度都是跟树的高度成正比的。所以就要来分析一棵有n个节点的树的高度，假设有L层，第一层1个节点，第二层2个...第L层最大值就是2^(L-1)个，最小值是1个，所以最后一层节点的范围是[1,2^(L-1)]，将所有的节点加起来得到n，那么
n<=1+2+4+...+2^(L-2)+2^(L-1)，
n>=1+2+4+...+2^(L-2)+1
利用等比数列求和公式求得L的范围是[log2(n+1),log2n+1]。(所以在这个区间内的查找二叉树才是比较好的，像上面图一那种二叉查找树就废了)显然极不平衡的二叉树是不可取的，我们要构建一种不管是插入、删除、查找都比较均衡的二叉树，也就是平衡二叉树，平衡二叉树的告诉是接近log(n)的，所以插入、删除、查找的时间复杂度也比较稳定，是O(logn)。
2.11.3二叉树查找树和散列表的对比
散列表的插入、删除、查找时间复杂度可以做到常量级的O(1)，而平衡二叉树也不过就才O(logn)，那么二叉树的优势是什么，为什么有散列表还要用二叉查找树？
一、散列表中的存储是无序存储的，如果要输出有序的数据，要先进行排序，而对于二叉查找树，只需要中序遍历就可以了，就可以在O(n)时间复杂度内输出有序序列。
二、散列表扩容很耗时，而且当遇到散列冲突时，性能不稳定，在工程中，常用的平衡二叉树的性能非常稳定的。
三、尽管散列表的查找等操作是常量级的，但是因为哈希冲突的存在，这个常量可能比logn还大，在加上哈希函数的计算还需要消耗时间，所以不一定比平衡二叉树更快。
四、散列表的设计要考虑很多问题，散列函数的设计、冲突的解决方法、扩容缩容。而查找二叉树只需要考虑平衡性这一个问题。
五、散列表有装载因子，都不能太大，会浪费存储空间。
（本文是个人听课笔记，不少东西摘取于王争老师的原文，原文链接http://gk.link/a/10aMZ）
