Javaデータ構造とアルゴリズム高級編のツリー、図

11820 ワード

データ構造

データは基礎であり、アルゴリズムは魂である.
この文章は門心くわえ龍のブログから来ました.オリジナルの種類に属しています.転載は出典を明記してください.https://blog.csdn.net/geduo_83/articale/detail/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年の1部の映画は奇跡を創造して、それは全世界の第1部の興収が27億ドルに達するので、総括的な興収は直ちに第1位の映画を順位付けて、それはジェームズです.キャメロンの監督の映画《アバター》.
映画の中で大きな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: 

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

二つの二叉の木が完全に同じかどうかを判断します.

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

二叉の木が対称二叉の木かどうか判断します.

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

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

3.図
3.1 概念
線形表では、データ要素の間は直列されており、線形関係だけがあり、各データ要素は直接前駆者と直接後継者が一つしかない.ツリー構造では、データ要素の間に明らかな階層関係があり、各階層のデータ要素は、次の層の複数の要素と関連していても、前の層の一つの要素としか関連していない.これは両親と一緒に多くの子供がいることができますが、すべての子供が両親とペアしかないのは同じです.しかし、現実生活では、人と人の関係は非常に複雑であり、もし私が知っている友達同士でも、お互いが知り合うなら、これは簡単な一対一ではありません.それは私たちが今日研究するもう一つの高級データ構造の図です.図は、線形表と数より複雑なデータ構造である.図形構造では、ノード間の関係は任意であり、図中の任意の2つの要素の間で相関が可能である.
3.2 ストレージ構造
図は、隣接行列と隣接テーブルの2つの記憶構造を使用することができる.隣接マトリクスは、図の頂点間の関係をマトリクスとして記憶します.隣接行列は以下の特徴があります.
1.隣接行列は正行列、すなわち横縦次元が等しい. 2.行列の各列または列は頂点を表し、列との交点はこの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

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

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

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

4.まとめ
今は木と図に対して基本的な理解ができました.後の文章で彼らがよく使うアルゴリズムについて議論し続けます.
ソースのダウンロード先:https://download.csdn.net/download/geduo_83/10913510
初級編:Javaデータ構造とアルゴリズム初級編の行列、集合と散リスト中級編:Javaデータ構造とアルゴリズム中級編のスタック、キュー、チェーン高級編:Javaデータ構造とアルゴリズム高級編のツリー、図
理論編:Java配列、集合、散リストの一般的なアルゴリズム浅分析理論編:Javaスタック、行列、チェーンの一般的なアルゴリズム浅分析理論編:Java樹、図の一般的なアルゴリズム浅分析

LCTまとめ