风也温柔

计算机科学知识库

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

  源码下载地址:

  初级篇:Java数据结构与算法初级篇之数组集合和散列表

  中级篇:Java数据结构与算法中级篇之栈、队列、链表

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

  理论篇:Java数组、集合、散列表常见算法浅析

  理论篇:Java栈、队列、链表常见算法浅析

  理论篇:Java树、图常见算法浅析

  1.前言

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

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

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

  2.树

  2.1树的概念

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

  2.2满二叉树

  note = 2^k - 1

  2.3完全二叉树

  2.3.1特点

  2.3.2堆

  2.4红黑树

  2.5相关算法

  <pre class="has">`package F树.A001求二叉树的高节点数中序遍历;
/**

  • Description:
  • Author: 门心叼龙
  • Date: 2018/11/21
  • Version: V1.0.0
  • Update:
    */

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

}
}`</pre>

  <pre class="has">`package F树.A002判断两颗二叉树是否完全相同;
import F树.A001求二叉树的高节点数中序遍历.TreeNode;
/**

  • Description:
  • Author: gxl
  • Date: 2018/11/23
  • Version: V1.0.0
  • Update:
    */

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());

}
}`</pre>

  <pre class="has">`package F树.A003判断一个二叉树是否是对称二叉树;
import F树.A001求二叉树的高节点数中序遍历.TreeNode;
/**

  • Description:
  • Author: gxl
  • Date: 2018/11/23
  • Version: V1.0.0
  • Update:
    */

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

<p>java算法和算法导论_java 数据结构与算法_算法导论与数据结构

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

}
}`</pre></p>
  3.图

  3.1概念

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

  3.2存储结构

  图可以使用两种存储结构java 数据结构与算法,分别是邻接矩阵和邻接表。

  邻接矩阵以矩阵的形式存储图所有顶点间的关系。邻接矩阵具有以下特点:

  邻接表是以一组链表来表示顶点间关系java 数据结构与算法 Java数据结构与算法高级篇之树、图,有以下特点:

  3.3图的实现

  3.3.1邻接矩阵无向图

<p><pre class="has">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