[数据结构与算法]数据结构全解（链，数组，栈，树，图）与算法分析（排序，查找，递归，分治，动态规划）

数据结构

数据结构包括：线性结构和非线性结构。

线性结构

• 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系
• 线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的
• 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
• 线性结构常见的有：数组、队列、链表和栈，后面我们会详细讲解.

非线性结构

• 非线性结构包括：二维数组，多维数组，广义表，树结构，图结构

稀疏数组

基本介绍

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是:

• 记录数组一共有几行几列，有多少个不同的值
• 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

应用实例

• 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
• 把稀疏数组存盘，并且可以从新恢复原来的二维数组数

整体思路分析

package dataStructure;

public class SparseArray {
    public static void main(String[] args) {
        int[][] chessArray = new int[11][11];
        chessArray[1][2]=1;
        chessArray[2][3]=2;
        for(int[] row:chessArray){
            for (int element:row) {
                System.out.print("\t"+element);
            }
            System.out.println();
        }

        //稀疏数组
        int sum=0;
        for (int i = 0; i < chessArray.length; i++) {
            for (int j = 0; j < chessArray.length; j++) {
                if (chessArray[i][j]!=0){
                   sum++;
                }
            }
        }
        System.out.println("sum="+sum);

        int[][] sparseArray=new int[sum+1][3];
        sparseArray[0][0]= chessArray.length;
        sparseArray[0][1]= chessArray.length;
        sparseArray[0][2]=sum;
        int count=1;
        for (int i = 0; i < chessArray.length; i++) {
            for (int j = 0; j < chessArray.length; j++) {
                if (chessArray[i][j]!=0){
                    sparseArray[count][0]=i;
                    sparseArray[count][1]=j;
                    sparseArray[count][2]=chessArray[i][j];
                    count++;
                }
            }
        }

        System.out.println("稀疏数组");
        for (int[] row:sparseArray){
            for (int element:row){
                System.out.print("\t"+element);
            }
            System.out.println();
        }

        //原型数组
        System.out.println("原型数组");
        int[][] chessArray1=new int[sparseArray[0][0]][sparseArray[0][1]];
        for (int i = 1; i < sparseArray.length; i++) {
            chessArray1[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
        }

        for (int[] row:chessArray1){
            for (int element:row){
                System.out.print("\t"+element);
            }
            System.out.println();
        }
        
    }
}

队列

队列介绍

• 队列是一个有序列表，可以用数组或是链表来实现。
• 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

数组模拟队列

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
• 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变

基本思想

• 将尾指针往后移：rear+1 , 当front == rear 【空】
• 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear ==maxSize - 1[队列满]

package dataStructure;


import java.util.Scanner;

public class Queue {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        boolean loop=true;
        ArrayQueue arrayQueue=new ArrayQueue(3);
        while (loop){
            System.out.println("1.显示队列"+
                                "\n2.添加数据"+
                                "\n3.取出数据"+
                                "\n4.查看头数据"+
                                "\n5.退出");
            int choice=s.nextInt();
            switch (choice){
                case 1:
                    arrayQueue.showQueue();
                    break;
                case 2:
                    int data=s.nextInt();
                    try {
                        arrayQueue.put(data);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 3:
                    try {
                        int data1=arrayQueue.get();
                        System.out.println("取出数据为"+data1);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 4:
                    try {
                        int data1=arrayQueue.getHead();
                        System.out.println("头数据为"+data1);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 5:
                    s.close();
                    loop=false;
                    System.out.println("退出");
            }
        }

    }
}
class  ArrayQueue{
    private int max;
    private int front;
    private int rear;
    private int[]  arr;

    public ArrayQueue(int max) {
        this.max = max;
        arr=new int[max];
        front=-1;
        rear=-1;
    }


    public boolean isFull(){
        return rear==max-1;
    }

    public boolean isEmpty(){
        return rear==front;
    }

    public void put(int n){
        if(isFull()){
            throw new RuntimeException("队列已满，无法添加");
        }
        rear++;
        arr[rear]=n;
    }

    public int get(){
        if (isEmpty()){
            throw  new RuntimeException("队列为空，无法取出");
        }
        int n=arr[++front];
        return n;
    }

    public int getHead(){
        if (isEmpty()){
            throw  new RuntimeException("队列为空，无法取出");
        }
        int n=arr[front+1];
        return n;
    }

    public void showQueue(){
        if (isEmpty()){
            throw  new RuntimeException("队列为空，无法取出");
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println("arr["+i+"]="+arr[i]);
        }
    }
}

环形队列

对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)

思路如下:

• front变量的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素front的初始值=0
• rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间做为约定.rear的初始值=0
• 当队列满时,条件是(rear +1)% maxSize = front【满】
• 对队列为空的条件，rear == front空
• 当我们这样分析，队列中有效的数据的个数(rear + maxSize - front) % maxSize // rear= 1 front=06.我们就可以在原来的队列上修改得到,一个环形队列

package dataStructure;

import java.util.Scanner;

public class CircleArray {

    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        boolean loop=true;
        ArrayQueue arrayQueue=new ArrayQueue(3);
        while (loop){
            System.out.println("1.显示队列"+
                    "\n2.添加数据"+
                    "\n3.取出数据"+
                    "\n4.查看头数据"+
                    "\n5.退出");
            int choice=s.nextInt();
            switch (choice){
                case 1:
                    arrayQueue.showQueue();
                    break;
                case 2:
                    int data=s.nextInt();
                    try {
                        arrayQueue.put(data);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 3:
                    try {
                        int data1=arrayQueue.get();
                        System.out.println("取出数据为"+data1);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 4:
                    try {
                        int data1=arrayQueue.getHead();
                        System.out.println("头数据为"+data1);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 5:
                    s.close();
                    loop=false;
                    System.out.println("退出");
            }
        }

    }
}
class  CircleQueue{
    private int max;
    private int front;
    private int rear;
    private int[]  arr;

    public CircleQueue(int max) {
        this.max = max;
        arr=new int[max];

    }

    public boolean isFull(){
        return (rear+1)%max==front;
    }

    public boolean isEmpty(){
        return rear==front;
    }

    public void put(int n){
        if(isFull()) {
            throw new RuntimeException("队列已满，无法添加");
        }
        arr[rear]=n;
        rear=(rear+1)%max;
    }

    public int get(){
        if (isEmpty()){
            throw  new RuntimeException("队列为空，无法取出");
        }
        int n=arr[front];
        front=(front+1)%max;
        return n;
    }

    public int getHead(){
        if (isEmpty()){
            throw  new RuntimeException("队列为空，无法取出");
        }
        int n=arr[front+1];
        return n;
    }

    public void showQueue(){
        if (isEmpty()){
            throw  new RuntimeException("队列为空，无法取出");
        }
        for (int i = 0; i < front+size(); i++) {
            System.out.println("arr["+i+"]="+arr[i]);
        }
    }

    public int size(){
        return (rear+max-front)%max;
    }
}

单向链表

• 链表是以节点的方式来存储,是链式存储
• 每个节点包含 data 域， next 域：指向下一个节点.
• 链表的各个节点不一定是连续存储.
• 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

单链表(带头结点) 逻辑结构示意图如下

添加节点（创建

• 1.先创建一个head头节点,作用就是表示单链表的头
• 2.后面我们每添加一个节点,就直接加入到链表的最后遍历:
• 3.通过一个辅助变量遍历,帮助遍历整个链表
  

package dataStructure;

//单链表
public class SingleLinkedList {
    public static void main(String[] args) {
        Single single=new Single();
        Node node1=new Node(1,"aaa");
        Node node2=new Node(2,"bbb");
        Node node3=new Node(3,"ccc");
        //添加节点
        single.add(node1);
        single.add(node3);
        single.add(node2);
        //展示链表
        single.list();
    }

}
class Single{
    private Node head=new Node(0,"");

    public  void add(Node node){
        Node temp=head;
        while (true){
            if(temp.next==null){
                break;
            }
            temp=temp.next;
        }
        temp.next=node;
    }

    public void list(){
        if(head.next==null){
            return;
        }
        Node temp=head.next;
        while (true){
            if(temp==null){
                break;
            }
            System.out.println(temp);
            temp=temp.next;
        }
    }
}
class Node{
    int no;
    String name;
    Node next;

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name+"}";
    }
}

顺序添加

• 1.首先找到新添加的节点的位置,是通过辅助变量(指针),通过遍历来搞定
• 2.新的节点.next=temp.next
• 3.将temp.next=新的节点
  

package dataStructure;

class Single{
    private Node head=new Node(0,"");

