数据结构与算法学习总结（一）

约定不等于承诺〃 2022-05-30 04:53 220阅读 0赞

### 前言 ###

受本人知识水平所限，若您发现有不足的地方，欢迎指正。本文的代码以及图片**纯手打手画**，如果觉得有用，麻烦点赞。

### 基本概念 ###

*  数据结构相关
    
     *  **数据元素**（data element ）是数据的基本单位。通常由若干个数据项组成，数据项具有原子性，是不可分割的最小单位。
     *  **数据对象**（data object ）是性质相同的数据元素的集合。
     *  **数据结构**（data structure ）是指相互之间存在一种或多种特定关系的数据元素的集合。
     *  数据结构有两种表现形式。一种是数据结构的逻辑层面，即数据的**逻辑结构**；一种是存在于计算机世界的物理层面，即数据的**存储结构**。逻辑结构按数据元素之间的关系可分为： 集合、线性结构、树形结构和图状结构。存储结构可分为：顺序存储结构和链式存储结构。
     *  可以用**二元组**来表示数据结构，**数据结构 = \{D , S\}**，D 是数据元素的集合；S 是 D 中数据元素之间的关系集合
     *  **数据类型**（data type）是一组性质相同的数据元素的集合以及加在这个集合上的一组操作。
 *  算法相关
    
     *  **算法**（algorithm ）是指令的集合，是为解决特定问题而规定的一系列操作。
     *  算法的五个特性：输入、输出、可行性、有穷性、确定性。
     *  **时间复杂度**： 执行算法所需要的计算工作量。规模n的函数`f(n)`，时间复杂度记为`T(n)=Ο(f(n))`。
     *  **空间复杂度**： 执行算法所需要消耗的内存空间。规模n的函数`f(n)`，空间复杂度记为`S(n)=Ο(f(n))`。

### 线性表 ###

**线性表（linear list）是n个类型相同数据元素的有限序列**，通常记作a\_0 , a\_1 , …a\_\{i-1\} , a\_i , a\_\{i+1\} …,a\_\{n-1\}。。

线性表和数组的区别：

> 线性表是**元素之间**具有1对1的线性关系的数据元素的集合，而数组是一组**数据元素到数组下标**的一一映射。  
> **数组中相邻的元素是连续地存储在内存中的**；线性表只是一个抽象的数学结构，并不具有具体的物理形式，线性表需要通过其它有具体物理形式的数据结构来实现。在线性表的具体实现中，表中相邻的元素不一定存储在连续的内存空间中，除非它是用数组来实现的。

线性表的两种实现(**顺序存储** or **链式存储**)比较

*  基于时间的比较

数据元素的**查找**功能，顺序存储优于链式存储  
数据元素的**插入、删除**功能，链式存储优于顺序存储

*  基于空间的比较

线性表的顺序存储，其存储空间是**预先静态分配**的，而线性表的链式存储，其结点空间是**动态分配**的。当线性表长度变化较大时，宜采用链式存储结构。  
由于链式存储结构使用了额外的存储空间来表示数据元素之间的逻辑关系。当线性表数据元素结构简单，长度变化不大时可以考虑采用顺序存储结构。

### 栈与队列 ###

*  栈

栈（stack）又称堆栈，**后进先出表**（Last In First Out，简称LIFO）。它是运算受限的线性表，其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。表中进行插入、删除操作的一端称为栈顶（top），栈顶保存的元素称为栈顶元素。相对的，表的另一端称为栈底（bottom）。

*  队列

队列（queue ）简称队，**先进先出表**（First In First Out,简称FIFO）。它也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。在队列中把插入数据元素的一端称为 队尾（rear），删除数据元素的一端称为 队首（front）。向队尾插入元素称为 进队或入队，新元素入队后成为新的队尾元素；从队列中删除元素称为离队或出队，元素出队后，其后续元素成为新的队首元素。

*  堆栈LIFO特性运用的案例
 *   *  进制换算

/** * 将一个十进制的数以八进制的形式表示 * @param num 传入的数字 * @return 字符串形式八进制的数字 */
    public String baseConversion (int num) { 
      Stack<String> stack = new Stack<>();
      while(num > 0) { 
        stack.push(num%8 + "");
        num = num/8;
      }
      String result = "";
      while(!stack.isEmpty()){ 
        result = result + stack.pop();
      }
      return result;
    }

*   *  括号检测

