Java数据结构与算法高级篇之树、图

数据是基础，算法是灵魂

本文出自门心叼龙的博客，属于原创类容，转载请注明出处。https://blog.csdn.net/geduo_83/article/details/86557628

源码下载地址：https://download.csdn.net/download/geduo_83/10913510

初级篇：Java数据结构与算法初级篇之数组、集合和散列表
中级篇：Java数据结构与算法中级篇之栈、队列、链表
高级篇：Java数据结构与算法高级篇之树、图

理论篇：Java数组、集合、散列表常见算法浅析
理论篇：Java栈、队列、链表常见算法浅析
理论篇：Java树、图常见算法浅析

****1.前言****
****2.树****
2.1 树的概念
2.2 满二叉树
2.3 完全二叉树
2.4 红黑树
2.5 相关算法
****3.图****
3.1 概念
3.2 存储结构
3.3 图的实现
****4.小结****

****1.前言****

2010年的一部电影创造了奇迹，它是全球第一部票房到达27亿美元，总票房及时排名第一的影片，那就是詹姆斯.卡梅隆执导的电影《阿凡达》。

电影里提到了一颗高大274米的参天大树，是那个潘多拉星球的纳威人的家园，让人印象非常深刻。可惜那只是导演的梦想，地球上不存在这样的物种。

无论多高大的树，那也是从小到大、由根到叶、一点点成长起来的。俗话说十年树木、百年树人，一棵大树又何止是十年这样的容易。而今天我们讲另外一种新的数据结构--树。

****2.树****

****2.1 树的概念****

有N个节点组成，具有一定层次关系的集合。

****2.2 满二叉树****

note = 2^k - 1

****2.3 完全二叉树****

****2.3.1 特点****

  • 叶子节点都在k或者k-1层
  • k层可以是不满的，但是k层的所有节点都
  • 必须集中在最左边

****2.3.2 堆****

  • 大顶堆：父节点都大于子节点
  • 小顶堆：附近点都小于子节点

****2.4 红黑树****

  • 根节点都是黑色的
  • 红色节点的子节点都必须是黑色的
  • 叶子结点都必须是null
  • 任意节点到其所有路径所包含的黑色节点的个数是相同的

****2.5 相关算法****

  • 求二叉树的高节点数中序遍历
package F树.A001求二叉树的高节点数中序遍历;

/**
 * Description: <求二叉树的节点数高遍历><br>
 * Author: 门心叼龙<br>
 * Date: 2018/11/21<br>
 * Version: V1.0.0<br>
 * Update: <br>
 */
public class MainAlgorithm {
  public static void main(String[] args) {
    TreeNode treeNode = new TreeNode(0);
    TreeNode treeNode1 = new TreeNode(1);
    TreeNode treeNode2 = new TreeNode(2);
    TreeNode treeNode3 = new TreeNode(3);
    TreeNode treeNode4 = new TreeNode(4);
    TreeNode treeNode5 = new TreeNode(5);

    treeNode.setLeftNote(treeNode1);
    treeNode.setRightNote(treeNode2);

    treeNode1.setLeftNote(treeNode3);
    treeNode1.setRightNote(treeNode4);

    treeNode3.setLeftNote(treeNode5);

    printTreeNote(treeNode);
  }

  // 求这个二叉树的高
  public static int getTreeHeight(TreeNode treeNode) {
    if (treeNode == null) {
      return 0;
    } else {
      int leftHeight = 1 + getTreeHeight(treeNode.getLeftNote());
      int rightHeight = 1 + getTreeHeight(treeNode.getRightNote());
      if (leftHeight > rightHeight) {
        return leftHeight;
      } else {
        return rightHeight;
      }
    }
  }

  // 遍历二叉树的所有节点
  public static void printTreeNote(TreeNode treeNode) {
    if (treeNode == null) {
      return;
    } else {
      System.out.println(treeNode.getValue());
      printTreeNote(treeNode.getLeftNote());
      // System.out.println(treeNode.getValue());//中序遍历
      printTreeNote(treeNode.getRightNote());
    }
  }

  // 求二叉树节点的个数
  public static int getTreeNodeCount(TreeNode treeNode) {
    if (treeNode == null) {
      return 0;
    } else {
      return 1 + getTreeNodeCount(treeNode.getLeftNote())
          + getTreeNodeCount(treeNode.getRightNote());
    }
  }
}
image.gif
  • 判断两个二叉树是否完全相同：
package F树.A002判断两颗二叉树是否完全相同;

import F树.A001求二叉树的高节点数中序遍历.TreeNode;

/**
 * Description: <判断两颗二叉树是否完全相同><br>
 * Author: gxl<br>
 * Date: 2018/11/23<br>
 * Version: V1.0.0<br>
 * Update: <br>
 */