    public void addByOrder(Node node){
        Node temp=head;
        boolean flag=false;
        while (true){
            if(temp.next==null){
                break;
            }
            if(temp.next.no>node.no){
                break;
            }else if(temp.next.no== node.no) {
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            System.out.println(node.no+"节点已经存在");
        }else {
            node.next=temp.next;
            temp.next=node;
        }
    }
}

修改节点

• 1.先找到该节点，通过遍历
• 2.temp.name=Node.name （修改节点名字）

package dataStructure;


class Single{
    private Node head=new Node(0,"");

    public void update(Node node){
        if(head.next==null){
            return;
        }
        Node temp=head.next;
        boolean flag=false;
        while (true){
            if(temp==null){
                break;
            }
            if (temp.no== node.no){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if(flag){
            temp.name=node.name;
        }else {
            System.out.println("没有找到"+node.no+"节点");
        }
    }
}

删除节点

• 1.我们先找到需要删除的这个节点的前一个节点temp
• 2.temn.next =temp.next.next
• 3.被删除的节点,将不会有其它引用指向，会被垃圾回收机制回收
  

package dataStructure;

class Single{
    private Node head=new Node(0,"");

    public void  del(Node node){
        Node temp=head;
        boolean flag=false;
        while(true){
            if(temp.next==null){
                break;
            }
            if(temp.next.no==node.no){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            temp.next=temp.next.next;
        }else {
            System.out.println(node.no+"节点不存在");
        }
    }
}

获取有效节点个数

 //获取有效节点个数
    public static int getLength(Node head){
        if(head.next==null){
            return 0;
        }
        Node cur=head.next;
        int length=0;
        while (cur!=null){
            length++;
            cur=cur.next;
        }
        return length;
    }

获取倒数第index个节点

• 1.编写一个方法，接收head节点，同时接收一个index
• 2.index表示是倒数第index个节点
• 3.先把链表从头到尾遍历，得到链表的总的长度getLength
• 4.得到size后，我们从链表的第一个开始遍历(size-index)个，就可以得到
• 5.如果找到了，则返回该节点，否则返回nul

public Node findLastIndexNode(Node head,int index){
        if (head.next==null){
            return null;
        }
        int size=getLength(head);
        if (index<0||index>size){
            return null;
        }
        Node cur=head.next;
        for (int i = 0; i < size-index; i++) {
            cur=cur.next;
        }
        return cur;
    }

反转单链表

• 1.先定义一个节点 reverseHead =new HeroNode();
• 2.从头到尾遍历原来的链表,每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
• 3.原来的链表的head.next =reverseHead.next

 //翻转单链表
    public static void reverseList(Node head){
        if (head.next==null||head.next.next==null){
            return;
        }
        Node cur=head.next;
        Node next=null;
        Node reverse=new Node(0,"");
        while (cur!=null){
            next=cur.next;
            cur.next=reverse.next;
            reverse.next=cur;
            cur=next;
        }
        head.next=reverse.next;
    }

双向链表

单向链表缺点

• 1)单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
• 2)单向链表不能自我删除，需要靠辅助节点﹐而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点

遍历

• (1)遍历方和单链表一样，可以向前，也可以向后查找

添加（默认添加到双向链表的最后)

• (1)先找到双向链表的最后这个节点
• (2) temp.next= newHeroNode
• (3) newHeroNode.pre = temp;

修改（思路和单向链表一样）
删除

• (1)直接找到要删除的这个节点，比如 temp
• (2)temp.pre.next =temp.next;
• (3) temp.next.pre =temp.pre;

package dataStructure;

//双向链表
public class DoubleLinkedList {
    public static void main(String[] args) {
        Double aDouble = new Double();
        Node1 node1=new Node1(1,"aaa");
        Node1 node2=new Node1(2,"bbb");
        Node1 node3=new Node1(3,"ccc");
        //添加节点
        aDouble.add(node1);
        aDouble.add(node2);
        aDouble.add(node3);
        aDouble.del(node2);
        aDouble.list();
    }
}
class Double{
    private Node1 head=new Node1(0,"");

