三种最常用的数据结构 - 线性表 、树 、堆_树状图,线性表

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;
    }
}

二叉树的遍历

1. 前序遍历：先访问根结点，然后再访问左子树，最后访问右子树
2. 中序遍历：先访问左子树，中间访问根节点，最后访问右子树
3. 后序遍历：先访问左子树，再访问右子树，最后访问根节点

前序遍历代码：

//使用前序遍历，获取整个树中的所有键
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

同样，删除元素也需要进行堆调整：

对于大根堆，索引1处的元素，也就是根结点是最大的元素，当我们把根结点的元素删除后，需要有一个新的根结点出现，这时我们可以暂时把堆中最后一个元素放到索引1处，充当根结点，但是它不满足大根堆的有序性需求，这个时候我们就需要通过一些方法，让这个新的根结点放入到合适的位置。

1. 构造大根堆；
2. 得到堆顶元素，这个值就是最大值；
3. 交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经放到合适的位置；
4. 对堆进行调整，重新让除了最后一个元素的剩余元素中的最大值放到堆顶；
5. 重复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);
			}
 		}
	}
	
}