public class MainAlgorithm {
  public static void main(String[] args) {
    TreeNode treeNode = new TreeNode(0);
    TreeNode treeNode1 = new TreeNode(1);
    TreeNode treeNode2 = new TreeNode(2);
    TreeNode treeNode3 = new TreeNode(3);
    TreeNode treeNode4 = new TreeNode(4);
    TreeNode treeNode5 = new TreeNode(5);

    treeNode.setLeftNote(treeNode1);
    treeNode.setRightNote(treeNode2);

    treeNode1.setLeftNote(treeNode3);
    treeNode1.setRightNote(treeNode4);

    treeNode3.setLeftNote(treeNode5);
    // ===============================
    TreeNode treeNode0 = new TreeNode(0);
    TreeNode treeNode11 = new TreeNode(11);
    TreeNode treeNode22 = new TreeNode(2);
    TreeNode treeNode33 = new TreeNode(3);
    TreeNode treeNode44 = new TreeNode(4);
    TreeNode treeNode55 = new TreeNode(5);

    treeNode0.setLeftNote(treeNode11);
    treeNode0.setRightNote(treeNode22);

    treeNode11.setLeftNote(treeNode33);
    treeNode11.setRightNote(treeNode44);

    treeNode33.setLeftNote(treeNode55);

    boolean sameTree = isSameTree(treeNode, treeNode0);
    System.out.println(sameTree);
  }
  //每个节点对应的值一样就可以
  public static boolean isSameTree(TreeNode treeNode, TreeNode treeNode1) {
    if (treeNode == null && treeNode1 == null) {
      return true;
    }
    if (treeNode != null && treeNode1 == null) {
      return false;
    }
    if (treeNode == null && treeNode1 != null) {
      return false;
    }
    return (treeNode.getValue() == treeNode1.getValue())
        && isSameTree(treeNode.getLeftNote(), treeNode1.getLeftNote())
        && isSameTree(treeNode.getRightNote(), treeNode1.getRightNote());
  }
}
image.gif
  • 判断一个二叉树是否是对称二叉树
package F树.A003判断一个二叉树是否是对称二叉树;

import F树.A001求二叉树的高节点数中序遍历.TreeNode;

/**
 * Description: <一个二叉树是否是对称二叉树><br>
 * Author: gxl<br>
 * Date: 2018/11/23<br>
 * Version: V1.0.0<br>
 * Update: <br>
 */
public class MainAlgorithm {
  public static void main(String[] args) {
    TreeNode treeNode = new TreeNode(0);
    TreeNode treeNode1 = new TreeNode(10);
    TreeNode treeNode2 = new TreeNode(10);

    TreeNode treeNode3 = new TreeNode(20);
    TreeNode treeNode4 = new TreeNode(30);

    treeNode.setLeftNote(treeNode1);
    treeNode.setRightNote(treeNode2);

    treeNode1.setLeftNote(treeNode3);
    treeNode1.setRightNote(treeNode4);

    treeNode2.setLeftNote(treeNode4);
    treeNode2.setRightNote(treeNode3);

    boolean duicheng = isDuicheng(treeNode);
    System.out.println(duicheng);

  }

  public static boolean isDuicheng(TreeNode rootNode) {
    if (rootNode == null) {
      return true;
    } else {
      return isDuicheng(rootNode.getLeftNote(), rootNode.getRightNote());
    }
  }

  public static boolean isDuicheng(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
      return true;
    } else if (left != null && right == null || left == null && right != null) {
      return false;
    } else {
      return left.getValue() == right.getValue()
          && isDuicheng(left.getLeftNote(), right.getRightNote())
          && isDuicheng(left.getRightNote(), right.getLeftNote());
    }
  }
}
image.gif

****3.图****

****3.1 概念****

在线性表中，数据元素之间是被串联起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间有着明显的层次关系，并且每一层的数据元素可能和下一层中多个元素关联，但只能和上一层中一个元素相关。这和一堆父母可以有多个孩子，但每个孩子只能有一对父母是一个道理。可在现实生活中，人与人之间的关系就非常的复杂，如果我认识的朋友，他们相互之间也互相认识，这就不是简单的一对一，一对多，研究人际关系很自然会考虑多对多的情况。那就是我们今天要研究的另外一种高级数据结构--图。图是一种比线性表和数更加复杂的数据结构。在图形结构中，节点之间的关系可以是任意的，图中任意两个元素之间都有可能相关。

****3.2 存储结构****

图可以使用两种存储结构，分别是邻接矩阵和邻接表。
邻接矩阵以矩阵的形式存储图所有顶点间的关系。邻接矩阵具有以下特点：

  • 1.邻接矩阵是正矩阵，即横纵维数相等。
  • 2.矩阵的每一行或一列代表一个顶点，行与列的交点对应这两个顶点的边。
  • 3.矩阵的点代表边的属性，1代表有边，0代表无边，所以矩阵的对角线都是0，因为对角线上对应的横纵轴代表相同的顶点，边没有意义。
  • 4.如果是无向图，那么矩阵是对称矩阵；如果是有向图则不一定。
  • 5.如果是有权图，矩阵点数值可以是权值。
  • 6.邻接矩阵表示图的关系非常清晰，但消耗空间较大。