    public Node1 getHead() {
        return head;
    }
    //添加节点
    public  void add(Node1 node){
        Node1 temp=head;
        while (true){
            if(temp.next==null){
                break;
            }
            temp=temp.next;
        }
        temp.next=node;
        node.pre=temp;
    }

    //更新节点
    public void update(Node1 node){
        if(head.next==null){
            return;
        }
        Node1 temp=head.next;
        boolean flag=false;
        while (true){
            if(temp==null){
                break;
            }
            if (temp.no== node.no){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if(flag){
            temp.name=node.name;
        }else {
            System.out.println("没有找到"+node.no+"节点");
        }
    }

    //删除节点
    public void  del(Node1 node){
        Node1 temp=head.next;
        boolean flag=false;
        while(true){
            if(temp==null){
                break;
            }
            if(temp.no==node.no){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            node.pre.next=node.next;
            if (temp.next!=null){
                node.next.pre=node.pre;
            }
        }else {
            System.out.println(node.no+"节点不存在");
        }
    }
    public void list(){
        if(head.next==null){
            return;
        }
        Node1 temp=head.next;
        while (true){
            if(temp==null){
                break;
            }
            System.out.println(temp);
            temp=temp.next;
        }
    }
}
class Node1{
    int no;
    String name;
    Node1 next;
    Node1 pre;

    public Node1(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name+"}";
    }
}

环形单向链表

构建

• 1.先创建第一个节点,让first指向该节点,并形成环形
• 2.后面当我们每创建一个新的节点,就把该节点，加入到已有的环形链表中即可.

遍历环形链表

• 1.先让一个铺助指针(变量)curBoy，指向first节点
• 2.然后通过一个while循环遍历该环形链表即可 curBoy.next == first结束

package dataStructure;

public class Josepfu {
    public static void main(String[] args) {
        CircleSingeLinkedList circleSingeLinkedList=new CircleSingeLinkedList();
        circleSingeLinkedList.addBoy(5);
        circleSingeLinkedList.list();
    }
}
//环形链表
class CircleSingeLinkedList{
    Boy first=new Boy(-1);

    public void addBoy(int num){
        if (num<1){
            return;
        }
        Boy curBoy=first;
        for (int i = 0; i <= num; i++) {
            Boy boy=new Boy(i);
            if (i==1){
                first=boy;
                first.setNext(first);
                curBoy=first;
            }else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy=boy;
            }
        }
    }

    public void list(){
        if(first==null){
            System.out.println("环形链表为空");
        }
        Boy curBoy=first;
        while (true){
            System.out.println(curBoy.getNo());
            if(curBoy.getNext()==first){
                break;
            }
            curBoy=curBoy.getNext();
        }
    }
}

class Boy{
    private int no;
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}

约瑟夫问题

Josephu问题为:设编号为1，2， n的n个人围坐一圈,约定编号为k (1<=k=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

n=5,有5个人
k=1,从第一个人开始报数
m =2,数2下

出圈思路

• 1.需求创建一个辅助指针(变量) helper ,事先应该指向环形链表的最后这个节点.
• 2.报数前,先让first和 helper移动k-1次
• 3.当报数时，让first和helper指针同时的移动m-1次这时就可以将first指向的节点出圈

first = first.next
helper.next = first

原来first指向的节点就没有任何引用,就会被回收

package dataStructure;
//约瑟夫问题
public class Josepfu {
    public static void main(String[] args) {
        CircleSingeLinkedList circleSingeLinkedList=new CircleSingeLinkedList();
        circleSingeLinkedList.countBoy(1,2,5);
    }
}
//环形链表
class CircleSingeLinkedList{
    Boy first=new Boy(-1);


    public void countBoy(int startNo,int countNum,int num){
        if(first==null||startNo>num||startNo<1){
            return;
        }
        Boy helper=first;
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }
        for (int i = 0; i < startNo-1; i++) {
            first=first.getNext();
            helper=helper.getNext();
        }

        while (first != helper) {
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.println(first.getNo() + "号出圈");
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println(first.getNo()+"最后在圈中");
    }
}

class Boy{
    private int no;
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}

栈

• 1)栈的英文为(stack)
• 2)栈是一个先入后出(FILO-First In Last Out)的有序列表。
• 3)栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
• 4 )根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

栈的实现思路

• 1.定义一个top来表示柱顶，初始化-1
• 2.入栈的操作,当有数据加入到栈时，top++; stack[top] = data;
• 3.出栈的操作，int value = stack[top]; top–

package dataStructure;

import java.util.Scanner;

public class Stack {
    public static void main(String[] args) {
        ArrayStack arrayStack=new ArrayStack(5);
        boolean flag=true;
        while (flag) {
            System.out.println("----------菜单----------");
            System.out.println("1.放入数据\n"+
                    "2.取出数据\n"+
                    "3.显示全部\n"+
                    "4.退出\n"+
                    "请选择：");
            Scanner scanner=new Scanner(System.in);
            int choice = scanner.nextInt();
            switch (choice) {
                case (1):
                    System.out.println("输入数据：");
                    int num = scanner.nextInt();
                    arrayStack.push(num);
                    break;
                case (2):
                    try {
                        arrayStack.pop();
                        break;
                    } catch (Exception e) {
                        e.getMessage();
                    }
                case (3):
                    arrayStack.show();
                    break;
                case (4):
                    scanner.close();
                    flag = false;
                    break;
            }
        }
    }
}

class ArrayStack{
    int max;
    int top=-1;
    int[] stack;