/** * 检测一个字符串的括号是否正确匹配 * * @param str 将要检测的字符串 * @return 检测结果 */
    public boolean checkBracket(String str){ 
      Stack<Character> stack = new Stack<>();
      for (int i = 0;i < str.length();i++) { 
        char c = str.charAt(i);
        switch (c) { 
          case '{':
          case '[':
          case '(': stack.push(c);break;// 将碰到的所有左括号(不分大中小)按字符串的顺序存入栈中
          case '}':
            if (!stack.isEmpty() && stack.pop()=='{'){ 
              // 当前元素是右大括号，检测到栈顶元素是左大括号,取出该元素。
              break;
            } else { 
              // 当前元素是右大括号，检测到栈顶元素不是左大括号，则该字符串的括号匹配肯定不合法
              return false;
            }
          case ']':
            if (!stack.isEmpty() && stack.pop()=='['){ 
              // 当前元素是右中括号，检测到栈顶元素是左中括号,取出该元素。
              break;
            } else { 
              // 当前元素是右中括号，检测到栈顶元素不是左中括号，则该字符串的括号匹配肯定不合法
              return false;
            }
          case ')':
            if (!stack.isEmpty() && stack.pop()=='('){ 
              // 当前元素是右中括号，检测到栈顶元素是左中括号,取出该元素。
              break;
            } else { 
              // 当前元素是右小括号，检测到栈顶元素不是左小括号，则该字符串的括号匹配肯定不合法
              return false;
            }
        }
      }
      // 扫描并比较完了字符串中所有字符，如果栈中没有括号，则表示该字符串的括号匹配是合法的
      return stack.isEmpty();
    }

*   *  迷宫求解

> 迷宫问题综述：从面向对象的思想出发，将整个迷宫地形看成一个由多个**单元格**组成的二维图。迷宫中的墙体为不可通行的单元格，通道为可通行的单元格。起点和终点均是迷宫通道上的一个单元格。基于该前提，就是寻找一条从起点到终点的轨迹线，该轨迹线路过的单元格均是可通行的。

> 原型图如下：  
> ![原型图][70]

> 建模后如下：  
> ![分析图][70 1]