邻接表是以一组链表来表示顶点间关系，有以下特点:

  • 1.邻接表示一个有但链表组成的数组
  • 2.图中的每一个顶点都有一个链，数组的大小等于图中顶点的个数。
  • 3.无向图的链的第一个元素是本顶点，后继分别连接着和这个顶点相连的顶点；有向图的链第一个顶点是本顶点，后继是以本顶点为起点的边的终点。
  • 4.如果是有权图，可以在节点元素中设置权值属性
  • 5.邻接链表关系表示不如邻接矩阵清晰，数据结构相对复杂，但节省空间。

****3.3 图的实现****

****3.3.1 邻接矩阵无向图****

public class MatrixNDG {

    int size;//图顶点个数
    char[] vertexs;//图顶点名称
    int[][] matrix;//图关系矩阵

    public MatrixNDG(char[] vertexs,char[][] edges){
        size=vertexs.length;
        matrix=new int[size][size];//设定图关系矩阵大小
        this.vertexs=vertexs;

        for(char[] c:edges){//设置矩阵值
            int p1 = getPosition(c[0]);//根据顶点名称确定对应矩阵下标
            int p2 = getPosition(c[1]);

            matrix[p1][p2] = 1;//无向图，在两个对称位置存储
            matrix[p2][p1] = 1;
        }

    }

    //图的遍历输出
    public void print(){
        for(int[] i:matrix){
            for(int j:i){
                System.out.print(j+" ");
            }
            System.out.println();
        }
    }

    //根据顶点名称获取对应的矩阵下标
    private int getPosition(char ch) {
        for(int i=0; i<vertexs.length; i++)
            if(vertexs[i]==ch)
                return i;
        return -1;
    }

    public static void main(String[] args) {
        char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J','K'};
        char[][] edges = new char[][]{
            {'A', 'C'}, 
            {'A', 'D'}, 
            {'A', 'F'}, 
            {'B', 'C'}, 
            {'C', 'D'}, 
            {'E', 'G'}, 
            {'D', 'G'},
            {'I','J'},
            {'J','G'},};
        MatrixNDG pG;
        // 自定义"图"(输入矩阵队列)
        // 采用已有的"图"
        long start=System.nanoTime();

        for(int i=0;i<10000;i++){
            pG = new MatrixNDG(vexs, edges);
            //pG.print();   // 打印图 
        }

        long end=System.nanoTime();

        System.out.println(end-start);
    }
}
image.gif

****3.3.2 邻接矩阵有向图****

public class MatrixDG {
    int size;
    char[] vertexs;
    int[][] matrix;

    public MatrixDG(char[] vertexs,char[][] edges){
        size=vertexs.length;
        matrix=new int[size][size];
        this.vertexs=vertexs;

        //和邻接矩阵无向图差别仅仅在这里
        for(char[] c:edges){
            int p1 = getPosition(c[0]);
            int p2 = getPosition(c[1]);

            matrix[p1][p2] = 1;
        }

    }

    public void print(){
        for(int[] i:matrix){
            for(int j:i){
                System.out.print(j+" ");
            }
            System.out.println();
        }
    }

    private int getPosition(char ch) {
        for(int i=0; i<vertexs.length; i++)
            if(vertexs[i]==ch)
                return i;
        return -1;
    }

    public static void main(String[] args) {
        char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J','K'};
        char[][] edges = new char[][]{
            {'A', 'C'}, 
            {'A', 'D'}, 
            {'A', 'F'}, 
            {'B', 'C'}, 
            {'C', 'D'}, 
            {'E', 'G'}, 
            {'D', 'G'},
            {'I','J'},
            {'J','G'},};
        MatrixDG pG;
        // 自定义"图"(输入矩阵队列)
        //pG = new MatrixUDG();
        // 采用已有的"图"
        pG = new MatrixDG(vexs, edges);

        pG.print();
    }

}
image.gif

****3.3.3 邻接表无向图****

public class ListNDG {

    Vertex[] vertexLists;//邻接表数组
    int size;

    class Vertex{//邻接表节点类，单链表数据结构
        char ch;
        Vertex next;

        Vertex(char ch){//初始化方法
            this.ch=ch;
        }
        void add(char ch){//加到链表尾
            Vertex node=this;
            while(node.next!=null){
                node=node.next;
            }
            node.next=new Vertex(ch);
        }
    }