    public ArrayStack(int max) {
        this.max = max;
        stack=new int[this.max];
    }

    public boolean isFull(){

        return top==max-1;
    }

    public boolean isEmpty(){
        return top==-1;
    }

    public void push(int num){
        if (isFull()){
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top]=num;
    }

    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空");
        }
        int num=stack[top];
        top--;
        System.out.println("取出数据："+num);
        return num;
    }

    public void show(){
        if (isEmpty()){
            System.out.println("栈空");
            return;
        }
        for (int i = top; i >=0 ; i--) {
            System.out.println("数据"+stack[i]);
        }
    }
}

综合计算器

计算思路

• 1.通过一个index值（索引）,来遍历我们的表达式
• 2.如果发现是一个数字,直接入数栈
• 3.如果发现扫描到是一个符号,就分如下情况
• 3.1如果发现当前的符号栈为空,就直接入栈
• 3.2如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于截中的操作符,就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符,就直接入符号栈.
• 4.当表达式扫描完毕,就顺序的从数栈和符号栈中pop出相应的数和符号,并运行.
• 5.最后在数栈只有一个数字,就是表达式的结果

package dataStructure;

public class Calculator {
    public static void main(String[] args) {
        String formula="7*4+1-3";
        ArrayStack2 num=new ArrayStack2(10);
        ArrayStack2 symbol=new ArrayStack2(10);
        int index=0;
        int sum=0;
        int num1=0;
        int num2=0;
        int oper=0;
        char ch=' ';
        StringBuilder keepNum= new StringBuilder();
        while (index<=formula.length()-1){
            ch=formula.substring(index,index+1).charAt(0);
            if(symbol.isSymbol(ch)){
                if(!symbol.isEmpty()){
                    if(symbol.priority(ch)<=symbol.top){
                        num1=num.pop();
                        num2=num.pop();
                        oper=symbol.pop();
                        sum=symbol.sum(num1,num2,oper);
                        num.push(sum);
                        symbol.push(ch);
                    }else {
                        symbol.push(ch);
                    }
                }else {
                    symbol.push(ch);
                }
            }else {
                keepNum.append(ch);
                if(index==formula.length()-1){
                    num.push(Integer.parseInt(keepNum.toString()));
                }
                else {
                    if(symbol.isSymbol(formula.substring(index+1,index+2).charAt(0))){
                        num.push(Integer.parseInt(keepNum.toString()));
                        keepNum = new StringBuilder();
                    }
                }
            }
            index++;
        }
        while (!symbol.isEmpty()){
            num1=num.pop();
            num2=num.pop();
            oper=symbol.pop();
            sum=num.sum(num1,num2,oper);
            num.push(sum);

        }
        int res=num.pop();
        System.out.println("结果为："+res);
    }

}
class ArrayStack2{
    int max;
    int top=-1;
    int[] stack;

    public ArrayStack2(int max) {
        this.max = max;
        stack=new int[this.max];
    }

    public boolean isFull(){

        return top==max-1;
    }

    public boolean isEmpty(){
        return top==-1;
    }

    public int getTop(){
        return stack[top];
    }

    public void push(int num){
        if (isFull()){
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top]=num;
    }

    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("栈空");
        }
        int num=stack[top];
        top--;
        System.out.println("取出数据："+num);
        return num;
    }

    public void show(){
        if (isEmpty()){
            System.out.println("栈空");
            return;
        }
        for (int i = top; i >=0 ; i--) {
            System.out.println("数据"+stack[i]);
        }
    }

    public int priority(int symbol){
        if(symbol=='*'||symbol=='/'){
            return 1;
        }
        else if(symbol=='+'||symbol=='-'){
            return 0;
        }else {
            return -1;
        }
    }

    public int sum(int num1,int num2,int symbol){
        int sum=0;
        if(symbol=='*'){
            sum=num1*num2;
        }else if(symbol=='/'){
            sum=num2/num1;
        }else if(symbol=='+'){
            sum=num2+num1;
        }else if(symbol=='-'){
            sum=num2-num1;
        }
        return sum;
    }

    public boolean isSymbol(int symbol){
        return symbol=='*'||symbol=='/'||symbol=='+'||symbol=='-';
    }
}

后缀表达式（逆波兰表达式）

思路分析：
例:(7+1)-3*6对应的后缀表达式就是7 1 + 3 6 * -

• 1．从左至右扫描，将7和1压入堆栈;
• 2．遇到+运算符，因此弹出7和1(1为栈顶元素，7为次顶元素)，计算出7+1的值，得8，再将8入栈;
• 3．将3,6入栈;
• 4．接下来是运算符，因此弹出3和6，计算出36=18，将18入栈;
• 5．最后是-运算符，计算出10-18的值，即-10，由此得出最终结果

package dataStructure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

//逆波兰表达式（后缀表达式）
public class PostfixExpression {
    public static void main(String[] args) {
        //(7+1)-3*6
        String suffixExpression = "7 1 + 3 6 * -";
        List<String> list = getList(suffixExpression);
        int calculate = calculate(list);
        System.out.println(calculate);
    }

    public static List<String> getList(String suffixExpression) {
        String[] s = suffixExpression.split(" ");
        return new ArrayList<>(Arrays.asList(s));
    }

    public static int calculate(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String num : list) {
            if (num.matches("\\d")) {
                stack.push(num);
            } else {
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = sum(num1, num2, num);
                stack.push(""+res);
            }
        }
        return Integer.parseInt(stack.pop());
    }

        public static int sum ( int num1, int num2, String symbol){
            int res = 0;
            switch (symbol) {
                case "+":
                    res = num1 + num2;
                    break;
                case "-":
                    res = num1 - num2;
                    break;
                case "*":
                    res = num1 * num2;
                    break;
                case "/":
                    res = num1 / num2;
            }
            return res;
        }
    }

