绪论

什么是程序？

程序=数据结构+算法

什么是数据结构？

组织和存储数据的集合。

什么是算法？

解决问题的方法。

顺序存储

面向对象的数组

import java.util.Arrays;

class MyArray {
    private int[] elements;
    public MyArray(){
        elements = new int[0];
    }
    public int size(){
        return elements.length;
    }
    public void show(){
        System.out.println(Arrays.toString(elements));
    }
    public void add(int element){
        int[] newArry = new int[elements.length+1];
        for (int i = 0;i<elements.length;i++)
        {
            newArry[i] = elements[i];
        }
        newArry[elements.length] = element;
        elements = newArry;
    }
//删除
    public void delet(int index){
        if (index<0||index>elements.length-1)
        {
            throw new RuntimeException("下标越界");
        }
        int [] newArry = new int[elements.length-1];
        for (int i =0;i<elements.length-1;i++)
        {
            if (index>i)
            {
                newArry[i] = elements[i];
            }else {
                newArry[i] = elements[i+1];
            }
        }
        elements = newArry;
    }
    public int get(int index){
        return elements[index];
    }
///插入
    public void insert(int index,int element){
        if (index<0||index>elements.length)
        {
            throw new RuntimeException("下标越界");
        }
        int[]newArry = new int[elements.length+1];
        for (int i =0;i<newArry.length;i++){
            if (index>i){
                newArry[i] = elements[i];
            }else if (index<i){
                newArry[i] = elements[i-1];
            }else {
                newArry[i] = element;
            }
        }
        elements = newArry;
    }
//    替换
    public void set(int index,int element){
        if (index<0||index>elements.length-1)
        {
            throw new RuntimeException("下标越界");
        }
        elements[index] = element;
    }
}
class Demo1
{
    public static void main(String[] args) {
        MyArray myArray = new MyArray();
        myArray.add(1);
        myArray.add(12);
        myArray.add(123);
        myArray.insert(0,1234);
        myArray.set(0,111);
        myArray.show();
    }
}

线性查找

class Demo1
{
    public static void main(String[] args) {
        int[]arr = {1,2,4,5,7,9};
        int index = -1;
        int target = 10;
        for (int i = 0;i<arr.length;i++){
            if(target == arr[i])
            {
                index = i;
                break;
            }
        }
        System.out.println(index);
    }
}

二分法查找

class Demo1
{
    public static void main(String[] args) {
        int[]arr = {1,2,3,4,5,6,7,8,9};
        int index=set(arr,0);
        System.out.println(index);
    }
    public static int set(int[]arr,int element){
        int max = arr.length-1;
        int min = 0;
        int mid = (max+min)/2;
        while (true){
            if (arr[mid]>element)
            {
                max = mid-1;
            }else if (arr[mid]<element)
            {
                min = mid+1;
            }else {
                return mid;
            }
            if(min>max)
            {
                return -1;
            }
            mid = (max+min)/2;
        }
    }
}

class Demo1{
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int max = arr.length - 1;
        int min = 0;
        int mid = (max + min) / 2;
        int index=-1 ;
        int argten = 0;
        while (true) {
            if (arr[mid] > argten) {

                max = mid - 1;
            } else if (arr[mid] < argten) {
                min = mid + 1;
            } else {
                index = mid;
                break;
            }
            if(min>max)
            {
                index = -1;
                break;
            }
            mid = (max + min) / 2;

        } System.out.println(index);
    }

}

整合

import java.util.Arrays;

class MyArray {
    public int[] elements;
    public MyArray(){
        elements = new int[0];
    }
    public int size(){
        return elements.length;
    }
    public void show(){
        System.out.println(Arrays.toString(elements));
    }
    public void add(int element){
        int[] newArry = new int[elements.length+1];
        for (int i = 0;i<elements.length;i++)
        {
            newArry[i] = elements[i];
        }
        newArry[elements.length] = element;
        elements = newArry;
    }
    //删除
    public void delet(int index){
        if (index<0||index>elements.length-1)
        {
            throw new RuntimeException("下标越界");
        }
        int [] newArry = new int[elements.length-1];
        for (int i =0;i<elements.length-1;i++)
        {
            if (index>i)
            {
                newArry[i] = elements[i];
            }else {
                newArry[i] = elements[i+1];
            }
        }
        elements = newArry;
    }
    public int get(int index){
        return elements[index];
    }
    ///插入
    public void insert(int index,int element){
        if (index<0||index>elements.length)
        {
            throw new RuntimeException("下标越界");
        }
        int[]newArry = new int[elements.length+1];
        for (int i =0;i<newArry.length;i++){
            if (index>i){
                newArry[i] = elements[i];
            }else if (index<i){
                newArry[i] = elements[i-1];
            }else {
                newArry[i] = element;
            }
        }
        elements = newArry;
    }
    //    替换
    public void set(int index,int element){
        if (index<0||index>elements.length-1)
        {
            throw new RuntimeException("下标越界");
        }
        elements[index] = element;
    }
    //线性查找
    public  int search(int a)
    {
        int index = -1;
        for (int i = 0;i<elements.length;i++)
        {
            if (elements[i]==a){
                index =i;
                break;
            }
        }
        return index;
    }
    //二分法查找
    public int set(int element) {
        int max = elements.length-1;
        int min = 0;
        int mid = (max + min) / 2;
        while (true) {
            if (elements[mid] > element) {
                max = mid - 1;
            } else if (elements[mid] < element) {
                min = mid + 1;
            } else {
                return mid;
            }
            if (min > max) {
                return -1;
            }
            mid = (max + min) / 2;
        }
    }
}

