《啊哈算法》的Java实现 | 第七章：神奇的树

• • 开启“树”之旅
  • • 树的特性
    • 树的定义
    • • 根
      • 父节点子节点
      • 深度
  • 二叉树
  • • 满二叉树
    • 完全二叉树
    • 编号
  • 堆
  • • 创建堆
    • 代码实验
    • 优化
    • 擒贼先擒王--并查集

树其实就是不包含回路的连通无向图，上边的图是一棵树，下边的图是一个图，因为右边的没有贿赂，而左边存在1-2-5-3-1这样的回路。

树有着“不包含回路”的特点，所以树被赋予了很多的特性：

1. 一棵树的任意两个节点有且仅有唯一的一条路径连通
2. 一个树如果有n个节点，那么它一定恰好有n-1条边
3. 在一棵树中加一条边将会构成一个回路

树是指任意两个节点间有且只有一条路径的无向图。或者说，只要是没有回路的连通无向图就是树

树中可以指定一个特殊的节点——根。我们在对一棵树进行讨论的时候，将树中的每个点称为结点。有一个根的树叫做有根树，其中上图中的1就为根结点

根又叫做根结点，一棵树有且只有一个根结点

父亲节点简称父结点；儿子节点简称为子结点。

2号节点为4号和5号节点的父结点，也是1号节点的子结点。

另外如果一个结点没有子结点，那么称这个结点为叶结点。例如4、5、6、7都为叶结点。

如果这个结点没有父节点，那么这个结点为根节点，比如1号结点。

如果一个结点既不是叶结点也不是根节点，那么称之为内部节点。

深度是指从根到这个结点的层数（根为第一层结点）

二叉树是一种特殊的树。二叉树的特点是每个结点最后有两个儿子，左边的叫左儿子，右边的叫右儿子，或者说每个结点最多有两棵子树。

二叉树中还有两种特殊的二叉树，叫做满二叉树和完全二叉树。如果二叉树中每个内部节点都有两个儿子，这样的二叉树叫做满二叉树

也就是说满二叉树所有的叶结点都有相同的深度

满二叉树的严格定义是一颗深度为h且有2^h-1个结点的二叉树

如果一个二叉树除了最右边的位置上有一个或者几个叶结点缺少之外，其余的都是满的，那么这样的二叉树就为完全二叉树。

**严格的定义是：若设二叉树的高度为h，除第n层外，其他的各层（1-h-1）的结点都达到最大个数，第h层从右向左连续缺若干结点，则这个二叉树就是完全二叉树。**也就是说如果有右子节点，那么必定有左子结点

如果一个完全二叉树的父节点编号为k，则左子结点为2* k，右子结点为2*k+1

若一个完全二叉树有N个结点，那么这个二叉树的高度为log₂N.

这颗树所有的父节点都要比子结点小，符合这样特点的完全二叉树称之为最小堆，反之如果所有父节点比子结点大，这样的完全二叉树称为最大堆

把n个元素建立成一个堆，首先可以将这n个 结点以自顶点向下、从左到右的方式从1到n编码，这样就可以把这个n个结点转换为一颗完全二叉树。接着从最后一个非叶结点n/2到跟结点1，逐个扫描所有的结点，根据需要将当前结点向下调整，直到以当前结点为根节点的子树符合堆的特性。

creat()之后的堆

package ch7;

import java.util.Scanner;

public class TreeTest01 {
    static  Scanner scanner = new Scanner(System.in);
    static  int n = scanner.nextInt();
    static  int[] h = new int[n+1];
    public static void swap(int x ,int y){
        int t;
        t = h[x];
        h[x] = h[y];
        h[y] = t;
        return;
    }

    
    public static void siftdown(int i){
        int t,flage = 0;
            //当i结点有儿子，那么至少有一个左儿子，所以从左子结点开始
            while (i*2 <=n && flage == 0){
                //首先判断和左儿子的关系
                if (h[i] > h[i*2]){
                    t = i*2;
                }else t = i;
                //如果有右儿子，判断与右儿子的关系
                if (i*2+1 <=n){
                //如果右儿子的值更小，则更新为更小的结点
                if(h[t] > h[i*2+1]){
                    t = i*2+1;
                }
            }
            //如果最小的结点不是本身，说明子结点中有比父节点更小的结点，交换继续
            if(t != i){
                swap(t,i);
                i = t;//更新为最小节点的编号，便于接下来继续
            }else flage = 1; //进行到这里说明，最小的结点就是本身。
        }
    }

    
    public static void creat(){
        for (int i = n/2; i>= 1; i--){
            siftdown(i);//从n/2个结点一直到根节点进行向下体调整
        }
    }

    
    public static int deletMax(){
        int t;
        t = h[1];//用一个临时变量来记录堆的顶点
        h[1] = h[n];//将堆的最后一个元素赋值到堆的顶点
        n--;
        siftdown(1);//向下调整
        return t;//返回之前记 录的堆的顶点最小值
    }