中缀转后缀表达式

思想路线

• 1)初始化两个核:运算符栈s1和储存中间结果的栈s2
• 2)从左至右扫描中缀表达式;
• 3)遇到操作数时,将其压s2;
• 4)遇到运算符时,比较其与s1核顶运算符的优先级:
• （1）.如果s1为空,或核顶运算符为左括号“(,则直接将此运算符入栈;
• （2）.否则,若优先级比栈顶运算符的高,也将运算符压入s1
• （3）.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较;
• 5)遇到括号时:
• （1）如果是左括号“(",则直接压入s
• （2）如果是右括号“)"，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
• 6重复步骤2至5，直到表达式的最右边
• 7将s1中剩余的运算符依次弹出并压入s2
• 8依次弹出s2中的元素并输出，结果的逆序为中缀表达式对应的后缀表达式

public static List<String> parseSuffixExpression(List<String> list){
        Stack<String> s1=new Stack<>();
        List<String> s2=new ArrayList<>();
        for (String item:list){
            if (item.matches("\\d")) {
                s2.add(item);
            }else if(item.equals("(")){
                s1.push(item);
            }else if(item.equals(")")){
                while (!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                s1.pop();
            }else {
                while (s1.size()!=0&&priority(item)<=priority(s1.peek())){
                    s2.add(s1.pop());
                }
                s1.push(item);
            }

        }
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;
    }

    public static List<String> getExpressionList(String suffixExpression){
        List<String> list=new ArrayList<>();
        int index = 0;
        char ch;
        String str;
        do {
            if((ch=suffixExpression.charAt(index))<48||(ch=suffixExpression.charAt(index))>57){
                list.add(String.valueOf(ch));
                index++;
            }else {
                str="";
                while (index<suffixExpression.length()&&(ch=suffixExpression.charAt(index))>=48&&(ch=suffixExpression.charAt(index))<=57){
                    str+=ch;
                    index++;
                }
                list.add(str);
            }
        }while (index<suffixExpression.length());
            return list;
    }

完整版

package dataStructure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

//逆波兰表达式（后缀表达式）
public class PostfixExpression {
    public static void main(String[] args) {
        //(7+1)-3*6
        String suffixExpression = "(7+1)-3*6";
        List<String> list = getExpressionList(suffixExpression);
        System.out.println(list);

        List<String> list1 = parseSuffixExpression(list);
        System.out.println(list1);
        int calculate = calculate(list1);
        System.out.println(calculate);
    }

    public static List<String> parseSuffixExpression(List<String> list){
        Stack<String> s1=new Stack<>();
        List<String> s2=new ArrayList<>();
        for (String item:list){
            if (item.matches("\\d")) {
                s2.add(item);
            }else if(item.equals("(")){
                s1.push(item);
            }else if(item.equals(")")){
                while (!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                s1.pop();
            }else {
                while (s1.size()!=0&&priority(item)<=priority(s1.peek())){
                    s2.add(s1.pop());
                }
                s1.push(item);
            }

        }
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;
    }

    public static List<String> getExpressionList(String suffixExpression){
        List<String> list=new ArrayList<>();
        int index = 0;
        char ch;
        String str;
        do {
            if((ch=suffixExpression.charAt(index))<48||(ch=suffixExpression.charAt(index))>57){
                list.add(String.valueOf(ch));
                index++;
            }else {
                str="";
                while (index<suffixExpression.length()&&(ch=suffixExpression.charAt(index))>=48&&(ch=suffixExpression.charAt(index))<=57){
                    str+=ch;
                    index++;
                }
                list.add(str);
            }
        }while (index<suffixExpression.length());
            return list;
    }

    public static List<String> getList(String suffixExpression) {
        String[] s = suffixExpression.split(" ");
        return new ArrayList<>(Arrays.asList(s));
    }

    public static int calculate(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String num : list) {
            if (num.matches("\\d")) {
                stack.push(num);
            } else {
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = sum(num1, num2, num);
                stack.push(""+res);
            }
        }
        return Integer.parseInt(stack.pop());
    }

    public static int priority(String symbol){
        int res=0;
        switch(symbol){
            case "+":
            case "-":
                res=1;
                break;
            case "*":
            case "/":
                res=2;
                break;
        }
        return res;
    }

        public static int sum ( int num1, int num2, String symbol){
            int res = 0;
            switch (symbol) {
                case "+":
                    res = num1 + num2;
                    break;
                case "-":
                    res = num1 - num2;
                    break;
                case "*":
                    res = num1 * num2;
                    break;
                case "/":
                    res = num1 / num2;
            }
            return res;
        }
    }

哈希表

散列表(Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

package dataStructure;

import java.util.Objects;
import java.util.Scanner;

//哈希表
public class HashTable {
    public static void main(String[] args) {
        HashTab hashTab=new HashTab(7);
        boolean flag=true;
        while (flag) {
            System.out.println("----------菜单----------");
            System.out.println("1.添加数据\n"+
                    "2.查找数据\n"+
                    "3.删除数据\n"+
                    "4.显示全部\n"+
                    "5.退出\n"+
                    "请选择：");
            Scanner scanner=new Scanner(System.in);
            int choice = scanner.nextInt();
            switch (choice) {
                case (1):
                    System.out.println("输入id和name：");
                    int id = scanner.nextInt();
                    String name=scanner.next();
                    Emp emp=new Emp(id,name);
                    hashTab.add(emp);
                    break;
                case (2):
                    System.out.println("输入id：");
                    int id1 = scanner.nextInt();
                    hashTab.findById(id1);
                    break;
                case (3):
                    System.out.println("输入id：");
                    int id2 = scanner.nextInt();
                    hashTab.delete(id2);
                    break;
                case (4):
                    hashTab.list();
                case (5):
                    scanner.close();
                    flag = false;
                    break;
            }
        }
    }
}
class HashTab{
    private final int size;
    private final LinkListed[] empHashTable;
    public HashTab(int size){
        this.size=size;
        empHashTable=new LinkListed[size];
        for (int i = 0; i < size; i++) {
            empHashTable[i]=new LinkListed();
        }
    }

    public void add(Emp emp){
        int empHashTableIndex=hashFun(emp.id);
        empHashTable[empHashTableIndex].add(emp);
    }

    public void list(){
        for (int i = 0; i < size; i++) {
            empHashTable[i].list(i);
        }
    }

    public void findById(int id){
        int empHashTableIndex=hashFun(id);
        Emp emp=empHashTable[empHashTableIndex].findById(id);
        if (emp!=null){
            System.out.println(id+"数据在"+"第"+empHashTableIndex+"链表上");
        }else {
            System.out.println("没有该数据");
        }
    }

    public void delete(int id){
        int empHashTableIndex=hashFun(id);
        empHashTable[empHashTableIndex].delete(id);
    }

    public int hashFun(int id){
        return id%size;
    }
}

class Emp{
    int id;
    String name;
    Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

class LinkListed{
    private Emp head;
    public void add(Emp emp){
        if (head==null){
            head=emp;
        }
        Emp curEmp=head;
        while (curEmp.next!=null){
            curEmp=curEmp.next;
        }
        curEmp.next=emp;
    }

    public void list(int no){
        if (head==null){
            System.out.println("第"+(no+1)+"行没有元素");
            return;
        }
        System.out.println("第"+(no+1)+"行数据：");
        Emp curEmp=head;
        while (true) {
            System.out.println("id:" + curEmp.id + "name:" + curEmp.name);
            if (curEmp.next == null){
                break;
            }
            curEmp = curEmp.next;
        }
        System.out.println();
    }

    public Emp findById(int id){
        if (head==null){
            System.out.println("没有数据");
        }
        Emp curEmp=head;
        while (true){
            if (curEmp.id==id){
                break;
            }
            if (curEmp.next == null) {
                curEmp=null;
                break;
            }
            curEmp=curEmp.next;
        }
        return curEmp;
    }

    public void delete(int id){
        if (head==null){
            System.out.println("没有数据");
        }
        Emp curEmp=head;
        while (true){
            if (curEmp.next==null){
                break;
            }
            if (curEmp.next.id==id){
                curEmp.next=null;
                break;
            }
            curEmp=curEmp.next;
        }
    }
}

树

树的存储方式
能提高数据存储，读取的效率，比如利用二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

树的常用术语

• 1)节点
• 2)根节点
• )父节点
• 4)子节点
• 5)叶子节点(没有子节点的节点)
• 6)节点的权(节点值)
• 7)路径(从root节点找到该节点的路线)
• 8)层
• 9)子树
• 10)树的高度(最大层数)
• 11)森林:多颗子树构成森林