栈

import java.util.Arrays;

class MyStack {
    public int[] elements;
    public MyStack(){
        elements = new int[0];
    }
    //压入
    public void add(int element){
        int[] newArry = new int[elements.length+1];
        for (int i = 0;i<elements.length;i++)
        {
            newArry[i] = elements[i];
        }
        newArry[elements.length] = element;
        elements = newArry;
    }
    //取出
    public int pop(){
        if (elements.length==0){
            throw new RuntimeException("栈为空");
        }
        int element = elements[elements.length-1];
        int [] newArry = new int[elements.length-1];

        for (int i =0;i<elements.length-1;i++)
        {
            newArry[i] = elements[i];
        }
        elements = newArry;
        return element;
    }
    //查看栈顶元素
    public int peek()
    {
        if (elements.length==0){
            throw new RuntimeException("栈为空");
        }
        return elements[elements.length-1];
    }
    //判断栈是否为空
    public boolean isEmpy()
    {
        return elements.length==0;
    }
}
class Demo1
{
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        int element;
        myStack.add(1);
        myStack.add(2);
        myStack.add(3);
        myStack.add(4);
        myStack.add(5);
        element =myStack.pop();
        element = myStack.peek();
        System.out.println(element);
        System.out.println(myStack.isEmpy());
    }
}

队列

class Demo1
{
    public static void main(String[] args) {
        Demo2 demo2 = new Demo2();
        demo2.add(9);
        demo2.add(8);
        demo2.add(7);
        demo2.add(6);
        int element;
        element = demo2.pop();
        System.out.println(demo2.isEmpy());
        System.out.println(element);
    }
}
class Demo2 {
    public int[] elements;
    public Demo2(){
        elements = new int[0];
    }
    //入队
    public void add(int element){
        int[] newArry = new int[elements.length+1];
        for (int i = 0;i<elements.length;i++)
        {
            newArry[i] = elements[i];
        }
        newArry[elements.length] = element;
        elements = newArry;
    }
    //出队
    public int pop(){
        if (elements.length==0){
            throw new RuntimeException("队为空");
        }
        int element = elements[0];
        int [] newArry = new int[elements.length-1];
        for (int i =0;i<elements.length-1;i++)
        {
            newArry[i] = elements[i+1];
        }
        elements = newArry;
        return element;
    }
    //判断队列是否为空
    public boolean isEmpy()
    {
        return elements.length==0;
    }
}

链式存储

单链表

class Node
{
//    节点内容
    int data;
//下一个节点
    Node next;
    public Node(int data){
        this.data = data;
    }
//    为节点追加节点
    public void append(Node node){
        this.next = node;
    }
    //获取下一个节点
    public Node next(){
        return this.next;
    }
//    获取节点内容
    public int getdata()
    {
        return this.data;
    }

}
class Demo1
{
    public static void main(String[] args) {
//        创建节点
        Node node = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
       //追加
        node.append(node1);
        node1.append(node2);
//  取出下一个节点
        System.out.println(node.next().getdata());
        System.out.println(node1.next().getdata());
    }
}

改进：

class Node
{
//    节点内容
    int data;
//下一个节点
    Node next;
    public Node(int data){
        this.data = data;
    }
//    为节点添加节点
    public Node append(Node node){
        //当前节点
        Node currentNode = this;
        while (true){
//            取出下一个节点
            Node nextNode= currentNode.next;
//            判断是否有下一个节点,如果为null,则当前节点为最后一个节点
            if (nextNode==null) {
                break;
            }
            //  赋给当前节点
            currentNode = nextNode;
        }
        currentNode.next = node;
        return this;
    }
    //获取下一个节点
    public Node next(){
        return this.next;
    }
//    获取节点内容
    public int getdata()
    {
        return this.data;
    }
    //当前节点是否是最后一个节点
    public boolean isLast()
    {
        return next == null;
    }
       //删除下一节点
    public void delete(){
        Node newNode = next.next;
        this.next = newNode;
    }
    //插入节点
    public void insert(Node node){
        //取出下一个节点,为新节点的下一节点作准备
        Node afterNext = next;
        //把新节点作为当前节点的下一节点
        this.next = node;
        //新节点的下一节点
        node.next = afterNext;
    }
    //显示所有节点 信息
    public void show(){
        Node currentNode = this;
        while (true){
            System.out.println(currentNode.base);
            //取出下一节点
            currentNode = currentNode.next;
            //若为最后一个节点
            if(currentNode == null){
                break;
            }
        }
    }

}
class Demo1
{
    public static void main(String[] args) {
//        创建节点
        Node node = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        //添加节点
        node.append(node1).append(node2);
    //  取出下一个节点
        System.out.println(node.next().isLast());
    }
}

循环链表

