- 树的表示
- 如何反转二叉树
- 广度优先和深度优先算法
- 判断是否二叉搜索树
- 平衡二叉树的认知
树的表示
树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。
每个非空树形结构有根节点(root node)和叶子节点(leaf node)，比如上图中根节点为A，叶子节点为 K、L、F、G、M、I、J 。整个存储形状在逻辑结构上看，类似于实际生活中倒着的树。
根节点：如果一个结点没有父结点，那么这个结点就是整棵树的根结点
叶子节点：如果结点没有任何子结点，那么此结点称为叶子结点（叶结点）
而对于一棵树来说具有它的深度和层次。比如图A树的深度为4，层次即深度。而每个节点自有它的高度，即度，对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（Degree），比如节点A度为3，节点M度为0。
而树中研究最广的数二叉树了，二叉树即每一个节点拥有字节点最多为2。
反转二叉树
作为曾经谷歌的一道面试题，却难倒了苹果电脑上最受欢迎的homebrew程序的作者Max Howell。谷歌有90%的工程师都在用homebrew。然而Max在面试谷歌时却因为这个二叉树反转而被拒之门外，说起来也叫人不甚唏嘘。。
何为反转二叉树？其实就是将一颗二叉树所有对应节点进行对此的交换，水平将二叉树翻转过来，如下所示：
代码中实现我们可以先定义个树结构如下：
public class BSTree> { BSTNode root; static class BSTNode { BSTNode left; BSTNode right; T data; public BSTNode(T data) { this.data=data; } }
BSTree中有根结点root，每个节点用BSTNode表示，其下有左节点，右节点和对应值data。
而反转这颗树只需要如下几行代码：
public staticvoid reverse(BSTNode node) { if(node == null) { return; } // 临时交换中间变量 BSTNode t = node.left; node.left = node.right; node.right = t; // 递归就行了 reverse(node.left); reverse(node.right); }
广度优先和深度优先
广度优先(Breath first)和深度优先(Depth fist)主要是表现在查找时节点的先后顺序上，广度主要是逐层遍历，而深度优先则是不断遍历每个节点的子节点，主要包括有先序、中序和后序三种。
对应上面一颗二叉树而言，深度优先查找
先序：5 3 2 4 7
后序：2 4 3 7 5
中序：2 3 4 5 7
而对于广度优先算法：
其遍历顺序为：12 8 23 7 11 15 28，可实现如下：
public static void bfs(BSTNode node){
// 遍历存储队列，保证先进先出
Queue> queue=new Queue>();
queue.enqueue(node);
while(queue.size()>0){
// 出队列
BSTNode item= queue.dequeue();
System.out.println(item.data);
// 左右节点入列
if(item.left!=null){
queue.enqueue(item.left);
}
if(item.right!=null){
queue.enqueue(item.right);
}
}
}
二叉搜索树
二叉搜索树（Binary Search Tree）当然首先满足是个二叉树，对于树中每个节点：
若其左子树存在，则其左子树中每个节点的值都不大于该节点值；
若其右子树存在，则其右子树中每个节点的值都不小于该节点值。
总结来说判断一棵树是否二叉搜索树，可以通过中序遍历查询其结果必然是按从小到大排列的。
对于一个完全二叉树而言：所有节点尽量填满树的每一层，上一层填满后还有剩余节点的话，则由左向右尽量填满下一层。如上图BST所示，即为一颗完全二叉树。其搜索时间复杂度可以达到高效的O(logN)，但如果存在另一种极端情况每一层只有一个节点的二叉树：
则树中每层只有一个节点，该状态的树结构更倾向于一种线性结构，节点的查询类似于数组的遍历，查询复杂度为 O(n)。所以如果二叉搜索树能够更“平衡”一些，避免了树结构向线性结构的倾斜，则能够显著降低时间复杂度。
平衡二叉树
平衡二叉树大部分操作和二叉查找树类似，其前提是必须是一颗二叉搜索树，主要不同在于插入删除的时候平衡二叉树的平衡可能被改变，并且只有从那些插入点到根结点的路径上的结点的平衡性可能被改变，因为只有这些结点的子树可能变化。
平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
Java中HashMap中的红黑树结构就是一种平衡二叉树。