二叉树

（1）
树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。

（2）
如果该二叉树的所有叶子节点都在最后一层，并且结点总数=2^n-1 , n为层数，则我们称为满二叉树。

（3）

如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树

1)前序遍历:先输出父节点，再遍历左子树和右子树
2)中序遍历:先遍历左子树，再输出父节点，再遍历右子树
3)后序遍历:先遍历左子树，再遍历右子树，最后输出父节点
4)小结:看输出父节点的顺序，就确定是前序，中序还是后序

二叉树的前序，中序,后序的遍历步骤

• 1.创建一颗二叉树
• 2.前序遍历（1,2,4,5,3,6）
  2.1先输出当前节点(初始的时候是root节点)
  2.2如果左子节点不为空,则递归继续前序遍历
  2.3如果右子节点不为空，则递归继续前序遍历
• 3.中序遍历（4,2,5,1,6,3）
  3.1如果当前节点的左子节点不为空,则递归中序遍历
  3.2输出当前节点
  3.2如果当前节点的右子节点不为空,则递归中序遍历
• 4.后序遍历（4,5,2,6,3,1）
  4.1如果当前节点的左子节点不为空,则递归后序遍历
  4.2如果当前节点的右子节点不为空,则递归后序遍历
  4.3输出当前节点
  

package dataStructure;

//二叉树
public class BinaryTree {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1,"1");
        TreeNode node2=new TreeNode(2,"2");
        TreeNode node3=new TreeNode(3,"3");
        TreeNode node4=new TreeNode(4,"4");
        TreeNode node5=new TreeNode(5,"5");
        TreeNode node6=new TreeNode(6,"6");

        Tree tree=new Tree(root);
        root.left=node2;
        root.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;

//        tree.perOrder();
//        tree.infixOrder();
//        tree.postOrder();
    }
}
class Tree{
    private final TreeNode root;

    public Tree(TreeNode root) {
        this.root = root;
    }
    //前序
    public void perOrder(){
        System.out.println(this);
        if (root!=null){
            root.perOrder();
        }else {
            System.out.println("没有数据");
        }
    }
    //中序
    public void infixOrder(){
        System.out.println(this);
        if (root!=null){
            root.infixOrder();
        }else {
            System.out.println("没有数据");
        }
    }
    //后序
    public void postOrder(){
        System.out.println(this);
        if (root!=null){
            root.postOrder();
        }else {
            System.out.println("没有数据");
        }
    }
}

class TreeNode{
    int no;
    String name;
    TreeNode left;
    TreeNode right;

    public TreeNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "no=" + no +
                ", name=" + name +
                '}';
    }

    //前序
    public void perOrder(){
        System.out.println(this);
        if (this.left!=null){
            this.left.perOrder();
        }
        if (this.right!=null){
            this.right.perOrder();
        }
    }
    //中序
    public void infixOrder(){
        if (this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right!=null){
            this.right.infixOrder();
        }
    }
    //后序
    public void postOrder(){
        if (this.left!=null){
            this.left.postOrder();
        }
        if (this.right!=null){
            this.right.postOrder();
        }
        System.out.println(this);
    }
}

