蓝桥杯算法基础（22）：（树、二叉树简介，对堆排序的认识）java版

物理层面：顺序存储，链式存储

（顺序存储）
可以用数组来表示一棵树
左孩子：2i+1
右孩子：2i+2
（适用于完全二叉树）
（i-1）/2算父节点

（遍历顺序）
先序（根），中序，后序
先序:根左右
中序:左根右
后序:根左右

static void preOrder(int[] arr,int index){
    if(index>=arr.length)
    return;
    System.out.println(arr[index]);输出根节点
    preOrder(arr,index*2+1);//递归输出左子树
    preOrder(arr,index*2+2);//递归输出右子树
}


static void inOrder(int[] arr,int index){
    if(index>=arr.length)
    return;
    preOrder(arr,index*2+1);
    System.out.println(arr[index]);
    preOrder(arr,index*2+2);
}



static void postOrder(int[] arr,int index){
    if(index>=arr.length)
    return;
    preOrder(arr,index*2+1);
     preOrder(arr,index*2+2);
   System.out.println(arr[index]);

}

延续二叉树的知识点，继续介绍之前提过的堆的概念
二叉堆是完全二叉树或者是近似完全二叉树

”二叉堆“满足二个特性
1.父节点的键值总是大于或等于（小于或等于）任何一个字节点的键值
2.每个节点的左子树和右子树都有一个二叉堆（都是最大堆或最小堆）。

任意节点的值都大于其子节点的值——大顶堆
任意节点的值都小于其子节点的值——小顶堆

1.堆化（heapify），反向调整使得每个子树都是大 顶或小顶堆
2.按序输出元素：把堆顶和最末元素对调，然后调整堆顶元素

Minheap(A){
    n=A.length;
    for i from n/2-1 down to 0{
     MinHeapFixDown(A,i);//堆化heapify
    }
}

MinHeapFixDown(A,i,n){

    //找到左右孩子
    left=2*i+1;
    right=2*i+2;

    if(left>=n){//左孩子已经越界，i就是叶子节点
    return;
    }
    if(right>=n){
    min=left;
    }else{
        if(A[right]<A[left])
        {min=right;}
    }
    //如果A[i]比两个孩子都要小，不用调整
    if(A[i]<A[min]){
    return;}
    //min指向了最有孩子中较小的那个

    //否则，找到两个孩子中较小的，和i交换
    temp=A[i];
    A[i]=A[min];
    A[min]=temp;
    //小孩子那个位置的值发生了变化，i变更为小孩子那个位置，递归调整
    MinHeapFixDown(A,min,n);
}


完善堆排序
Sort(A){
//先对A进行堆化
MinHeap(A);
//把堆顶，0号元素和最后一个元素对调
for(int x=n-1;x>=0;x--)
swap(A,0,x);
//缩小堆的范围，堆顶元素进行向下取整
MinHeapFixDown(A,0,x-1);
}

//小顶堆与大顶堆类似