    public ListNDG(char[] vertexs,char[][] edges){

        size=vertexs.length;
        this.vertexLists=new Vertex[size];//确定邻接表大小
        //设置邻接表头节点
        for(int i=0;i<size;i++){
            this.vertexLists[i]=new Vertex(vertexs[i]);
        }
        //存储边信息
        for(char[] c:edges){
           int p1=getPosition(c[0]);
           vertexLists[p1].add(c[1]);
           int p2=getPosition(c[1]);
           vertexLists[p2].add(c[0]);
        }

    }

    //跟据顶点名称获取链表下标
    private int getPosition(char ch) {
        for(int i=0; i<size; i++)
            if(vertexLists[i].ch==ch)
                return i;
        return -1;
    }

    //遍历输出邻接表
    public void print(){
       for(int i=0;i<size;i++){
           Vertex temp=vertexLists[i];
           while(temp!=null){
               System.out.print(temp.ch+" ");
               temp=temp.next;
           }
           System.out.println();
       }
    }

    public static void main(String[] args){
        char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J','K'};
        char[][] edges = new char[][]{
            {'A', 'C'}, 
            {'A', 'D'}, 
            {'A', 'F'}, 
            {'B', 'C'}, 
            {'C', 'D'}, 
            {'E', 'G'}, 
            {'D', 'G'},
            {'I','J'},
            {'J','G'},};

        ListNDG pG;
        long start=System.nanoTime();
        for(int i=0;i<10000;i++){
            pG = new ListNDG(vexs, edges);
            //pG.print();   // 打印图 
        }
        long end=System.nanoTime();
        System.out.println(end-start);
    }

}
image.gif

****3.3.4 邻接表有向图****

public class ListDG {
    Vertex[] vertexLists;
    int size;

    class Vertex{
        char ch;
        Vertex next;

        Vertex(char ch){
            this.ch=ch;
        }
        void add(char ch){
            Vertex node=this;
            while(node.next!=null){
                node=node.next;
            }
            node.next=new Vertex(ch);
        }

    }

    public ListDG(char[] vertexs,char[][] edges){

        size=vertexs.length;
        this.vertexLists=new Vertex[size];
        for(int i=0;i<size;i++){
            this.vertexLists[i]=new Vertex(vertexs[i]);
        }

        for(char[] c:edges){
           int p=getPosition(c[0]);
           vertexLists[p].add(c[1]);
        }

    }

    private int getPosition(char ch) {
        for(int i=0; i<size; i++)
            if(vertexLists[i].ch==ch)
                return i;
        return -1;
    }

    public void print(){
       for(int i=0;i<size;i++){
           Vertex temp=vertexLists[i];
           while(temp!=null){
               System.out.print(temp.ch+" ");
               temp=temp.next;
           }
           System.out.println();
       }
    }

    public static void main(String[] args){
        char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J','K'};
        char[][] edges = new char[][]{
            {'A', 'C'}, 
            {'A', 'D'}, 
            {'A', 'F'}, 
            {'B', 'C'}, 
            {'C', 'D'}, 
            {'E', 'G'}, 
            {'D', 'G'},
            {'I','J'},
            {'J','G'},};

        ListDG pG;

        long start=System.nanoTime();

        for(int i=0;i<10000;i++){
            pG = new ListDG(vexs, edges);
            //pG.print();   // 打印图 
        }

        long end=System.nanoTime();
        System.out.println(end-start);

    }
}
image.gif

****4.小结****

现在我们对树和图已经有了一个基本的了解，在后续文章我们将继续讨论他们常用的一些算法。

源码下载地址：https://download.csdn.net/download/geduo_83/10913510

初级篇：Java数据结构与算法初级篇之数组、集合和散列表
中级篇：Java数据结构与算法中级篇之栈、队列、链表
高级篇：Java数据结构与算法高级篇之树、图

理论篇：Java数组、集合、散列表常见算法浅析
理论篇：Java栈、队列、链表常见算法浅析
理论篇：Java树、图常见算法浅析

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 217,657评论 6赞 505
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,889评论 3赞 394
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,057评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,509评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,562评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,443评论 1赞 302
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,251评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,129评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,561评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,779评论 3赞 335
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,902评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,621评论 5赞 345
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,220评论 3赞 328
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,838评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,971评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,025评论 2赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,843评论 2赞 354

推荐阅读更多精彩内容

  • 七色花开（三）
    七色花家人们： 大家周末好！“林花谢了春红，太匆匆”。忙碌之中，一周的时间总是很快就过去了，而刚结束的一周...
    张毛丽阅读 1,005评论 1赞 1
  • 加缪和毛姆告诉你：不要存乎世俗价值观
    这次说到两本书。一本是上个月读的加缪《局外人》，另一本是近几天读的毛姆《月亮和六便士》。由于在两本书中感受到相似的...
    肉松读书阅读 4,719评论 2赞 3