二叉树前序，中序，后序查找
前序查找思路

• 1.先判断当前结点的no是否等于要查找的
• 2.如果是相等,则返回当前结点
• 3.如果不等，则判断当前结点的左子节点是否为空,如果不为空，则递归前序查找
• 4.如果左递归前序查找，找到结点，则返回，否继续判断，当前的结点的右子节点是否为空,如果不空，则继续向右递归前序查找.

中序查找思路

• 1.判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
• 2如果找到，则返回,如果没有找到,就和当前结点比较,如果是则返回当前结点,否则继续进行右递归的中序查找
• 3.如果右递归中序查找,找到就返回，否则返回null

后序查找思路

• 1.判断当前结点的左子节点是否为空,如果不为空,则递归后序查找
• 2如果找到,就返回,如果没有找到，就判断当前结点的右子节点是否为空,如果不为空,则右递归进行后序查找,如果找到,就返回
• 3.就和当前结点进行,比如,如果是则返回,否则返回null

package dataStructure;

//二叉树
public class BinaryTree {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1,"1");
        TreeNode node2=new TreeNode(2,"2");
        TreeNode node3=new TreeNode(3,"3");
        TreeNode node4=new TreeNode(4,"4");
        TreeNode node5=new TreeNode(5,"5");
        TreeNode node6=new TreeNode(6,"6");

        Tree tree=new Tree(root);
        root.left=node2;
        root.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;

    }
}
class Tree{
    private final TreeNode root;

    public Tree(TreeNode root) {
        this.root = root;
    }
    

    public void perOrderSearch(int no){
        if (root!=null){
            TreeNode node = root.perOrderSearch(no);
            System.out.println(node);
        }
    }

    public void infixOrderSearch(int no){
        if (root!=null){
            TreeNode node = root.infixOrderSearch(no);
            System.out.println(node);
        }
    }
    public void postOrderSearch(int no){
        if (root!=null){
            TreeNode node = root.postOrderSearch(no);
            System.out.println(node);
        }
    }
}

class TreeNode{
    int no;
    String name;
    TreeNode left;
    TreeNode right;

    public TreeNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "no=" + no +
                ", name=" + name +
                '}';
    }


    public TreeNode perOrderSearch(int no){
        if (this.no==no){
            return this;
        }
        TreeNode node = null;
        if (this.left!=null){
            node=this.left.perOrderSearch(no);
        }
        if (node!=null){
            return node;
        }
        if (this.right!=null){
            node=this.right.perOrderSearch(no);
        }
        return node;
    }

    public TreeNode infixOrderSearch(int no){
        TreeNode node = null;
        if (this.left!=null){
            node=this.left.infixOrderSearch(no);
        }
        if (node!=null){
            return node;
        }
        if (this.no==no){
            return this;
        }

        if (this.right!=null){
            node=this.right.infixOrderSearch(no);
        }
        return node;
    }

    public TreeNode postOrderSearch(int no){
        TreeNode node = null;
        if (this.left!=null){
            node=this.left.postOrderSearch(no);
        }
        if (node!=null){
            return node;
        }
        if (this.right!=null){
            node=this.right.postOrderSearch(no);
        }
        if (node!=null){
            return node;
        }
        if (this.no==no){
            return this;
        }
        return node;
    }
}

删除节点
删除结点的规定:

• 1)如果删除的节点是叶子节点，则删除该节点
• 2)如果删除的节点是非叶子节点,则删除该子树

思路

• 考虑如果树是空树root ,如果只有一个root结点,则等价将二叉树置空
• 1.因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是转需要删除结点，而不能去判断当前这个结点是不是需要删除结点.
• 2如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将this.left=null;并且就返回(结束递归删除)
• 3.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null;并且就返回(结束递归删除)
• 4.如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
• 5.如果第4步也没有删除结点,则应当向右子树进行递归删除.

package dataStructure;

//二叉树
public class BinaryTree {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1,"1");
        TreeNode node2=new TreeNode(2,"2");
        TreeNode node3=new TreeNode(3,"3");
        TreeNode node4=new TreeNode(4,"4");
        TreeNode node5=new TreeNode(5,"5");
        TreeNode node6=new TreeNode(6,"6");

        Tree tree=new Tree(root);
        root.left=node2;
        root.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;

        tree.delete(5);
        tree.perOrder();
    }
}
class Tree{
    private TreeNode root;

    public Tree(TreeNode root) {
        this.root = root;
    }
  

    public void delete(int no){
        if (root!=null){
            if (root.no==no){
                root=null;
            }else {
                root.delete(no);
            }
        }else {
            System.out.println("没有数据");
        }
    }
}

class TreeNode{
    int no;
    String name;
    TreeNode left;
    TreeNode right;

    public TreeNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "no=" + no +
                ", name=" + name +
                '}';
    }


    public void delete(int no){
        if (this.left!=null&&this.left.no==no){
            this.left=null;
            return;
        }
        if (this.right!=null&&this.right.no==no){
            this.right=null;
            return;
        }
        if (this.left!=null){
            this.left.delete(no);
        }
        if (this.right!=null){
            this.right.delete(no);
        }
    }
}

顺序存储二叉树

基本说明
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，

顺序存储二叉树的特点:

• 1)顺序二叉树通常只考虑完全二叉树
• 2)第n个元素的左子节点为2*n+1
• 3)第n个元素的右子节点为2*n+2
• 4)第n个元素的父节点为(n-1)/ 2
• 5)n :表示二叉树中的第几个元素(按0开始编号如图所示)

package dataStructure;

public class ArrBinaryTree {
    public static void main(String[] args) {
        int[] arr={1,2,3,4,5};
        ArrTree tree=new ArrTree(arr);
        tree.perOrder();
        tree.infixOrder();
        tree.postOrder();
    }
}
class ArrTree{
    private int[] arr;

