树
树的基本定义
树是由 n （ n>=1 ）个有限结点组成一个具有层次关系的集合。把它叫做 “ 树 ”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的
二叉树
结点的度： 一个结点含有的子树的个数称为该结点的度；
二叉树就是度不超过 2 的树 ( 每个结点最多有两个子结点 )
二叉树的节点类代码：
private class Node<Key,Value>{ //存储键 public Key key; //存储值 private Value value; //记录左子结点 public Node left; //记录右子结点 public Node right; public Node(Key key, Value value, Node left, Node right) { this.key = key; this.value = value; this.left = left; this.right = right; } }
满二叉树
一个二叉树，如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。
完全二叉树
叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
二叉树的遍历
前序遍历：先访问根结点，然后再访问左子树，最后访问右子树
中序遍历：先访问左子树，中间访问根节点，最后访问右子树
后序遍历：先访问左子树，再访问右子树，最后访问根节点
如果我们分别对下面的树使用三种遍历方式进行遍历，得到的结果如下：
前序遍历代码：
//使用前序遍历，获取整个树中的所有键 public Queue<Key> preErgodic(){ Queue<Key> keys = new Queue<>(); preErgodic(root,keys); return keys; } //使用前序遍历，把指定树x中的所有键放入到keys队列中 private void preErgodic(Node x,Queue<Key> keys){ if (x==null){ return; } //1.把当前结点的key放入到队列中; keys.enqueue(x.key); //2.找到当前结点的左子树，如果不为空，递归遍历左子树 if (x.left!=null){ preErgodic(x.left,keys); } //3.找到当前结点的右子树，如果不为空，递归遍历右子树 if (x.right!=null){ preErgodic(x.right,keys); } }
中序遍历代码：
//使用中序遍历，获取整个树中的所有键 public Queue<Key> midErgodic(){ Queue<Key> keys = new Queue<>(); midErgodic(root,keys); return keys; } //使用中序遍历，把指定树x中的所有键放入到keys队列中 private void midErgodic(Node x,Queue<Key> keys){ if (x==null){ return; } //1.找到当前结点的左子树，如果不为空，递归遍历左子树 if (x.left!=null){ midErgodic(x.left,keys); } //2.把当前结点的key放入到队列中; keys.enqueue(x.key); //3.找到当前结点的右子树，如果不为空，递归遍历右子树 if (x.right!=null){ midErgodic(x.right,keys); } }
后序遍历代码：
//使用后序遍历，获取整个树中的所有键 public Queue<Key> afterErgodic(){ Queue<Key> keys = new Queue<>(); afterErgodic(root,keys); return keys; } //使用后序遍历，把指定树x中的所有键放入到keys队列中 private void afterErgodic(Node x,Queue<Key> keys){ if (x==null){ return; } //1.找到当前结点的左子树，如果不为空，递归遍历左子树 if (x.left!=null){ afterErgodic(x.left,keys); } //2.找到当前结点的右子树，如果不为空，递归遍历右子树 if (x.right!=null){ afterErgodic(x.right,keys); } //3.把当前结点的key放入到队列中; keys.enqueue(x.key); }
堆
堆的定义
堆是计算机科学中一类特殊的数据结构的统称，堆通常可以被看做是一棵完全二叉树的数组对象
堆的特性
1.它是完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满。
2.它通常用数组来实现。具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子结点的子 结点则分别在位置4,5,6和7，以此类推。
如果一个结点的位置为k，则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从a[k]向上一层，就令k等于k/2,向下一层就令k等于2k或2k+1。
3.每个结点都大于等于它的两个子结点。这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，跟我们之前学习的二叉查找树是有区别的。
堆排序
堆可以分为大根堆，小根堆
大根堆:每个节点的值都大于或者等于他的左右孩子节点的值
小根堆:每个结点的值都小于或等于其左孩子和右孩子结点的值0
堆是用数组完成数据元素的存储的，由于数组的底层是一串连续的内存地址，所以我们要往堆中插入数据，我们只能往数组中从索引0处开始，依次往后存放数据，但是堆中对元素的顺序是有要求的，每一个结点的数据要大于等于它的两个子结点的数据，所以每次插入一个元素，都会使得堆中的数据顺序变乱，这个时候我们就需要通过一些方法让刚才插入的这个数据放入到合适的位置。
以大根堆的调整为例：
同样，删除元素也需要进行堆调整：
对于大根堆，索引1处的元素，也就是根结点是最大的元素，当我们把根结点的元素删除后，需要有一个新的根结点出现，这时我们可以暂时把堆中最后一个元素放到索引1处，充当根结点，但是它不满足大根堆的有序性需求，这个时候我们就需要通过一些方法，让这个新的根结点放入到合适的位置。
堆排序实现步骤（使用大根堆，实现从小到大排序）：
- 构造大根堆；
- 得到堆顶元素，这个值就是最大值；
- 交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经放到合适的位置；
- 对堆进行调整，重新让除了最后一个元素的剩余元素中的最大值放到堆顶；
- 重复2~4这个步骤，直到堆中剩一个元素为止；
public class HeapSort { public static void main(String[] args) { int[] a=new int[]{5,32,4,23,1,8,64,67,35,85,12,123,543,45,23,10}; System.out.println(Arrays.toString(a)); int l=a.length; for(int i=0;i<a.length-1;i++) { for(int p=l-1;p>=0;p--) { sort(a,p,l); } int temp=a[0]; a[0]=a[l-1]; a[l-1]=temp; l--; } System.out.println(Arrays.toString(a)); } public static void sort(int[] a,int p,int l) { int c=2*p+1; if(c<l) { int rc=c+1; if(rc<l && a[c]<a[rc]) c=rc; if(a[p]<a[c]) { int temp=a[p]; a[p]=a[c]; a[c]=temp; p=c; sort(a,p,l); } } } }