    public static void main(String[] args) {
        for (int i = 1; i<= n;i++){
            h[i] = scanner.nextInt();
        }
        scanner.close();
        creat();
        int num = n;//n 的值会随着deleMax的调用而减少
        for (int i = 1; i<= num;i++){
            System.out.print(deletMax() + " ");
        }


    }
}

当然堆排序还有一种更好的办法，从小到大排序的时候不是建立最小堆而是建立最大堆，最大堆建好之后，最大的元素在h[1]中，因此我们需要的是从小到大排序，希望最大的放在最后。因此将h[1]和h[n]呼唤，此时h[n]就是数组中的最大元素，请注意交换后还需要将h[1]向下调整以保存堆的特性，之后将堆的大小减1，并将交换后的新h[1]向下调整保持堆的特性。

package ch7;

import java.util.Scanner;

public class TreeTest02 {
    static Scanner scanner = new Scanner(System.in);
    static int n = scanner.nextInt();
    static int[] h = new int[n+1];

    
    public static void swap(int x,int y){
        int t  = h[x];
        h[x] = h[y];
        h[y] = t;
    }

    
    public static void shiftdown(int i){
        int flage = 0;
        int t;
        while(i*2 <=n && flage == 0){
            if(h[i] < h[i*2]) t = i*2;
            else t = i;
            if(i*2+1 <=n){
                if (h[t] < h[i*2+1]) t= i*2+1;
            }
            if (t!=i){
                swap(t,i);
                i = t;
            }else flage =1;
        }
    }

    
    public static void creat(){
        for (int i =n/2; i>=1;i--){
            shiftdown(i);
        }
    }

    
    public static void heapsort(){
        while(n>1){
            swap(1,n);//将1和n交换，n就为最大的值，之后再将1继续进行向下调整变为最大堆
            n--;
            shiftdown(1);
        }
    }

    public static void main(String[] args) {
        int num = n;
        for (int i =1;i<=n;i++){
            h[i] = scanner.nextInt();
        }
        scanner.close();
        creat();
        heapsort();
        for (int i =1;i<=num;i++){
            System.out.print(h[i] + " ");
        }

    }
}

package ch7;

    public static int getf(int v){
        if (f[v] == v)
            return v;
        else {
            //这里是路径压缩，每一次在函数返回的时候，顺带把路上遇到的人的"BOSS"改为最后找到的祖宗的编号
            //也就是最大BOSS的编号。这样可以提高今后找到犯罪团伙的最高领导人的速度
            f[v] =getf(f[v]);//路径压缩
            return f[v];
        }
    }

    
    public static void merge(int v,int u){
        int t1,t2;//t1、t2分别为v u的大BOSS， 每次双方的会谈都必须是最高领导人才行
        t1=  getf(v);
        t2 = getf(u);
        if (t1!=t2){
            //两个结点不在同一个集合当中。
            f[t2] = t1;//靠左原则，左边的变为右边的boss
        }
        return;
    }

    public static void main(String[] args) {
        int sum= 0;
        init();
        int m = scanner.nextInt();
        for (int i =1; i<= m;i++){
            int x= scanner.nextInt();
            int y =scanner.nextInt();
            merge(x,y);//合并两个集合

        }
        scanner.close();
        for (int i =1;i<=n;i++){
            if (f[i] == i)
                sum ++;
        }
        System.out.println(sum);
    }

}


       for (int i =1; i<= m;i++){
            int x= scanner.nextInt();
            int y =scanner.nextInt();
            merge(x,y);//合并两个集合

        }
        scanner.close();
        for (int i =1;i<=n;i++){
            if (f[i] == i)
                sum ++;
        }
        System.out.println(sum);
    }

}