    public ArrTree(int[] arr) {
        this.arr = arr;
    }

    public void perOrder(){
        this.perOrder(0);
    }
    public void infixOrder(){
        this.infixOrder(0);
    }
    public void postOrder(){
        this.postOrder(0);
    }
    public void perOrder(int index){
        if (arr == null) {
            assert false;
            if (arr.length<=0) {
                System.out.println("数组为空");
            }
        }
        System.out.println(arr[index]);
        if (2*index+1< arr.length) {
            perOrder(2*index+1);
        }
        if (2*index+2<arr.length){
            perOrder(2*index+2);
        }
    }

    public void infixOrder(int index){
        if (arr == null) {
            assert false;
            if (arr.length<=0) {
                System.out.println("数组为空");
            }
        }
        
        if (2*index+1< arr.length) {
            infixOrder(2*index+1);
        }
        System.out.println(arr[index]);
        if (2*index+2<arr.length){
            infixOrder(2*index+2);
        }
    }

    public void postOrder(int index){
        if (arr == null) {
            assert false;
            if (arr.length<=0) {
                System.out.println("数组为空");
            }
        }
        if (2*index+1< arr.length) {
            postOrder(2*index+1);
        }
        if (2*index+2<arr.length){
            postOrder(2*index+2);
        }
        System.out.println(arr[index]);
    }
}

线索化二叉树

充分的利用各个节点的左右指针，让各个节点可以指向自己的前后节点-线索二叉树
基本概念

• 1)n个结点的二叉链表中含有n+l【公式2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索")
• 2)这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
• 3)一个结点的前一个结点，称为前驱结点
• 4)一个结点的后一个结点，称为后继结点

说明:当线索化二叉树后，Node节点的属性 left和 right ，有如下情况:

• l1) left 指向的是左子树，也可能是指向的前驱节点.比如①节点left 指向的左子树,而⑩节点的 left 指向的就是前驱节点.
• 2)right 指向的是右子树，也可能是指向后继节点，比如①节点right 指向的是右子树，而⑩节点的 right 指向的是后继节点.

package dataStructure.BinaryTree;

//线索化二叉树
public class ThreadedBinaryTree {
    public static void main(String[] args) {
        Node root=new Node(1,"1");
        Node node2=new Node(2,"2");
        Node node3=new Node(3,"3");
        Node node4=new Node(4,"4");
        Node node5=new Node(5,"5");
        Node node6=new Node(6,"6");

        ThreadedTree tree=new ThreadedTree(root);
        root.left=node2;
        root.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;

        tree.threadedNode();
//        Node left = node6.left;
//        System.out.println(left);
        tree.ThreadedList();

    }
}

class ThreadedTree {
    private final Node root;
    private Node pre;

    public ThreadedTree(Node root) {
        this.root = root;
    }

    public void threadedNode(){
        this.threadedNode(root);
    }

    public void threadedNode(Node node){
        if (node==null){
            return;
        }
        threadedNode(node.left);

        if (node.left==null){
            node.left=pre;
            node.leftType=1;
        }
        if (pre!=null&&pre.right==null){
            pre.right=node;
            pre.rightType=1;
        }
        pre=node;

        threadedNode(node.right);
    }


    public void ThreadedList(){
        Node node=root;
        while (node!=null){
            while (node.leftType == 0) {
                node=node.left;
            }
            System.out.println(node);

            while (node.rightType==1){
                node=node.right;
                System.out.println(node);
            }
            node=node.right;
        }
    }

}

class Node {
    int no;
    String name;
    Node left;
    Node right;
    int leftType;
    int rightType;

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + "}";
    }
}

哈弗曼树

基本介绍

• 1)给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(HuffmanTree)，还有的书翻译为霍夫曼树。
• 2)赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近

赫夫曼树几个重要概念

• 1)路径和路径长度:在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1
• 2)结点的权及带权路径长度:若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积
• 3)树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weighted pathlength),权值越大的结点离根结点越近的二叉树才是最优二叉树。
• 4)WPL最小的就是赫夫曼树

构成赫夫曼树的步骤:

{13,7,8,3,29,6,1}

• 1)从小到大进行排序，将每一个数据，每个数据都是一个节点﹐每个节点可以看成是一颗最简单的二叉树
• 2)取出根节点权值最小的两颗二叉树
• 3)组成一颗新的二叉树，该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
• 4)再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复1-2-3-4的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

package dataStructure.Tree;

import java.util.ArrayList;
import java.util.Collections;

//哈夫曼树
public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr={13,7,8,3,29,6,1};
        HuffmanNode huffmanNode = creatHuffmanTree(arr);
        perOrder(huffmanNode);
    }

    public static void perOrder(HuffmanNode root){
        if (root!=null){
            root.perOrder();
        }else {
            System.out.println("数据为空");
        }
    }

    public static HuffmanNode creatHuffmanTree(int[] arr){
        ArrayList<HuffmanNode> list=new ArrayList<>();
        for (int value:arr){
            list.add(new HuffmanNode(value));
        }
        while (list.size()>1){
            Collections.sort(list);
            System.out.println(list);
            HuffmanNode leftNode = list.get(0);
            HuffmanNode rightNode = list.get(1);
            HuffmanNode parent=new HuffmanNode(leftNode.no+rightNode.no);
            parent.left=leftNode;
            parent.right=rightNode;
            list.remove(leftNode);
            list.remove(rightNode);
            list.add(parent);
        }
        return list.get(0);
    }

}
class HuffmanNode implements Comparable<HuffmanNode>{
    int no;
    HuffmanNode left;
    HuffmanNode right;

    public HuffmanNode(int no) {
        this.no = no;
    }

    public void perOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.perOrder();
        }
        if (this.right!=null){
            this.right.perOrder();
        }
    }
    @Override
    public String toString() {
        return "HuffmanNode{" +
                "no=" + no +
                '}';
    }

    @Override
    public int compareTo(HuffmanNode o) {
        return this.no-o.no;
    }
}