package opp;import java.util.Vector;class Node{    //节点内容    int base;    //下一节点    Node next = this;    public Node(int base){        this.base = base;    }    //删除下一节点    public void delete(){        Node newNode = next.next;        this.next = newNode;    }    //插入节点    public void insert(Node node){        //取出下一个节点,为新节点的下一节点作准备        Node afterNext = next;        //把新节点作为当前节点的下一节点        this.next = node;        //新节点的下一节点        node.next = afterNext;    }    //获取下一个节点    public Node next(){        return this.next;    }    //    获取节点内容    public int getBase()    {        return this.base;    }}class Dmoe1{    public static void main(String[] args) {        Node n1 = new Node(1);        Node n2 = new Node(2);        Node n3 = new Node(3);        Node n4 = new Node(4);        n1.insert(n2);        n2.insert(n3);        n3.insert(n4);        System.out.println(n1.next().getBase());        System.out.println(n2.next().getBase());        System.out.println(n3.next().getBase());        System.out.println(n4.next().getBase());    }}

双链表

package opp;import java.util.Vector;class Node{    //节点内容    int base;    //下一节点    Node next = this;    //上一个节点    Node pre = this;    public Node(int base){        this.base = base;    }    //插入节点    public void insert(Node node){        //取出下一个节点,为新节点的下一节点作准备        Node afterNext = next;        //把新节点作为当前节点的下一节点        this.next = node;        //把当前节点作为新节点的上一个节点        node.pre = this;        //新节点的下一节点        node.next = afterNext;        //源节点的上一节点为新节点        afterNext.pre = node;    }    //获取下一个节点    public Node next(){        return this.next;    }    //获取上一个节点    public Node pre(){        return this.pre;    }    //    获取节点内容    public int getBase()    {        return this.base;    }}class Dmoe1{    public static void main(String[] args) {        Node n1 = new Node(1);        Node n2 = new Node(2);        Node n3 = new Node(3);        Node n4 = new Node(4);        n1.insert(n2);        n2.insert(n3);        System.out.println(n2.pre.base);        System.out.println(n2.base);        System.out.println(n2.next.base);            }}

斐波那契数列

1 1 2 3 5 8 13 21

package opp;class Dmoe1{    public static void main(String[] args) {        int i = feiBoNaC(3);        System.out.println(i);    }    public static int  feiBoNaC(int i ){        if (i==1|| i==2){            return 1;        }else {            return feiBoNaC(i-1)+feiBoNaC(i-2);        }    }}

汉罗塔问题

package opp;class Dmoe1{    public static void main(String[] args) {        hanLuo(3,"开始柱子","中间柱子","目标柱子");    }    /**     *     * @param n    共有n个盘中     * @param from 开始的柱子     * @param in   中间柱子     * @param to   目标柱子     * 无论有多少盘中.都认为只有两个.     * 即上面的所有盘子和最下面的盘子.     */    public static void hanLuo(int n,String from,String in , String to){        //只有一个盘子        if (n==1){            System.out.println("第1个盘子从 "+from+" 移动到 "+to);        }//多个盘子        else {            //移动上面所有盘子到中间位置            hanLuo(n-1,from,to,in);            //移动最下面的盘子            System.out.println("第"+n+"个盘子从 "+from+" 移动到 "+to);            //把上面的盘子从中间位置移到目标位置            hanLuo(n-1,in,from,to);        }    }}

排序算法

交换排序

冒泡排序

public static void bubbleSort(int[]arr){
        int i;
        int j;
        int temp;
        for (i=0;i< arr.length-1;i++)
        {
            for (j=0;j<arr.length-1-i;j++)
            //紧挨着的俩俩排序, **注意** j<arr.length-1-i;
                //arr.length-1防止 arr[j+1]不会越界
                //(arr.length-1)-i  表示上面以及排序完的不需要再排序,提高效率.
            {
                if (arr[j]>arr[j+1])
                {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
}

快速排序

package 算法;

import java.util.Arrays;

public class Qsort {
    public static void main(String[] args) {
        int[]arr ={3,1,4,5,7,8};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    //定义方法进行快速排序
    public static void quickSort(int[]arr,int left,int right){
//        进行判断：
//        1.如果空数组或者一个元素的数组之间输出
//        2.如果左侧的索引值比右侧的索引值大,不合法,return直接结束这个方法.
        
        //递归的基线条件必须写在最上面
        if (arr.length<2||left>right){
            return;
        }
//      定义变量保存基准数
        int base = arr[left];
//      定义变量i指向最左边
        int i = left;
//      定义变量j指向最右边
        int j = right;
//      当i和j不相遇时候,在循环中进行检索
        while (i!=j)
        {
            //由j从右往左检索比基准数小的,如果检索到比基准数小的就停下.
            while (arr[j] >= base && i<j){
                //检索的数字比基准数大或者相等.就继续检索
                j--;//j从右向左移动
            }


            //由i从左往右检索比基准数大的,如果检索到比基准数大的就停下.
            while (arr[i]<=base && i<j){
                //检索的数字比基准数小或者相等.就继续检索
                i++;//i从左向右移动
            }

            //此时i停下,j停下l.开始交换i和j位置的元素.
            int temp = arr[j];
            arr[j]= arr[i];
            arr[i] = temp;
        }
        //条件不成立,即i==j,i和j相遇了

        /*
         * i和j相遇了就要交换基准数和相遇位置的元素
         *  方法:
         *   1.把相遇位置的元素赋予给基准数位置的元素.
         *   2.将基准数的值赋予给相遇位置的元素.
         * */

        arr[left] = arr[i];//相遇位置元素给到基准数位置去

        arr[i] = base;//基准数的值赋予给相遇位置上
        //排左侧
        quickSort(arr,left,i-1);
        //排右侧
        quickSort(arr,j+1,right);
    }
}

选择排序

public static void selectionSort(int[]arr){    int i;    int j;    int temp;    for (i=0;i< arr.length-1;i++)    {        for (j=i+1;j< arr.length;j++){            if (arr[i]>arr[j]){                temp = arr[i];                arr[i]=arr[j];                arr[j] = temp;            }        }    }    System.out.println(Arrays.toString(arr));}

插入排序

直接插入排序

package opp;import java.util.Arrays;class Demo1{    public static void main(String[] args) {        int []arr = {10,5,3,1,6,9,2};        insertSort(arr);        System.out.println(Arrays.toString(arr));    }    public static void insertSort(int[]arr){        //遍历所有的数字        for (int i= 1;i< arr.length;i++)        {            //如果当前数字比前一个数字小            if (arr[i]<arr[i-1]){                int j;                //就把当前的数字储存起来                int temp = arr[i];                //遍历当前数字前面所有的数字                for (j=i-1;j>=0 && temp<arr[j];j--){                    //只要比当前数字大,位置都向后移动一位                    arr[j+1] = arr[j];                }                //arr[j]比当前数字小即 temp>arr[j],所以temp为arr[j+1]                arr[j+1] = temp;            }        }    }}

希尔排序

package opp;import java.util.Arrays;class Demo1{    public static void main(String[] args) {        int[]arr = {23,1,3,2,6,8,31,34};        shellSort(arr);        System.out.println(Arrays.toString(arr));    }    public static void shellSort(int[]arr){        //遍历所有的步长        for(int d = arr.length/2;d>0;d/=2){            //遍历所有的元素            for (int i=d;i< arr.length;i++){                //遍历本组中的所有元素                for (int j = i-d;j>=0;j-=d)                {                    //如果当前元素大于步长后的元素                    if (arr[j]>arr[j+d]){                        int temp  = arr[j];                        arr[j] = arr[j+d];                        arr[j+d] = temp;                    }                }            }        }    }}

选择排序

简单选择排序

堆排序

package 算法;import java.util.Arrays;public class HeapSort {    public static void main(String[] args) {        int[]arr = {9,6,8,7,0,1,10,4,2};//      开始位置是最后一个非子节点,即最后一个节点的父节点;        int start = (arr.length-1)/2;        //调整为大顶堆        for (int i= start;i>=0;i--){            maxHeap(arr,arr.length,i);        }//       先把数组中的第0个和堆中的最后一个数交换位置,再把前面处理为大顶堆        for (int i = arr.length-1;i>0;i--)        {            int temp = arr[0];            arr[0] = arr[i];            arr[i] = temp;            maxHeap(arr,i,0);        }        System.out.println(Arrays.toString(arr));    }    /**     *     * @param arr   转换的数组     * @param size   调整的次数     * @param index  调整的元素位置     */    public static void maxHeap(int[]arr,int size,int index){        //左子节点        int leftNode = 2*index+1;        //右子节点        int rightNode = 2*index+2;        int max = index;        //和两个节点分别对比,找出最大节点        if (leftNode<size && arr[leftNode]>arr[max]){            max = leftNode;        }        if (rightNode<size && arr[rightNode]>arr[max]){            max = rightNode;        }        //交换顺序        if (max!=index){            int temp = arr[index];            arr[index] = arr[max];            arr[max] = temp;            //交换后可能破坏之前排好的堆,所以,之前的拍好的堆需要重新调整.            maxHeap(arr, size,max);        }    }}

归并排序

基数排序

广度优先搜索(算法图解–未完成)

package opp;import java.util.*;class Demo1 {    public static void main(String[] args) {        Map<String, Object> map = new HashMap<String, Object>();        ArrayList<String> you = new ArrayList<String>();        ArrayList<String> bob = new ArrayList<String>();        ArrayList<String> alice = new ArrayList<String>();        ArrayList<String> claire = new ArrayList<String>();        you.add("alice");        you.add("bob");        you.add("claire");        bob.add("anuj");        bob.add("peggy");        alice.add("peggy");        claire.add("thom");        claire.add("jonny");        map.put("you", you);        map.put("bob", bob);        map.put("alice", alice);        map.put("claire", claire);        map.put("anuj", "");        map.put("peggy", "");        map.put("thom", "");        map.put("jonny", "");        Queue queue = new LinkedList();        queue.offer(you);        while (queue.isEmpty()) {            Object name = queue.peek();            if (isSeller(name)){                System.out.println("他是芒果经销商");            }else{                queue.offer(name);            }        }        //entrySet方法遍历        Set<Map.Entry<String, Object>> entrys = map.entrySet();        Iterator<Map.Entry<String, Object>> it = entrys.iterator();        while (it.hasNext()) {            Map.Entry<String, Object> entry = it.next();            System.out.println(entry.getKey() + entry.getValue());        }    }    public static boolean isSeller(Object name) {        if (name.equals("bob")) {            return true;        }else{            return false;        }    }    public static void search(Object name){            }}

狄克斯特拉算法

树结构

二叉树

定义:任何一个节点的子节点数量不超过2

**注意:**二叉树的子节点分左右两个节点

**满二叉树:**所有叶子节点都在最后一层,而且节点的总数为2^n-1

n为数的高度

完全二叉树: 所有叶子节点都在最后一层或者倒数第二层.而且最后一岑的叶子节点在左边联系,倒数第二层的叶子节点在右边连续.

链式存储的二叉树

创建二叉树 添加节点 树的遍历 查找节点 删除子树

package opp;
class BinaryTree{
    TreeNode root;
    //设置根节点
    public void setRoot(TreeNode root) {
        this.root = root;
    }
    //获取根节点
    public TreeNode getRoot() {
        return root;
    }
    public void frontShow() {
        root.frontShow();
    }

    public void midShow() {
        root.midShow();
    }

    public void houShow() {
        root.houShow();
    }

    public TreeNode frontSearch(int i) {
        return root.frontSearch(i);
    }

    public void delet(int i) {
        if (root.value == i){
            root =null;
        }else {
            root.delet(i);
        }
    }
}
class TreeNode{
   
    //节点的权
    int value;
    //左儿子
    TreeNode leftNode;
    //右儿子
    TreeNode rightNode;
    public TreeNode(int value){
        
        this.value = value;
    }
    //设置左儿子
    public void setlNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }
    //设置右儿子
    public void setrNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }
//前序遍历
    public void frontShow() {
        //先遍历当前节点的内容
        System.out.println(value);
        //左节点
        if (leftNode!=null){
            leftNode.frontShow();
        }
        //右节点
        if (rightNode!=null){
            rightNode.frontShow();
        }
    }

    public void midShow() {
        //左子节点
        if (leftNode!=null){
            leftNode.midShow();
        }
        //当前节点
        System.out.println(value);
        //右子节点
        if (rightNode!=null){
            rightNode.midShow();
        }
    }
    //后续遍历
    public void houShow() {
        //左子节点
        if (leftNode!=null){
            leftNode.houShow();
        }
        //右子节点
        if (rightNode!=null){
            rightNode.houShow();
        }
        //当前节点
        System.out.println(value);
    }

    public TreeNode frontSearch(int i) {
        TreeNode target = null;
        //对比当前节点的值
        if (this.value == i){
            return this;
            //当前节点值不是要查找的节点
        }else {
            //查找左儿子
            if (leftNode!=null){
//                有可能查到,也有可能查不到,查不到target还是一个null
                 target = leftNode.frontSearch(i);
            }
//            如果不为空,说明左儿子中已经找到了
            if (target!=null){
                return target;
            }
//            查找右儿子
            if (rightNode!=null){
                target = rightNode.frontSearch(i);
            }
        }
        return target;
    }
//   删除子树
    public void delet(int i) {
        TreeNode parent = this;
        //判断左儿子
        if (parent.leftNode!=null && parent.leftNode.value == i){
            parent.leftNode = null;
            return;
        }
//        判断右儿子
        if (parent.rightNode!=null && parent.rightNode.value == i){
            parent.rightNode = null;
            return;
        }
//        递归检查并删除左儿子
        parent = leftNode;
        if (parent!=null){
            parent.delet(i);
        }
//        递归检查并删除右儿子
        parent = rightNode;
        if (parent!=null){
            parent.delet(i);
        }

    }
}
class Demo1{
    public static void main(String[] args) {
        //创建一个树
        BinaryTree binaryTree = new BinaryTree();
        //创建一个节点
        TreeNode root = new TreeNode(1);
        //把根节点赋给树
        binaryTree.setRoot(root);
        //创建两个节点
        //左节点
        TreeNode rootL = new TreeNode(2);
        //把新创建的节点设置为根节点的子节点
        root.setlNode(rootL);
        //右节点
        TreeNode rootR = new TreeNode(3);
        //把新创建的节点设置为根节点的子节点
        root.setrNode(rootR);
        //为第二层的左节点创建两个子节点
        rootL.setlNode(new TreeNode(4));
        rootL.setrNode(new TreeNode(5));
        //为第二层的右节点创建两个子节点
        rootR.setlNode(new TreeNode(6));
        rootR.setrNode(new TreeNode(7));

        //前序遍历
       binaryTree.frontShow();
        //中序遍历
        //binaryTree.midShow();
        //后续遍历
       // binaryTree.houShow();
        //前序查找
//        TreeNode result = binaryTree.frontSearch(8);
//        System.out.println(result);
        //删除子树
        System.out.println("+++++++++++");
        binaryTree.delet(2);
        binaryTree.frontShow();
    }
}

顺序存储的二叉树（只考虑全完二叉树）

性质

**第n个元素的左子节点：**2*n+1

**第n个元素的左子节点：**2*n+2

第n个元素的父节点： (n-1)/2

遍历

package opp;class ArrayBinaryTree{    int[]arr;    public ArrayBinaryTree(int[]arr){        this.arr = arr;    }    public void frontShow(){        frontShow(0);    }    public void frontShow(int index){        if (arr==null||arr.length==0){            return;        }        //遍历当前节点内容        System.out.println(arr[index]);        //处理左子树        if (2*index+1<arr.length){            frontShow(2*index+1);        }        //处理右子树        if (2*index+2<arr.length){            frontShow(2*index+2);        }    }}public class Demo2 {    public static void main(String[] args) {        int[]arr = {1,2,3,4,5,6,7};        ArrayBinaryTree tree = new ArrayBinaryTree(arr);        tree.frontShow();    }}

线索二叉树

线索二叉树。一个节点的前一个节点，叫前驱节点。

线索二叉树，一个节点的后一个节点，叫后继节点。

package opp;
class BinaryTree{
    TreeNode root;
    //临时存储前驱节点
    TreeNode pre = null;
    //遍历线索二叉树
    public void threadIterate(){
        //用于临时存储当前遍历节点
        TreeNode node = root;
        while (node!= null){
            //循环找到最开始节点
            while (node.leftType==0){
                node = node.leftNode;
            }
        }
        //打印当前节点的值
        System.out.println(node.value);
//        如果当前节点的右指针指向的是后继节点,可能后继节点还有后继节点.
        while (node.rightType ==1){
            node = node.leftNode;
            System.out.println(node.value);
        }
        //替换遍历的节点
        node = node.rightNode;
    }
    //设置根节点
    public void setRoot(TreeNode root) {
        this.root = root;
    }
    //获取根节点
    public TreeNode getRoot() {
        return root;
    }
    public void frontShow() {
        root.frontShow();
    }

    public void midShow() {
        root.midShow();
    }

    public void houShow() {
        root.houShow();
    }
    public void threadNode(){
        threadNode(root);
    }
//    中序线索化二叉树
    public void threadNode(TreeNode node){
        //当前节点为null,直接返回
        if (node==null){
            return;
        }
        //处理左子树
        threadNode(node.leftNode);
        //处理前驱节点
         if (node.leftNode== null){
             //让当前节点的左指针指向前驱节点
             node.leftNode = pre;
//             改变当前节点左指针类型
             node.leftType = 1;
         }
//         处理前驱的右指针,如果前驱节点的右指针是null(没有指向右子树)
         if ( pre!=null&&pre.rightNode == null){
             //让前驱节点的右指针指向当前节点
             pre.rightNode = node;
             //改变前驱节点的右指针类型
             pre.rightType = 1;
         }
         //每处理一个节点,当前节点是下一个节点的前驱节点
        pre = node;
        //处理右子树
        threadNode(node.rightNode);
    }
//前序查找
    public TreeNode frontSearch(int i) {
        return root.frontSearch(i);
    }
//删除节点
    public void delet(int i) {
        if (root.value == i){
            root =null;
        }else {
            root.delet(i);
        }
    }
}
class TreeNode{
   
    //节点的权
    int value;
    //左儿子
    TreeNode leftNode;
    //右儿子
    TreeNode rightNode;
    //标识指针类型
    int leftType;
    int rightType;
    public TreeNode(int value){
        
        this.value = value;
    }
    //设置左儿子
    public void setlNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }
    //设置右儿子
    public void setrNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }
//前序遍历
    public void frontShow() {
        //先遍历当前节点的内容
        System.out.println(value);
        //左节点
        if (leftNode!=null){
            leftNode.frontShow();
        }
        //右节点
        if (rightNode!=null){
            rightNode.frontShow();
        }
    }

    public void midShow() {
        //左子节点
        if (leftNode!=null){
            leftNode.midShow();
        }
        //当前节点
        System.out.println(value);
        //右子节点
        if (rightNode!=null){
            rightNode.midShow();
        }
    }
    //后续遍历
    public void houShow() {
        //左子节点
        if (leftNode!=null){
            leftNode.houShow();
        }
        //右子节点
        if (rightNode!=null){
            rightNode.houShow();
        }
        //当前节点
        System.out.println(value);
    }

    public TreeNode frontSearch(int i) {
        TreeNode target = null;
        //对比当前节点的值
        if (this.value == i){
            return this;
            //当前节点值不是要查找的节点
        }else {
            //查找左儿子
            if (leftNode!=null){
//                有可能查到,也有可能查不到,查不到target还是一个null
                 target = leftNode.frontSearch(i);
            }
//            如果不为空,说明左儿子中已经找到了
            if (target!=null){
                return target;
            }
//            查找右儿子
            if (rightNode!=null){
                target = rightNode.frontSearch(i);
            }
        }
        return target;
    }
//   删除子树
    public void delet(int i) {
        TreeNode parent = this;
        //判断左儿子
        if (parent.leftNode!=null && parent.leftNode.value == i){
            parent.leftNode = null;
            return;
        }
//        判断右儿子
        if (parent.rightNode!=null && parent.rightNode.value == i){
            parent.rightNode = null;
            return;
        }
//        递归检查并删除左儿子
        parent = leftNode;
        if (parent!=null){
            parent.delet(i);
        }
//        递归检查并删除右儿子
        parent = rightNode;
        if (parent!=null){
            parent.delet(i);
        }

    }
}
class Demo1{
    public static void main(String[] args) {
        //创建一个树
        BinaryTree binaryTree = new BinaryTree();
        //创建一个节点
        TreeNode root = new TreeNode(1);
        //把根节点赋给树
        binaryTree.setRoot(root);
        //创建两个节点
        //左节点
        TreeNode rootL = new TreeNode(2);
        //把新创建的节点设置为根节点的子节点
        root.setlNode(rootL);
        //右节点
        TreeNode rootR = new TreeNode(3);
        //把新创建的节点设置为根节点的子节点
        root.setrNode(rootR);
        //为第二层的左节点创建两个子节点
        rootL.setlNode(new TreeNode(4));
        rootL.setrNode(new TreeNode(5));
        //为第二层的右节点创建两个子节点
        rootR.setlNode(new TreeNode(6));
        rootR.setrNode(new TreeNode(7));

        //前序遍历
       //binaryTree.frontShow();
//       中序遍历
       // binaryTree.midShow();
        //后续遍历
       // binaryTree.houShow();
        //前序查找
//        TreeNode result = binaryTree.frontSearch(8);
//        System.out.println(result);
        //删除子树
        System.out.println("+++++++++++");
        //binaryTree.delet(2);
        //binaryTree.frontShow();
        binaryTree.threadNode();
        binaryTree.threadIterate();

    }
}

赫夫曼树

权值越大的节点越近的二叉树才是最优二叉树。

package opp;

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

class Node implements Comparable<Node>{
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }
    @Override
    public int compareTo(Node o) {
        return  -(this.value-o.value);
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}
public class Demo3 {
    public static void main(String[] args) {
        int[]arr ={3,7,8,29,5,11,23,14};
        Node node = createHuffmanTree(arr);
        System.out.println(node);
    }
    //创建赫夫曼树
    public static Node createHuffmanTree(int[]arr){
//        先使用数组中所有的元素创建若干个二叉树(只有一个节点)
        List<Node> nodes = new ArrayList<>();
        for (int value:arr){
            nodes.add(new Node(value));
        }
        //循环处理
        while (nodes.size()>1){
//            排序
            Collections.sort(nodes);
//            取出权值最小的二叉树
            Node left = nodes.get(nodes.size()-1);
//            取出权值次小的二叉树
            Node right = nodes.get(nodes.size()-2);
//            创建一棵新的二叉树
             Node parent = new Node(left.value+ right.value);
//            把取出来的两个二叉树移除
            nodes.remove(left);
            nodes.remove(right);
//            放入原来的二叉树集合中
            nodes.add(parent);
        }
        return nodes.get(0);
    }
}

赫夫曼树编码

package opp;import java.util.*;class Human implements Comparable<Human>{    Byte data;    int weigh;    Human left;    Human right;    public Human(Byte data, int weigh) {        this.data = data;        this.weigh = weigh;    }    @Override    public String toString() {        return "Human{" +                "data=" + data +                ", weigh=" + weigh +                '}';    }    @Override    public int compareTo(Human o) {        return o.weigh-this.weigh;    }}public class Demo4 {    public static void main(String[] args) {        String msg = "can you can";        byte[]bytes= msg.getBytes();        //进行赫夫曼编码        byte[] b = huffmanZip(bytes);        System.out.println(bytes.length);        System.out.println(b.length);    }    /**     *   //进行赫夫曼编码压缩的方法     * @param bytes     * @return     */    private static byte[] huffmanZip(byte[] bytes) {//      先统计每一个byte出现的次数,并放入一个集合中        List<Human> nodes = getHuman(bytes);//      创建赫夫曼树        Human tree = createHuffmanTree(nodes);//      创建一个赫夫曼编码表        Map<Byte,String>huffCodes = getCodes(tree);//      编码        byte[]b =zip(bytes,huffCodes);        return b;    }    /**     * //把byte转node集合     * @param bytes     * @return     */    private static List<Human> getHuman(byte[] bytes) {        List<Human> nodes = new ArrayList<Human>();        //储存每一个byte出现了多少次        Map<Byte,Integer> counts = new HashMap<>();        //统计每一个byte出现的次数        for (byte b:bytes)        {            Integer count = counts.get(b);            if (count == null){                counts.put(b,1);            }else {                counts.put(b,count+1);            }        }        //把每一个键值对转换为node对象        for (Map.Entry<Byte,Integer>entry:counts.entrySet())        {            nodes.add(new Human(entry.getKey(),entry.getValue()));        }        return nodes;    }    /**     *  创建赫夫曼树      */    private static Human createHuffmanTree(List<Human> nodes) {        while (nodes.size()>1){//            排序            Collections.sort(nodes);//             取出两个权值最低的二叉树            Human left = nodes.get(nodes.size()-1);            Human right = nodes.get(nodes.size()-2);//             创建一个新的二叉树            Human parent = new Human(null,left.weigh+ right.weigh);//            把之前取出来的两棵二叉树设置为新创建的二叉树的子树            parent.left =left;            parent.right =right;//             把前面取出来的两棵二叉树删除            nodes.remove(left);            nodes.remove(right);//             把新创建的二叉树放入集合中            nodes.add(parent);        }        return nodes.get(0);    }    /**     *  //根据赫夫曼树获取赫夫曼编码     * @param tree     * @return     */    //用于临时存储路径    static  StringBuilder sb = new StringBuilder();    //用于存储赫夫曼编码    static Map<Byte,String> huffCodes = new HashMap<>();    private static Map<Byte, String> getCodes(Human tree) {        if (tree == null){            return null;        }        getCodes(tree.left,"0",sb);        getCodes(tree.right,"1",sb);        return huffCodes;    }    private static void getCodes(Human node,String code,StringBuilder sb) {        StringBuilder sb2 = new StringBuilder(sb);        sb2.append(code);        if (node.data == null) {            getCodes(node.left,"0",sb2);            getCodes(node.right,"1",sb2);        }else {            huffCodes.put(node.data,sb2.toString());        }    }    /**     * 进行赫夫曼编码     * @param bytes     * @param huffCodes     * @return     */    private static byte[] zip(byte[] bytes, Map<Byte, String> huffCodes) {        StringBuilder sb = new StringBuilder();//       把需要压缩的byte数组处理成二进制的字符串        for (byte b : bytes) {            sb.append(huffCodes.get(b));        }        //定义长度        int len;        if (sb.length()%8==0){            len = sb.length()%8;        }else {            len = sb.length()%8+1;        }        //用于存储压缩后的byte        byte[]by = new byte[len];//        记录新的byte的位置        int index = 0;        for (int i= 0; i<sb.length();i+=8){            String strByte;            if (i+8>sb.length()){                strByte = sb.substring(i);            }else {                strByte = sb.substring(i,i+8);            }            byte byt = (byte) Integer.parseInt(strByte,2);            by[index] = byt;           index++;        }        return by;    }}

二叉排序树

**定义:**对于二叉树中的任何一个非叶子节点,要求左子节点比当前节点值小,右子节点比当前值大.

添加, 查找, 删除.

出错

package 基础语法;class Node {    int value;    Node left;    Node right;    public Node(int value) {        this.value = value;    }    /**     * 向子树添加节点     * @param node     */    public void add(Node node) {        if (node==null){            return;        }        //判断传入的节点的值比当前子树的根节点的值大还是小        //添加的节点比当前节点的值更小        if (this.value> node.value){            //如果左节点为空            if (this.left!=null){                this.left.add(node);            }else {                this.left = node;            }        }else {            if (this.right!=null){                this.right.add(node);            }else {                this.right = node;            }        }    }    public void frontShow(Node node) {        if (node==null){            return;        }        frontShow(node.left);        System.out.println(node.value);        frontShow(node.right);    }    public Node search(int value) {        if (this.value==value){            return this;        }else if (this.value>value){            if (left==null){                return null;            }            return left.search(value);        }else {            if (right==null){                return null;            }            return right.search(value);        }    }}class Tree{    Node root;    /**     * 向二叉树中添加节点     * @param node     */    public void add(Node node){        //如果为空树        if (root==null){          root = node;        }else {            root.add(node);        }    }    /**     * 中序遍历,从小到大     */    public void frontShow(){        if (root!=null){            root.frontShow(root);        }    }    /**     * 节点的查找     */    public Node search(int value){        if (root==null){            return null;        }else {            return root.search(value);        }    }}class Demo1{    public static void main(String[] args) {        int[]arr = {1,7,3,21,6,34,9};        Tree tree = new Tree();        for (int i:arr){            tree.add(new Node(i));        }        //查看树中的值        tree.frontShow();        //查找        Node node = tree.search(0);        System.out.println(node.value);    }}

视频代码

节点类

package demo10;public class Node {    int value;    Node left;    Node right;    public Node(int value){        this.value=value;    }    /**     * 向子树中添加节点     * @param node     */    public void add(Node node) {        if(node==null){            return;        }else{            //判断传入的节点的值比当前子树的根节点的值大还是小            //添加的节点比当前节点的值更小            if(node.value<this.value){                //如果左节点为空                if(this.left==null){                    this.left=node;                }                //如果不为空                else{                    this.left.add(node);                }            //添加的节点比当前节点的值大            }else{                if(this.right==null){                    this.right=node;                }else{                    this.right.add(node);                }            }        }    }    /**     * 中序遍历二叉排序树，从小到大排序     * @param node     */    public void midShow(Node node) {        if(node==null){            return;        }        midShow(node.left);        System.out.print(node.value+" ");        midShow(node.right);    }    /**     * 查找节点     * @param value     * @return     */    public Node search(int value) {        if(this.value==value){            return this;        }else if(value<this.value){            if(left==null){                return null;            }            return left.search(value);        }else{            if(right==null){                return null;            }            return right.search(value);        }    }}

树类

package demo10;public class BinarySortTree {    Node root;    /**     * 向二叉排序树中添加节点     * @param node     */    public void add(Node node){        //如果是一棵空树        if(root==null){            root=node;        }else{            root.add(node);        }    }    /**     * 中序遍历二叉排序树，从小到大的顺序     */    public void midShow(){        if(root!=null){            root.midShow(root);        }    }    /**     * 节点的查找     * @param value     * @return     */    public Node search(int value){        if(root==null){            return null;        }else{            return root.search(value);        }    }}

测试

package demo10;public class TestBinarySortTree {    public static void main(String[] args) {        int[] arr = new int[]{7,3,10,12,5,1,9};        //创建一棵二叉排序树        BinarySortTree bst = new BinarySortTree();        //循环添加        for(int i:arr){            bst.add(new Node(i));        }        //查看树中的值        System.out.println("二叉排序树中序遍历：");        bst.midShow();        System.out.println();        System.out.println("=============");        Node node = bst.search(10);        System.out.println(node.value);        Node node2 = bst.search(20);        System.out.println(node2);    }}

平衡二叉树

**定义：**左子树和右子树的高度差的绝对值不超过1