import java.util.Stack;
    
    /** * The type Maze. * * @author zhenye 2018/3/1 */
    public class Maze { 
      /** * 单元格类 */
      private class Cell { 
        /** * 单元格所在行 */
        int x;
        /** * 单元格所在列 */
        int y;
        /** * 墙:1，可让通行:0，起点到终点轨迹上的点:* */
        char c;
        /** * 单元格是否被访问过 */
        boolean visited;
    
        Cell(int x,int y,char c,boolean visited){ 
          this.x = x;
          this.y = y;
          this.c = c;
          this.visited = visited;
        }
      }
    
      /** * 迷宫图能走通时，打印从起点到终点的轨迹图 * * @param maze 迷宫图的二维数组(数据项为0,1) * @param sx 起点单元格所在行数 * @param sy 起点单元格所在列数 * @param ex 终点单元格所在行数 * @param ey 终点单元格所在列数 */
      private void mazeExit(char[][] maze,int sx,int sy,int ex,int ey){ 
        Cell[][] cells = initMaze(maze);// 初始化迷宫图
        printMaze(cells);// 打印初始化后的迷宫图
        Stack<Cell> stack = new Stack<>();
        Cell startCell = cells[sx][sy];// 起点
        Cell endCell = cells[ex][ey];// 终点
        stack.push(startCell); // 起点入栈，表示开始寻找终点
        startCell.visited = true; // 此时起点已经访问
    
        while (!stack.isEmpty()){ 
          Cell current = stack.peek(); //当前所处单元格，peek方法：获取栈顶元素的值，但不取出。
          if (current == endCell) {  //当前单元格为终点时，说明轨迹已经被找到
            while (!stack.isEmpty()) { 
              Cell cell = stack.pop();
              cell.c = '*';
              // 只有两个元素在二维数组以及栈中均是相邻的元素，这才是实际路径经过的单元格。因此需要过滤哪些不符合条件的单元格
              while(!stack.isEmpty()&&!isAdjoinCell(stack.peek(),cell)) stack.pop();
            }
            System.out.println("找到从起点到终点的路径");
            printMaze(cells);
            return;
          } else {  // 如果当前单元格不是终点
            int x = current.x;
            int y = current.y;
            int count = 0;
            if (isValidWayCell(cells[x+1][y])){  //向下走一步
              stack.push(cells[x+1][y]);
              cells[x+1][y].visited = true;
              count++;
            }
            if (isValidWayCell(cells[x][y+1])){  //向右走一步
              stack.push(cells[x][y+1]);
              cells[x][y+1].visited = true;
              count++;
            }
            if (isValidWayCell(cells[x-1][y])){  //向上走一步
              stack.push(cells[x-1][y]);
              cells[x-1][y].visited = true;
              count++;
            }
            if (isValidWayCell(cells[x][y-1])){  //向左走一步
              stack.push(cells[x][y-1]);
              cells[x][y-1].visited = true;
              count++;
            }
            if (count == 0) { 
              stack.pop(); //如果该单元格是个死点(走进了死胡同),从栈中取出该单元格
            }
          }
        }
        System.out.println("没有一条路径是起点通往终点的");
      }
    
      /** * 判断两个单元格在二维数组中是否是相邻的元素 * @param cell1 单元格1 * @param cell2 单元格2 * @return 只有两个单元格在二维数组、栈中均为相邻元素时，这才是实际路径经过的单元格。 */
      private boolean isAdjoinCell(Cell cell1, Cell cell2) { 
        if (cell1.x==cell2.x&&Math.abs(cell1.y-cell2.y)<2) return true;
        if (cell1.y==cell2.y&&Math.abs(cell1.x-cell2.x)<2) return true;
        return false;
      }
    
      /** * 该单元格是否可以通行 * @param cell 待检测的单元格 * @return 只有不是墙体并且未被访问过的单元格，才可以通行 */
      private boolean isValidWayCell(Cell cell) { 
        return cell.c == '0' && !cell.visited;
      }
    
      /** * 在控制台打印由单元格组成的二维数组 * @param cells 单元格组成的二维数组 */
      private void printMaze(Cell[][] cells) { 
        for (int x=0;x<cells.length;x++){ 
          for (int y=0;y<cells[x].length;y++){ 
            System.out.print(cells[x][y].c + " ");
          }
          System.out.println();
        }
      }
    
      /** * 初始化迷宫图 * @param maze 由(0:可通行单元格、1:墙体)组成的二维数组 * @return 由单元格组成的二维数组 */
      private Cell[][] initMaze(char[][] maze){ 
        Cell[][] cells = new Cell[maze.length][];
        for (int x = 0; x < maze.length; x++) { 
          char[] row = maze[x];
          cells[x] = new Cell[row.length];
          for (int y = 0; y < row.length; y++) { 
            cells[x][y] = new Cell(x,y,maze[x][y],false);
          }
        }
        return cells;
      }
    
      // 在main方法中进行测试
      public static void main(String[] args) { 
        Maze test = new Maze();
        char[][] maze = { 
          { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'},
          { '1', '0', '0', '1', '1', '1', '0', '0', '1', '1'},
          { '1', '0', '0', '1', '1', '0', '0', '1', '0', '1'},
          { '1', '0', '0', '0', '0', '0', '0', '1', '0', '1'},
          { '1', '0', '0', '0', '0', '1', '1', '0', '0', '1'},
          { '1', '0', '0', '1', '1', '1', '0', '0', '0', '1'},
          { '1', '0', '0', '0', '0', '1', '0', '1', '0', '1'},
          { '1', '0', '1', '1', '0', '0', '0', '1', '0', '1'},
          { '1', '1', '0', '0', '0', '0', '1', '0', '0', '1'},
          { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'}
        };
        // 起点在第9行第9列，终点在第2行第8列
        int sx = 8;
        int sy = 8;
        int ex = 1;
        int ey = 7;
        test.mazeExit(maze,sx,sy,ex,ey);
      }
    }

> 运行上述程序后,控制台输出:  
> ![控制台输出][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1V0b3BpYU9mQXJ0b3JpYQ_size_16_color_FFFFFF_t_70]

> 即结果如下：  
> ![运行结果图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1V0b3BpYU9mQXJ0b3JpYQ_size_16_color_FFFFFF_t_70 1]

1.  递归法

*  4.1 汉诺塔问题

详情见图如下：  
![汉诺塔分析图][70 2]  
,则代码如下：

/** * @author zhenye 2018/3/1 */
    public class Hanio { 
    
      /** * 将n个盘子从x塔座移动到z塔座，y塔座为过渡塔座。 * 要求大盘子不能放在小盘子上，每次只能移动最上面的一个盘子。 * @param n 盘子数 * @param x 起始塔座 * @param y 过渡塔座 * @param z 目标塔座 */
      public void hanio(int n,char x,char y,char z){ 
        if (n == 1) { 
          // 如果盘子只剩下一个，只需要将这个序号为1盘子的盘子从起始塔座x移动到目标塔座z上
          move (x,n,z);
        } else { 
          // 先将n-1个盘子从塔座x移动到塔座y上，塔座z为过渡塔座
          hanio(n-1,x,z,y);
          // 再将序列为n的盘子，从塔座x移动到塔座z
          move(x,n,z);
          // 再准备将剩下的n-1个盘子从塔座y移动到塔座z，塔座x为过渡塔座
          hanio(n-1,y,x,z);
        }
      }
    
      /** * 将下标为n的盘子，从x塔座移动到z塔座上 * @param x 起始塔座 * @param n 盘子序号，序号越大，盘子越大 * @param z 目标塔座 */
      private void move(char x, int n, char z) { 
        System.out.println("从塔座<"+ x + ">，移动序号为(" + n + ")的盘子，到塔座<" + z + ">");
      }
    
      // 在main方法中测试
      public static void main(String[] args) { 
        Hanio hanio = new Hanio();
        hanio.hanio(4,'A','B','C');
      }
    }

*  分治法

设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

*   *  分治法简单运用

import java.util.Random;
    import java.util.Scanner;
    
    /** * 分治法：将规模较大(n)的问题，分解成与原问题形式相同的子问题(k)进行解决 * * @author zhenye 2018/3/2 */
    public class IntPair { 
    
      /** * 用来记录数组中最大值、最小值的类 */
      private class Value { 
        int max;
        int min;
      }
    
      /** * 用最简单的方法找出一个整型数组的最大最小值 * @param a 给定的数组 * @return 返回数组a中最大最小值 */
      public Value simpleMinMax(int[] a) { 
        Value value = new Value();
        value.max = a[0];
        value.min = a[0];
        for (int i = 1;i < a.length;i++) { 
          value.max = value.max > a[i] ? value.max : a[i];
          value.min = value.min < a[i] ? value.min : a[i];
        }
        return value;
      }
    
      /** * 用分治法找出一个整型数组的最大最小值 * 具体实现：先将一个数组拆分成两个大小相等的子数组，需要找出这两个子数组的最大最小值， * 然后比较这两个子数组的最大值、最小值即可得到整个数组的最大最小值。 * 这里的子数组可以拆分成子子数组...直到数组的长度少于3个。 * @param a 给定的数组 * @param start 拆分后子数组在根数组中的起始下标 * @param end 拆分后子数组在根数组中的终止下标 * @return 返回数组a下标(start-end)之间元素组成的子数组的最大最小值 */
      private Value min_max (int[] a ,int start ,int end){ 
        Value value = new Value();
        if (start + 2 > end) { 
          // 如果start + 2 > end，说明拆分后的子目标数组元素个数少于3个(只可能是1个或2个)
          value.max = a[start] > a[end] ? a[start] : a[end];
          value.min = a[start] < a[end] ? a[start] : a[end];
        } else { 
          // 可以拆分时，选择从中间拆分
          int mid = (start + end)/2;
          Value value1 = min_max(a,start,mid);
          Value value2 = min_max(a,mid+1,end);
          value.max = value1.max > value2.max ? value1.max : value2.max;
          value.min = value1.min < value2.min ? value1.min : value2.min;
        }
        return value;
      }
    
      // 在main方法中测试
      public static void main(String[] args) { 
        Scanner scanner = new Scanner(System.in);
        System.out.println("数组中的值为0-1000的随机数，请你设置数组的大小：");
        String size = scanner.nextLine();
        IntPair intPair = new IntPair();
        Random random = new Random();
        int a[] = new int[Integer.valueOf(size)];
    // System.out.println("生成的初始数组如下：");
        for (int i = 0;i < a.length; i++) { 
          a[i] = random.nextInt(1000);
    // 打印初始数组
    // System.out.print(a[i]);
    // if (i < a.length - 1) System.out.print(",");
        }
        System.out.println();
        long value1Start = System.currentTimeMillis();
        Value value1 = intPair.simpleMinMax(a);
        long value1End = System.currentTimeMillis();
        System.out.println("简单方法计算，该数组的最大值为" + value1.max + ",最小值为" + value1.min + ",所耗时间毫秒数为:" + (value1End - value1Start));
        long value2Start = System.currentTimeMillis();
        Value value2 = intPair.min_max(a,0,a.length-1);
        long value2End = System.currentTimeMillis();
        System.out.println("分治法计算，该数组的最大值为" + value2.max + ",最小值为" + value2.min + ",所耗时间毫秒数为:" + (value2End - value2Start));
      }
    }

我测试的其中一次结果如下：  
![分治法效率][70 3]

测试10000000个随机数字(0-999之间)组成的数组，找到其中的最大最小值。经过多次测试结果对比，均是简单方法的效率高于分治法的效率。而从时间复杂度来分析，简单方法的时间复杂度为T(n)= 2n - 2;分治法的时间复杂度为：T(n) = 3n/2 - 2。按理说，分治法是优于简单方法的。出现这种结果我猜测是：JVM对递归方法的调用，需要用堆栈存储当前执行的递归方法层数、上层递归方法返回的结果等来维护递归方法的正确调用而损耗了时间。

*  4.3 矩阵相乘(用分治法不划算，就不扩展了)

百度百科中给出矩阵相乘的运算规则如下：  
![矩阵相乘][70 4]

矩阵相乘的实际用途如下：  
![矩阵用途][70 5]

### 树 ###

> 树，由n（n>=1）个有限节点组成一个具有层次关系的集合。按子节点是否由顺序关系，分为有序树、无序树。下面学习的是**有序二叉树的遍历**。

遍历的样本如下图所示：  
![将要遍历的二叉树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1V0b3BpYU9mQXJ0b3JpYQ_size_16_color_FFFFFF_t_70 2]

遍历的源码如下：

*  节点Node的源码如下：

import lombok.AllArgsConstructor;
    import lombok.Data;
    
    /** * 节点类，树中节点 * @author zhenye 2018/3/2 */
    @Data
    @AllArgsConstructor
    public class Node { 
      /** * 该节点中保存的值 */
      private int data;
      /** * 该节点的左子节点 */
      private Node leftChild;
      /** * 该节点的右子节点 */
      private Node rightChild;
    }

*  二叉树BinaryTree的源码如下：

import org.apache.log4j.NDC;
    import java.util.Stack;
    
    /** * 二叉树 * 主要学习二叉树的遍历：先序遍历、中序遍历、后序遍历。 * 每种遍历的实现又分为： 递归、堆栈。 * * 先序遍历：先保证打印顺序从上到下，再保证从左到右（根-左-右） * 中序遍历：先保证打印顺序从左到右，再保证从上到下（左-根-右） * 后序遍历：先保证打印顺序从左到右，再保证从下到上（左-右-根） * @author zhenye 2018/3/2 */
    public class BinaryTree { 
      /** * 初始化二叉树 * @return 返回二叉树的根节点 node */
      private Node init() { 
        Node I = new Node(9,null,null);
        Node H = new Node(5,null,null);
        Node G = new Node(6,null,null);
        Node F = new Node(7,null,null);
        Node E = new Node(1,null,I);
        Node D = new Node(3,G,H);
        Node C = new Node(2,null,F);
        Node B = new Node(8,D,E);
        Node A = new Node(4,B,C);
        return A;
      }
    
      /** * 在控制台打印该节点的值 * @param node the node */
      private void printNodeValue(Node node) { 
        System.out.print(node.getData() + " ");
      }
    
      /** * 用递归的方法，先序遍历二叉树 * @param node 二叉树的根节点 */
      private void preOrderRecursion(Node node){ 
        printNodeValue(node);
        if (node.getLeftChild() != null) { 
          preOrderRecursion(node.getLeftChild());
        }
        if (node.getRightChild() != null) { 
          preOrderRecursion(node.getRightChild());
        }
      }
    
      /** * 用堆栈的方法，先序遍历二叉树 * @param node 二叉树的根节点 */
      private void preOrderStack(Node node) { 
        Stack<Node> stack = new Stack<>();
        while (node != null || stack.size() > 0) { 
          if (node != null) { 
            printNodeValue(node);
            stack.push(node);
            node = node.getLeftChild();
          } else { 
            node = stack.pop();
            node = node.getRightChild();
          }
        }
      }
    
      /** * 用递归的方法，中序遍历二叉树 * @param node 二叉树的根节点 */
      private void inOderRecursion(Node node) { 
        if (node.getLeftChild() != null) { 
          inOderRecursion(node.getLeftChild());
        }
        printNodeValue(node);
        if (node.getRightChild() != null) { 
          inOderRecursion(node.getRightChild());
        }
      }
    
      /** * 用堆栈的方法，中序遍历二叉树 * @param node 二叉树的根节点 */
      private void inOrderStack(Node node) { 
        Stack<Node> stack = new Stack<>();
        while (node != null || stack.size() > 0) { 
          if (node != null) { 
            stack.push(node);
            node = node.getLeftChild();
          } else { 
            node = stack.pop();
            printNodeValue(node);
            node = node.getRightChild();
          }
        }
      }
    
      /** * 用递归的方法，后序遍历二叉树 * @param node 二叉树的根节点 */
      private void postOrderRecursion(Node node) { 
        if (node.getLeftChild() != null) { 
          postOrderRecursion(node.getLeftChild());
        }
        if (node.getRightChild() != null) { 
          postOrderRecursion(node.getRightChild());
        }
        printNodeValue(node);
      }
    
      /** * 用堆栈的方法，后序遍历二叉树 * @param node 二叉树的根节点 */
      private void postOrderStack(Node node) { 
        Stack<Node> stack = new Stack<>();
        Stack<Node> output = new Stack<>();//构造一个中间栈来存储逆后序遍历的结果
        while (node != null || stack.size() > 0) { 
          if (node != null) { 
            output.push(node);
            stack.push(node);
            node = node.getRightChild();
          } else { 
            node = stack.pop();
            node = node.getLeftChild();
          }
        }
        while (output.size() > 0) { 
          printNodeValue(output.pop());
        }
      }
    
      // 在main方法中测试
      public static void main(String[] args) { 
        BinaryTree tree = new BinaryTree();
        Node root = tree.init();
        System.out.println("用递归的方法实现二叉树的先序遍历(顺序：根节点->左子节点->右子节点)");
        tree.preOrderRecursion(root);
        System.out.println();
        System.out.println();
        System.out.println("用堆栈的方法实现二叉树的先序遍历(顺序：根节点->左子节点->右子节点)");
        tree.preOrderStack(root);
        System.out.println();
        System.out.println();
        System.out.println("用递归的方法实现二叉树的中序遍历(顺序：左子节点->根节点->右子节点)");
        tree.inOderRecursion(root);
        System.out.println();
        System.out.println();
        System.out.println("用堆栈的方法实现二叉树的中序遍历(顺序：左子节点->右子节点->根节点)");
        tree.inOrderStack(root);
        System.out.println();
        System.out.println();
        System.out.println("用递归的方法实现二叉树的后序遍历(顺序：左子节点->右子节点->根节点)");
        tree.postOrderRecursion(root);
        System.out.println();
        System.out.println();
        System.out.println("用堆栈的方法实现二叉树的后序遍历(顺序：左子节点->右子节点->根节点)");
        tree.postOrderStack(root);
      }
    }

在控制台的输出结果如下：  
![二叉树的执行结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1V0b3BpYU9mQXJ0b3JpYQ_size_16_color_FFFFFF_t_70 3]

### 图 ###

> 图是一种网状数据结构，由非空的顶点集合和一个描述顶点之间关系的集合组成。按顶点之间的连线是否由方向，分为：无向图、有向图。

*  图的存储方式：  
    : **邻接矩阵(adjacent matrix )**表示法是使用数组来存储图结构的方法，它采用两个数组来表示图：一个是用于存储所有顶点信息的一维数组，另一个是用于存储图中顶点之间关联关系的二维数组。

: **邻接表（adjacency list ）**是图的一种链式存储方法，邻接表表示法类似于树的孩子链表表示法。邻接表中共有两种结点结构，分别是**边表结点和表头结点**。**表头结点(data + firstedage)**，data:顶点信息，firstedage:第一条边(根顶点指向第一个子顶点的线)；**边表结点(adjvex + info + nextedge)**,adjvex:当前结点的存储位置，info:当前结点的信息，nextedge:下一条边(**根顶点指向下一个子顶点**的线)

*  图的遍历

![图样本][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1V0b3BpYU9mQXJ0b3JpYQ_size_16_color_FFFFFF_t_70 4]

**深度优先搜索（depth first search）**：类似于树的先序遍历。从图中某个顶点N出发，访问此顶点，然后依次从N的未被访问的邻接点出发深度优先遍历图，直至图中所有和N有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。**(1-2-4-8-5-3-6-7)**

**广度优先搜索（breadth first search ）**：类似于树的层次遍历。从图中某顶点N出发，在访问了N之后依次访问N的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”先被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。**(1-2-3-4-5-6-7-8)**

**用邻接矩阵**的方式实现无向矩阵及其DFS，BFS方法的实现源码如下：

import java.util.ArrayList;
    import java.util.LinkedList;
    
    /** * 邻接矩阵(Adjacency Matrix)的方式实现图(Vertex)，以及DFS，BFS方法实现 * * @author zhenye 2018/3/5 */
    public class AMVertex { 
      /** * 存储所有顶点信息的一维数组 */
      private ArrayList vertexList;
    
      /** * 与vertexList对应的数组，展示结点是否被访问过 */
      private boolean[] isVisited;
      /** * 存储图中顶点之间关联关系(边)的二维数组 */
      private int[][] edges;
      /** * 边的数目 */
      private int numOfEdges;
    
      /** * 初始化矩阵，二维数组，边的数目 * * @param n 结点数目 */
      public AMVertex(int n){ 
        vertexList = new ArrayList(n);
        isVisited = new boolean[n];
        edges = new int[n][n];
        numOfEdges = 0;
      }
    
      /** * 得到结点的个数 * * @return the num of vertex */
      public int getNumOfVertex() { 
        return vertexList.size();
      }
    
      /** * 得到边的数目 * * @return the num of edges */
      public int getNumOfEdges() { 
        return numOfEdges;
      }
    
      /** * 返回结点i的数据 * * @param i 结点的下标 * @return the value by index */
      public Object getValueByIndex(int i) { 
        return vertexList.get(i);
      }
    
      /** * 返回v1,v2的权值 * * @param v1 起始结点下标 * @param v2 终止结点下标 * @return the weight */
      public int getWeight(int v1,int v2) { 
        return edges[v1][v2];
      }
    
      /** * 在图中插入结点 * * @param vertex 待插入的结点 */
      public void insertVertex(Object vertex) { 
        vertexList.add(vertexList.size(),vertex);
      }
    
      /** * 插入边 * * @param v1 起始结点下标 * @param v2 终止结点下标 * @param weight 权重 */
      public void insertEdge(int v1,int v2,int weight) { 
        edges[v1][v2]=weight;
        numOfEdges++;
      }
    
      /** * 删除边 * * @param v1 起始结点下标 * @param v2 终止结点下标 */
      public void deleteEdge(int v1,int v2) { 
        edges[v1][v2]=0;
        numOfEdges--;
      }
    
      /** * 得到第一个邻接结点的下标 * * @param index 结点下标 * @return the first neighbor */
      public int getFirstNeighbor(int index) { 
        for(int j=0;j<vertexList.size();j++) { 
          if (edges[index][j]>0) { 
            return j;
          }
        }
        return -1;
      }
    
      /** * 根据前一个邻接结点的下标来取得下一个邻接结点 * * @param v1 根结点的下标 * @param v2 前一个子结点的下标 * @return the next neighbor */
      public int getNextNeighbor(int v1,int v2) { 
        for (int j=v2+1;j<vertexList.size();j++) { 
          if (edges[v1][j]>0) { 
            return j;
          }
        }
        return -1;
      }
    
      /** * 将isVisited中的值重置为false */
      public void resetIsVisited(){ 
        for (int i = 0;i< isVisited.length; i++) { 
          isVisited[i] = false;
        }
      }
    
      /** * 从vertexList中下标为i的结点，开始深度遍历(类似树的先序遍历) * @param i 选取的根节点下标 */
      private void depthFirstSearch(int i) { 
        // 首先访问该结点，在控制台打印出来
        System.out.print(getValueByIndex(i) + " ");
        //置该结点为已访问
        isVisited[i] = true;
    
        int w=getFirstNeighbor(i);
        while (w!=-1) { 
          if (!isVisited[w]) { 
            depthFirstSearch(w);
          }
          w=getNextNeighbor(i, w);
        }
      }
      /** * 用户调用的深度优先遍历方法 */
      public void depthFirstSearch(){ 
        for(int i=0;i<getNumOfVertex();i++) { 
          //因为对于非连通图来说，并不是通过一个结点就一定可以遍历所有结点的。
          if (!isVisited[i]) { 
            depthFirstSearch(i);
          }
        }
        // 本次遍历完后，需要重置该数组，才能保证下次也能够正常遍历
        resetIsVisited();
      }
    
      /** * 从vertexList中下标为i的结点，开始广度遍历(类似树的层次遍历) * @param i 选取的根节点下标 */
      private void broadFirstSearch(int i) { 
        int u,w;
        LinkedList queue=new LinkedList();
    
        //访问结点i
        System.out.print(getValueByIndex(i)+" ");
        isVisited[i]=true;
        //结点入队列
        queue.addLast(i);
        while (!queue.isEmpty()) { 
          u=((Integer)queue.removeFirst()).intValue();
          w=getFirstNeighbor(u);
          while(w!=-1) { 
            if(!isVisited[w]) { 
              //访问该结点
              System.out.print(getValueByIndex(w)+" ");
              //标记已被访问
              isVisited[w]=true;
              //入队列
              queue.addLast(w);
            }
            //寻找下一个邻接结点
            w=getNextNeighbor(u, w);
          }
        }
      }
    
      /** * 用户调用的广度优先遍历方法 */
      public void broadFirstSearch(){ 
        for(int i=0;i<getNumOfVertex();i++) { 
          if(!isVisited[i]) { 
            broadFirstSearch(i);
          }
        }
        // 本次遍历完后，需要重置该数组，才能保证下次也能够正常遍历
        resetIsVisited();
      }
      // 在main方法中进行测试
      public static void main(String[] args) { 
        int n=8,e=9;//分别代表结点个数和边的数目
        String labels[]={ "1","2","3","4","5","6","7","8"};//结点的标识
        AMVertex vertex = new AMVertex(n);
        for (String label : labels) { 
          vertex.insertVertex(label);
        }
        //插入九条边
        vertex.insertEdge(0, 1, 1);
        vertex.insertEdge(0, 2, 1);
        vertex.insertEdge(1, 3, 1);
        vertex.insertEdge(1, 4, 1);
        vertex.insertEdge(3, 7, 1);
        vertex.insertEdge(4, 7, 1);
        vertex.insertEdge(2, 5, 1);
        vertex.insertEdge(2, 6, 1);
        vertex.insertEdge(5, 6, 1);
    
        System.out.println("深度优先搜索序列为：");
        vertex.depthFirstSearch();
        System.out.println();
        System.out.println("深度优先搜索序列为：");
        vertex.broadFirstSearch();
      }
    }

图的遍历结果如图所示：  
![图运行结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1V0b3BpYU9mQXJ0b3JpYQ_size_16_color_FFFFFF_t_70 5]

[70]: /images/20220530/432c958a51124383aaea3c0e0adf53af.png
[70 1]: /images/20220530/66cd567272164bc5bb6bc596e458a233.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1V0b3BpYU9mQXJ0b3JpYQ_size_16_color_FFFFFF_t_70]: /images/20220530/c04225deb7054255904f1f7322b1988b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1V0b3BpYU9mQXJ0b3JpYQ_size_16_color_FFFFFF_t_70 1]: /images/20220530/b9b76f36fb2740d983e9ba8055a5c4dd.png
[70 2]: /images/20220530/ad5c683dffe14ae1b21fe68a0a3d372e.png
[70 3]: /images/20220530/7f83eeb26cf74565a32b4b7a60e1fdff.png
[70 4]: /images/20220530/808f01e1700e42819e0e53ad7f2648e3.png
[70 5]: /images/20220530/0979c030454743cbac5e7c4d18d15727.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1V0b3BpYU9mQXJ0b3JpYQ_size_16_color_FFFFFF_t_70 2]: /images/20220530/582add07043d48a692e107267c9eaa5e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1V0b3BpYU9mQXJ0b3JpYQ_size_16_color_FFFFFF_t_70 3]: /images/20220530/8214f5e4a1e64c558480b475188e627d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1V0b3BpYU9mQXJ0b3JpYQ_size_16_color_FFFFFF_t_70 4]: /images/20220530/47f47c8ac50041478a910644e3970f8a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1V0b3BpYU9mQXJ0b3JpYQ_size_16_color_FFFFFF_t_70 5]: /images/20220530/3bd0594055fd4e9e823d066b8fdc5f71.png