数据结构与算法每日一练(Java)

数据结构与算法每日一练(Java)

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

Java数据结构与算法每日一练

• • 稀疏数组（2022-06-09）
  • 数组队列（2022-06-09）
  • 环形数组队列-泛型（2022-06-11）
  • 单链表（2022-06-10）
  • 双向链表（2022-06-10）
  • 双向链表-支持泛型（2022-06-11）
  • 栈（2022-06-10）
  • 栈-支持泛型（2022-06-11）
  • 利用栈实现数字大小不超过10 的 计算器(2022-06-10)
  • 利用栈实现计算器(数字大小不限)(2022-06-10)
  • 排序方法的比较
  • 二分法查找有序集合(2022-06-11)
  • 冒泡排序(2022-06-11)
  • 快速排序(2022-06-11)
  • 插入排序（2022-06-12）
  • 希尔排序（2022-06-12）
  • 选择排序(2022-06-12)
  • 归并排序(2022-06-12)
  • 基数排序(2022-06-12)
  • 二叉树-支持泛型（2022-06-13）
  • 二叉排序树（2022-06-13）
  • 平衡二叉树（202206-14）
  • 平衡二叉树-支持泛型（2022-06-14）

源码Github下载地址

---

稀疏数组（2022-06-09）

/**** 二维数组* 转为* 稀疏数组*/
public class SparseArray {private static final int ROW =11;private static final int COL =11;/*** @Author mabo* @Description   初始化*/public static int[][] initSparseArray(){int[][] array = new int[ROW][COL];array[2][3]=1;array[5][6]=3;array[3][4]=2;return array;}public static void show(int  array[][]){for (int[]ROW:array) {for (int data:ROW) {System.out.print(data+" ");}System.out.println();}}/*** @Author mabo* @Description   二维数组转为稀疏数组*/public static int[][] getSparseArray(int  array[][]){int sum=0;for (int i = 0; i < ROW; i++) {for (int j = 0; j < COL; j++) {if (array[i][j]!=0){sum++;}}}int[][] sparseArray = new int[sum+1][3];sum=1;for (int i = 0; i < ROW; i++) {for (int j = 0; j < COL; j++) {if (array[i][j]!=0){sparseArray[sum][0]=i;sparseArray[sum][1]=j;sparseArray[sum][2]=array[i][j];sum++;}}}sparseArray[0][0]=ROW;sparseArray[0][1]=COL;sparseArray[0][2]=sum-1;return  sparseArray;}/*** @Author mabo* @Description   稀疏数组转为二维数组*/public static int[][] toArray(int  sparseArray[][]){int row=sparseArray[0][0];int col=sparseArray[0][1];int sum=sparseArray[0][2];//数量int[][] array = new int[row][col];for (int i = 1; i <=sum; i++) {int x = sparseArray[i][0];int y = sparseArray[i][1];array[x][y]=sparseArray[i][2];}return  array;}public static void main(String[] args) {int[][] array = SparseArray.initSparseArray();SparseArray.show(array);int[][] sparseArray = SparseArray(array);SparseArray.show(sparseArray);int[][] ints = Array(sparseArray);SparseArray.show(ints);}
}

数组队列（2022-06-09）

package com.mabo.queue;
/*** @Author mabo* @Description   环形* 数组队列*/public class ArrayQueue {int size=5;int front=0;int rear=0;int queue[] = new int[size];boolean full(){boolean b = (rear + 1) % size == front;if (b){System.out.println("队列已满");}return  b ;}boolean empty(){boolean b = front == rear;if (b){System.out.println("队列为空");}return b;}boolean add(int num) throws Exception {if (!full()){queue[rear]=num;System.out.println(num+"加入队列成功");rear=(rear+1)%size;show();return true;}else {throw new Exception(num+"加入队列失败");}}int get() throws Exception {if (!empty()){int result=queue[front];front=(front+1)%size;System.out.println("获取数据成功"+result);show();return result;}else {throw new Exception("获取数据失败");}}void show(){for (int a : queue) {System.out.print(a+" ");}System.out.println();}public static void main(String[] args) {try {ArrayQueue arrayQueue=new ArrayQueue();arrayQueue.add(1);arrayQueue.add(2);();();arrayQueue.add(1);arrayQueue.add(2);} catch (Exception e) {e.printStackTrace();}}}

环形数组队列-泛型（2022-06-11）

package com.mabo.queue;public interface Queue<T> {boolean full();boolean empty();boolean add(T num)throws Exception ;T remove() throws Exception;void show();int getSize();}

package com.mabo.queue;import java.util.Date;/*** @Author mabo* @Description   环形* 数组队列*/public class ArrayQueue<T> implements Queue<T>{int size=10;int front=0;int rear=0;T queue[] =(T[]) new Object[size];@Overridepublic boolean full(){boolean b = (rear + 1) % size == front;if (b){System.out.println("队列已满");}return  b ;}@Overridepublic boolean empty(){boolean b = front == rear;if (b){System.out.println("队列为空");}return b;}@Overridepublic boolean add(T num) throws Exception {if (!full()){queue[rear]=num;System.out.println(num+"加入队列成功");rear=(rear+1)%size;show();return true;}else {throw new Exception(num+"加入队列失败");}}@Overridepublic T remove() throws Exception {if (!empty()){T result=queue[front];front=(front+1)%size;System.out.println("获取数据成功"+result);show();return result;}else {throw new Exception("获取数据失败");}}@Overridepublic void show(){for (T a : queue) {System.out.print(a+" ");}System.out.println();}@Overridepublic int getSize(){int i = (rear + size - front) % size;System.out.println("队列大小为"+i);return i;}public static void main(String[] args) {try {Date date = new Date();ArrayQueue<Object> arrayQueue=new ArrayQueue();arrayQueue.add(1);arrayQueue.add("1231");arrayQueue.add('c');arrayQueue.add(false);arrayQueue.add(date);int i = (int) ve();String s = (String) ve();char c = (char) ve();boolean bool = (boolean) ve();Date date1 = (Date) ve();System.out.println(i);System.out.println(s);System.out.println(c);System.out.println(bool);System.out.println(date1);} catch (Exception e) {e.printStackTrace();}}}

单链表（2022-06-10）

package com.mabo.linkedlist;public class Node{String nodeName;Node next;int value;public Node(String nodeName, int value, Node next) {deName =  = next;this.value = value;}public Node(String nodeName, Node next) {deName =  = next;}
}

package com.mabo.linkedlist;
/*** @Author mabo* @Description   单链表*/public class SingleList {private   Node head=new Node("head",0,null);public void add(String  nodeName,int value){if (!exist(nodeName)){Node node = new Node(nodeName,value, null);if (==null){= node;}else {Node next&#;=ext=next;}show();}else {update(nodeName,value);}}public void remove(String  nodeName){Node node = new Node(nodeName, null);Node position = head;Node before =head;while (!=null){position&#;if ( deName.deName)){= ;break;}before=position;}show();}public void show(){Node position = head;do {System.out.print("["&#deName+" "+position.value+"]  ");position&#;}while (position!=null);System.out.println();}public void update(String  nodeName,int valve){Node position = head;Node before =head;while (!=null){position&#;if ( deName.equals(nodeName)){position.value=valve;break;}before=position;}show();}public boolean exist(String  nodeName){Node position = head;Node before =head;while (!=null){position&#;if ( deName.equals(nodeName)){return true;}before=position;}return false;}public static void main(String[] args) {SingleList singleList = new SingleList();singleList.add("1",1);singleList.add("2",2);singleList.add("3",3);singleList.add("4",4);singleList.add("1",5);singleList.add("6",6);ve("3");}
}

双向链表（2022-06-10）

package com.mabo.linkedlist;public class DoubleNode{String nodeName;int value;DoubleNode pre;DoubleNode next;public DoubleNode(String nodeName, int value) {deName = nodeName;this.value = value;}
}

package com.mabo.linkedlist;
/*** @Author mabo* @Description  头插法 双向链表*/public class DoubleLinkedList {private   DoubleNode head=new DoubleNode("head",0);public void add(String  nodeName,int value){if (!exist(nodeName)){DoubleNode node = new DoubleNode(nodeName,value);if (==null){= node;}else {DoubleNode next&#;=node;node.pre==next;}show();}else {update(nodeName,value);}}public void remove(String  nodeName){DoubleNode position = head;while (!=null){position&#;if ( deName.equals(nodeName)){&#;break;}}show();}public void show(){DoubleNode position = head;do {System.out.print("["&#deName+" "+position.value+"]  ");position&#;}while (position!=null);System.out.println();}public void update(String  nodeName,int valve){DoubleNode position = head;while (!=null){position&#;if ( deName.equals(nodeName)){position.value=valve;break;}}show();}public boolean exist(String  nodeName){DoubleNode position = head;while (!=null){position&#;if ( deName.equals(nodeName)){return true;}}return false;}public int getLength(Node head){int length=0;Node position = head;while (!=null){position&#;length++;;}System.out.println("链表长度为"+length);return length;}public static void main(String[] args) {SingleList singleList = new SingleList();singleList.add("1",1);singleList.add("2",2);singleList.add("3",3);singleList.add("4",4);singleList.add("1",5);singleList.add("6",6);ve("3");Length();}
}

双向链表-支持泛型（2022-06-11）

package com.ics;public class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item =  = next;this.prev = prev;}
}

package com.ics;public interface List<T> {public void add(T t);public void remove(T t);public void show();}

package com.ics;public class LinkedList<T> implements List<T>{private Node head=new Node(null,"head",null);@Overridepublic void add(T t){Node node = new Node(head,t,null);if (!=null){Node next&#;=next;}=node;}@Overridepublic void remove(T t){Node position = head;while (!=null){position&#;if ( position.item.equals(t)){&#;break;}}}public void show(){Node position = head;do {System.out.print(position.item);position&#;}while (position!=null);System.out.println();}public static void main(String[] args) {List list = new LinkedList();list.add(123);list.add(123);System.out.println(list);ve(123);list.show();}
}

栈（2022-06-10）

package com.mabo.stack;
/*** @Author mabo* @Description   数组栈*/public class ArrayStack {private static final int SIZE=4;private int stack[]=new int[10];private int top=-1;public void push(int num) throws Exception {if (!full()){top++;stack[top]=num;}else {throw new Exception("栈已经满了");}show();}public int pop() throws Exception {if (!empty()){int a=stack[top];top--;show();return a;}else {throw new Exception("栈为空");}}public void show(){for (int i = 0; i <=top; i++) {System.out.print(stack[i]);}System.out.println();}public boolean full(){boolean b = (top == SIZE - 1);return b;}public boolean empty(){return top==-1;}public static void main(String[] args) {try {ArrayStack arrayStack = new ArrayStack();arrayStack.push(1);arrayStack.push(2);arrayStack.push(3);arrayStack.push(4);arrayStack.push(5);arrayStack.pop();arrayStack.pop();arrayStack.pop();} catch (Exception e) {e.printStackTrace();}}
}

栈-支持泛型（2022-06-11）

package com.ics;public interface Stack<T> {int top=-1;public int getSize();public void push(T t) throws Exception;public T pop() throws Exception ;public void show();public boolean full();public boolean empty();}

package com.ics;import java.util.Date;/*** @Author mabo* @Description   数组栈*/
public class ArrayStack<T> implements Stack<T> {private static final int SIZE=10;private T stack[]=(T[])new Object[SIZE];private int top=-1;public int getSize(){return top+1;}public void push(T num) throws Exception {if (!full()){top++;stack[top]=num;}else {throw new Exception("栈已经满了");}show();}public T pop() throws Exception {if (!empty()){T a=stack[top];top--;show();return a;}else {throw new Exception("栈为空");}}public void show(){for (int i = 0; i <=top; i++) {System.out.print(stack[i]+" ");}System.out.println();}public boolean full(){boolean b = (top == SIZE - 1);return b;}public boolean empty(){return top==-1;}public static void main(String[] args) {try {ArrayStack arrayStack = new ArrayStack();arrayStack.push(1);arrayStack.push("1231");arrayStack.push('C');arrayStack.push(false);arrayStack.push(new Date());arrayStack.pop();arrayStack.pop();arrayStack.pop();arrayStack.pop();arrayStack.pop();arrayStack.pop();} catch (Exception e) {e.printStackTrace();}}
}

利用栈实现数字大小不超过10 的 计算器(2022-06-10)

package com.mabo.stack;
/*** @Author mabo* @Description   利用栈实现* 计算器* 数字大小不超过10 的 简单加减乘除的功能*/public class Calculator {private ArrayStack numberStack=new ArrayStack();private ArrayStack operatorStack=new ArrayStack();private String string="2+4*4-2/2";public void putString() throws Exception {char[] chars = CharArray();for (char c : chars) {operatorAndPop(c);}}/*** @Author mabo* @Description   获取当前字符的运算符* 0为数组* 1为+ -* 2为* /*/public void operatorAndPop(char c) throws Exception {if (c=='+'||c=='-'){  //+43    -45    /47    *42if (pty()){operatorStack.push(c);}else {int pop = operatorStack.pop();int num2 = numberStack.pop();int num1 = numberStack.pop();int result ;if (pop=='*'){result=num1*num2;}else {result=num1/num2;}numberStack.push(result);operatorStack.push(c);}}else if (c=='*'||c=='/'){operatorStack.push(c);}else {numberStack.push(c- '0');}}public int getResult() throws Exception {while (Size()>1){int num2 = numberStack.pop();int num1 = numberStack.pop();int operator = operatorStack.pop();int result;if (operator=='+'){result=num1+num2;}else if (operator=='-'){result=num1-num2;}else if (operator=='*'){result=num1*num2;}else{result=num1/num2;}numberStack.push(result);}return numberStack.pop();}public static void main(String[] args) throws Exception {Calculator calculator = new Calculator();calculator.putString();calculator.numberStack.show();calculator.operatorStack.show();int result = Result();System.out.println("最终运算结果为"+result);}
}

利用栈实现计算器(数字大小不限)(2022-06-10)

package com.mabo.stack;import java.util.ArrayList;
import java.util.List;/*** @Author mabo* @Description   利用栈实现* 计算器* 简单加减乘除的功能*/public class Calculator {private ArrayStack numberStack=new ArrayStack();private ArrayStack operatorStack=new ArrayStack();private String string="12+43*1-22/22";public List getStringList(String  string) {char[] chars = CharArray();List<String> list= new ArrayList<>();String s=null;for (int i = 0; i < chars.length; i++){char c=chars[i];if (c!='+'&&c!='-'&&c!='*'&&c!='/'){int a=c-'0';if (s==null){s=String.valueOf(a);}else {s=s+a;}if (s!=null&&(i==chars.length-1)){list.add(s);}}else {if (s!=null){list.add(s);s=null;}list.add(String.valueOf(c));}}return list;}public void putString() throws Exception {List<String> stringList = getStringList(string);for (String  s : stringList) {operatorAndPop(s);}}/*** @Author mabo* @Description   获取当前字符的运算符* 0为数组* 1为+ -* 2为* /*/public void operatorAndPop(String string) throws Exception {char c;if (string.equals("+")){c='+';}else if (string.equals("-")){c='-';}else if (string.equals("*")){c='*';}else if (string.equals("/")){c='/';}else {c='0';}if (string.equals("+")||string.equals("-")){  //+43    -45    /47    *42if (pty()){operatorStack.push(c);}else {int pop = operatorStack.pop();int num2 = numberStack.pop();int num1 = numberStack.pop();int result ;if (pop=='*'){result=num1*num2;}else {result=num1/num2;}numberStack.push(result);operatorStack.push(c);}}else if (string.equals("*")||string.equals("/")){operatorStack.push(c);}else {numberStack.push(Integer.valueOf(string));}}public int getResult() throws Exception {while (Size()>1){int num2 = numberStack.pop();int num1 = numberStack.pop();int operator = operatorStack.pop();int result;if (operator=='+'){result=num1+num2;}else if (operator=='-'){result=num1-num2;}else if (operator=='*'){result=num1*num2;}else{result=num1/num2;}numberStack.push(result);}return numberStack.pop();}public static void main(String[] args) throws Exception {Calculator calculator = new Calculator();calculator.putString();calculator.numberStack.show();calculator.operatorStack.show();int result = Result();System.out.println("最终运算结果为"+result);}
}

排序方法的比较

二分法查找有序集合(2022-06-11)

package com.mabo.search;
/*** @Author mabo* @Description   二分法查找有序集合算法*/public class BinarySearch {int nums[]=new int[]{1,2,3,4,6,9,17,24,53};public int getNumPosition(int value){int low=0;int high=nums.length-1;while(low<=high) {int mid=(low+high)/2;if(value==nums[mid]) {return mid;}if(value>nums[mid]) {low=mid+1;}if(value<nums[mid]) {high=mid-1;}}return -1;//没有找到返回-1}public static void main(String[] args) {BinarySearch binarySearch = new BinarySearch();int numPosition = NumPosition(6);System.out.println(numPosition);}
}

冒泡排序(2022-06-11)

package com.mabo.sort;
/*** @Author mabo* @Description   冒泡排序*/public class BubbleSort {public  int[] sort(int nums[]){for (int i = 0; i < nums.length-1; i++) {for (int j = i+1; j <nums.length ; j++) {int temp=nums[i];if (temp>nums[j]){temp=nums[j];nums[j]=nums[i];nums[i]=temp;}}}return nums;}public void show(int nums[]){for (int a :nums) {System.out.print(a+" ");}}public static void main(String[] args) {int nums[]=new int[]{123,2231,334,43,346,93,137,234,453};BubbleSort bubbleSort = new BubbleSort();int[] sort = bubbleSort.sort(nums);bubbleSort.show(sort);}
}

快速排序(2022-06-11)

package com.mabo.sort;/*** @Author mabo* @Description   快速排序*/public class QuickSort {public  int[] sort(int nums[],int start,int end) {int left=start;int right=end;int flag = nums[left];while (left < right) {while (left < right&&nums[left]<flag){left++;}while (left < right&&nums[right]>flag){right--;}int temp=nums[right];nums[right]=nums[left];nums[left]=temp;}nums[left]=flag;//左边的if (left-start>1){nums = sort(nums, start, left);}//右边的if (end-left>1){nums =sort(nums,left+1,end);}return nums;}public void show(int nums[]){for (int a :nums) {System.out.print(a+" ");}}public static void main(String[] args) {int nums[]=new int[]{123,2231,334,43,3426,93,137,234,453};QuickSort quickSort = new QuickSort();int[] sort = quickSort.sort(nums, 0, nums.length-1);quickSort.show(sort);}
}

插入排序（2022-06-12）

package com.mabo.sort;/*** @Author mabo* @Description   插入排序*/public class InsertionSort {public  int[] sort(int nums[],int start) {while (start<nums.length){if (nums[start]>=nums[start-1]){start++;}else {nums = put(nums, start, nums[start]);}}return nums;}public int[] put(int nums[],int start,int n){while (start>0&& nums[start]<nums[start-1]){nums[start]=nums[start-1];start--;nums= put(nums, start, n);}nums[start]=n;return nums;}public void show(int nums[]){for (int a : nums) {System.out.print(a+" ");}}public static void main(String[] args) {int nums[]=new int[]{123,2231,334,43,3426,93,137,234,453};InsertionSort quickSort = new InsertionSort();int[] sort = quickSort.sort(nums, 1);quickSort.show(sort);}
}

希尔排序（2022-06-12）

package com.mabo.sort;
/*** @Author mabo* @Description   希尔排序*/
public class ShellSort {public static void main(String[] args){int[] ins = {2,3,5324,1,23243,6,7238,34,233,43,235,78,34,65,32,65,76,32,76,1,9};int[] ins2 = sort(ins);for(int in: ins2){System.out.print(in+" ");}}public static int[] sort(int[] ins){int n = ins.length;int gap = n/2;while(gap > 0){for(int j = gap; j < n; j++){int i=j;while(i >= gap && ins[i-gap] > ins[i]){int temp = ins[i-gap]+ins[i];ins[i-gap] = temp-ins[i-gap];ins[i] = temp-ins[i-gap];i -= gap;}}gap = gap/2;}return ins;}
}

选择排序(2022-06-12)

package com.mabo.sort;
/*** @Author mabo* @Description   选择排序*/public class SelectionSort {public  int[] sort(int nums[]) {for (int i = 0; i < nums.length-1; i++) {int min=nums[i];int x=i;for (int j = i+1; j < nums.length; j++) {if (nums[j]<min){x=j;min=nums[j];}}if (x!=i){int temp=nums[i];nums[i]=nums[x];nums[x]=temp;}}return nums;}public void show(int nums[]){for (int a : nums) {System.out.print(a+" ");}}public static void main(String[] args) {int nums[]=new int[]{123,2231,334,43,3426,93,137,234,453};SelectionSort selectionSort = new SelectionSort();int[] sort = selectionSort.sort(nums);selectionSort.show(sort);}
}

归并排序(2022-06-12)

package com.mabo.sort;/***  归并排序*/
public class MergeSort {public  void sort(int nums[]){int[] ints = new int[nums.length];sortNums(nums, ints,0, nums.length - 1);}public  void sortNums(int nums[], int ints[], int low, int high){int middle=(high+low)/2;if (low<high){sortNums(nums,ints, low, middle);sortNums(nums, ints,middle+1, high);merge(nums,ints, low, middle, high);}}public  void merge(int nums[],int[] ints ,int low,int middle,int high) {int x=low;int y=middle+1;int index=0;while (x<=middle&&y<=high){if (nums[x]<nums[y]){ints[index]=nums[x];x++;}else {ints[index]=nums[y];y++;}index++;}while (y<high){ints[index]=nums[y];y++;index++;}while (x<=middle){ints[index]=nums[x];x++;index++;}//临时数组存入原数据for (int i = 0; i < index; i++) {nums[low+i]=ints[i];}}public void show(int nums[]){for (int a : nums) {System.out.print(a+" ");}}public static void main(String[] args) {
//        int nums[]=new int[]{43,3};int nums[]=new int[]{43,123,211,212,3126,36,13,1,4,53,3};MergeSort mergeSort = new MergeSort();mergeSort.sort(nums);mergeSort.show(nums);}
}

基数排序(2022-06-12)

package com.mabo.sort;import com.mabo.queue.ArrayQueue;/*** @Author mabo* @Description   基数排序*/public class RadixSort {public void show(int nums[]){for (int a :nums) {System.out.print(a+" ");}}public void sort(int nums[]) throws Exception {ArrayQueue<Integer>[] stacks = new ArrayQueue[10];for (int i = 0; i < stacks.length; i++) {stacks[i]=new ArrayQueue<>();}int max=nums[0];for (int i = 1; i < nums.length; i++) {if (max<nums[i]){max=nums[i];}}int time=1;while (max>10){max=max/10;time++;}int count=10;for (int i = 0; i < time; i++) {for (int j = 0; j < nums.length; j++) {int x = (nums[j]%count)/(count/10);stacks[x].add(nums[j]);}int size=0;for (int j = 0; j < stacks.length; j++) {while (!stacks[j].empty()){int pop =(int) stacks[j].remove();nums[size]=pop;size++;}}count=count*10;}}public static void main(String[] args) throws Exception {int nums[]=new int[]{23421,23342,343,43,234326,93,137,234,3};RadixSort radixSort=new RadixSort();radixSort.sort(nums);radixSort.show(nums);}
}

二叉树-支持泛型（2022-06-13）

集中隔离结束了，居家隔离，享用美食耽误了半天

package ;/*** 二叉树*/
public class BinaryTree<T> implements Tree<T>{private final TreeNode root=new TreeNode();public boolean nodeFull(TreeNode treeNode){if (treeNode.left!=null&&treeNode.right!=null){return true ;}else {return false;}}public void putByNode(TreeNode treeNode, T t) {if (treeNode.value==null){treeNode.value=t;return;}if ( Left()==null) {treeNode.left=new TreeNode(t);return;}if ( Left()!=null&&treeNode.right==null){treeNode.right=new TreeNode(t);return;}if (nodeFull(treeNode)){if (nodeFull(treeNode.left)&&!nodeFull(treeNode.right)){putByNode(treeNode.right,t);}else{putByNode(treeNode.left,t);}}}@Overridepublic void put( T t) {putByNode(root,t);}public void removeObj(TreeNode treeNode, T t) {if(treeNode!=null){if (treeNode.value.equals(t)){treeNode.value=null;return;}if ( treeNode.right!=null){removeObj(treeNode.right,t);return;}else {removeObj(treeNode.left,t);return;}}}@Overridepublic void remove( T t){removeObj(root,t);}/*** @Author mabo* @Description   前序遍历*/public void frontShow(TreeNode treeNode) {System.out.print(treeNode.value+"  ");if ( Left()!=null){frontShow(treeNode.left);}if ( treeNode.right!=null){frontShow(treeNode.right);}}/*** @Author mabo* @Description   中序遍历*/public void middleShow(TreeNode treeNode) {if ( Left()!=null){middleShow(treeNode.left);}System.out.print(treeNode.value+"  ");if ( treeNode.right!=null){middleShow(treeNode.right);}}/*** @Author mabo* @Description   后序遍历*/public void afterShow(TreeNode treeNode) {if ( Left()!=null){afterShow(treeNode.left);}if ( treeNode.right!=null){afterShow(treeNode.right);}System.out.print(treeNode.value+"  ");}public static void main(String[] args) {BinaryTree<Object> tree = new BinaryTree<>();tree.put( 1);tree.put(2);tree.put(3);tree.put("123");tree.put(new Object());tree.put(5);tree.put(6);tree.put(7);tree.);ve(3);ve(1);System.out.println();tree.);tree.put(7);System.out.println();tree.);tree.put('C');System.out.println();tree.);tree.put(132);System.out.println();tree.);}}

二叉排序树（2022-06-13）

package ;/*** @Author mabo* @Description   二叉排序树* 因为要比较大小，仅支持int 类型*/public class BinarySortedTree{class TreeNode {TreeNode left;TreeNode right;int value;public TreeNode() {}public TreeNode(int value) {this.value = value;}public TreeNode(TreeNode left, TreeNode right, int value) {this.left = left;this.right = right;this.value = value;}public TreeNode getLeft() {return left;}public void setLeft(TreeNode left) {this.left = left;}public TreeNode getRight() {return right;}public void setRight(TreeNode right) {this.right = right;}public int getValue() {return value;}public void setValue(int value) {this.value = value;}}private final TreeNode root=new TreeNode();public int compare(int root,int node) {return node-root;}public void putByNode(TreeNode treeNode, int t) {if (root.value==0){root.value=t;return;}int compare = compare(treeNode.value,t);if (compare< 0) {if (treeNode.left==null||treeNode.left.value==0){treeNode.left=new TreeNode(t);return;}else {putByNode(treeNode.left,t);}return;}else if(compare> 0){if (treeNode.right==null||treeNode.right.value==0){treeNode.right=new TreeNode(t);return;}else {putByNode(treeNode.right,t);}return;}}public void put( int t) {putByNode(root,t);}public void removeObj(TreeNode treeNode, int t) {if(treeNode!=null){if (treeNode.value==t){treeNode.value=0;return;}if ( treeNode.right!=null){removeObj(treeNode.right,t);return;}else {removeObj(treeNode.left,t);return;}}}public void remove( int t){removeObj(root,t);}/*** @Author mabo* @Description   前序遍历*/public void frontShow(TreeNode treeNode) {System.out.print(treeNode.value+"  ");if ( Left()!=null){frontShow(treeNode.left);}if ( treeNode.right!=null){frontShow(treeNode.right);}}public static void main(String[] args) {BinarySortedTree tree=new BinarySortedTree();tree.put(4);tree.put(3);tree.put(2);tree.put(5);tree.);System.out.println();ve(5);tree.put(7);tree.);}}

平衡二叉树（202206-14）

package ;/*** @Author mabo* @Description   平衡二叉树* 因为要比较大小，仅支持int 类型*/public class BalancedBinaryTree{class TreeNode {TreeNode left;TreeNode right;int value;public TreeNode() {}public TreeNode(int value) {this.value = value;}public TreeNode getLeft() {return left;}public void setLeft(TreeNode left) {this.left = left;}public TreeNode getRight() {return right;}public void setRight(TreeNode right) {this.right = right;}public int getValue() {return value;}public void setValue(int value) {this.value = value;}public int height(){return Math.max(left==null?0:left.height(), right==null?0:right.height())+1;}public int leftHeight(){if (left!=null){return left.height();}return 0;}public int rightHeight(){if (right!=null){return right.height();}return 0;}}private TreeNode root=new TreeNode();public int compare(int root,int node) {return node-root;}public void putByNode(TreeNode treeNode, int t) {if (root.value==0){root.value=t;}else {int compare = compare(treeNode.value,t);if (compare< 0) {if (treeNode.left==null||treeNode.left.value==0){treeNode.left=new TreeNode(t);}else {putByNode(treeNode.left,t);}}else if(compare> 0){if (treeNode.right==null||treeNode.right.value==0){treeNode.right=new TreeNode(t);}else {putByNode(treeNode.right,t);}}}//左情况 右旋转if (treeNode.leftHeight()-treeNode.rightHeight()>=2){if (treeNode.left.leftHeight()<treeNode.left.rightHeight()){//左子树的右边大于左边，先左旋再右旋转TreeNode node=treeNode.left;rotateLeft(node);}rotateRight(treeNode);}//右情况 左旋转if (treeNode.leftHeight()-treeNode.rightHeight()<=-2){if (treeNode.right.leftHeight()>treeNode.right.rightHeight()){//左子树的左边大于右边，先右旋再左旋转TreeNode node=treeNode.right;rotateRight(node);}frontShow(root);System.out.println();rotateLeft(treeNode);}}/*** @Author mabo* @Description 右旋转*/public void rotateRight(TreeNode  treeNode){TreeNode newNode = new TreeNode(treeNode.value);newNode.right=treeNode.right;newNode.left=treeNode.left.right;treeNode.value=treeNode.left.value;treeNode.left=treeNode.left.left;treeNode.right=newNode;}/*** @Author mabo* @Description 左旋转*/private void rotateLeft(TreeNode treeNode) {TreeNode newNode = new TreeNode(treeNode.value);newNode.left=treeNode.left;newNode.right=treeNode.right.left;treeNode.value=treeNode.right.value;treeNode.right=treeNode.right.right;treeNode.left=newNode;}public void put( int t) {putByNode(root,t);}public void removeObj(TreeNode treeNode, int t) {if(treeNode!=null){if (treeNode.value==t){treeNode.value=0;return;}if ( treeNode.right!=null){removeObj(treeNode.right,t);return;}else {removeObj(treeNode.left,t);return;}}}public void remove( int t){removeObj(root,t);}/*** @Author mabo* @Description   前序遍历*/public void frontShow(TreeNode treeNode) {System.out.print(treeNode.value+"  ");if ( Left()!=null){frontShow(treeNode.left);}if ( treeNode.right!=null){frontShow(treeNode.right);}}/*** @Author mabo* @Description   求二叉树深度的函数TreeDepth*/int deep(TreeNode pRoot){if(pRoot==null){return 0;}int leftLen = deep(pRoot.left);int rightLen= deep(pRoot.right);return leftLen>rightLen ? (leftLen+1) : (rightLen+1);}public static void main(String[] args) {BalancedBinaryTree tree=new BalancedBinaryTree();//测试左左
//        tree.put(8);
//        tree.put(9);
//        tree.put(6);
//        tree.put(7);
//        tree.put(5);
//        tree.);
//        System.out.println();
//        tree.put(4);
//测试右右
//        tree.put(5);
//        tree.put(2);
//        tree.put(7);
//        tree.put(6);
//        tree.put(8);
//        tree.);
//        System.out.println();
//        tree.put(9);//        //测试左旋再右旋
//        tree.put(10);
//        tree.put(6);
//        tree.put(11);
//        tree.put(5);
//        tree.put(7);
//        tree.);
//        System.out.println();
//        tree.put(8);//测试右旋再左旋tree.put(7);tree.put(6);tree.put(10);tree.put(11);tree.put(9);tree.);System.out.println();tree.put(8);//        int height = height();
//        System.out.println(height);tree.);System.out.println();}}

平衡二叉树-支持泛型（2022-06-14）

package enerics;/*** @Author mabo* @Description   平衡二叉树*/public class BalancedBinaryTree<K extends Comparable<K>,V>{private BRNode root=new BRNode();class BRNode<K extends Comparable<K>,V>{private BRNode left;private BRNode right;private K key;private V value;public BRNode() {}public BRNode( K key, V value) {this.key = key;this.value = value;}public K getKey() {return key;}public void setKey(K key) {this.key = key;}public V getValue() {return value;}public void setValue(V value) {this.value = value;}public int leftHeight(){if (left!=null){return left.height();}return 0;}public int rightHeight(){if (right!=null){return right.height();}return 0;}public int height(){return Math.max(left==null?0:left.height(), right==null?0:right.height())+1;}}/*** @Author mabo* @Description 右旋转*/public void rotateRight(BRNode treeNode){BRNode newNode = new BRNode(treeNode.key,treeNode.value);newNode.right=treeNode.right;newNode.left=treeNode.left.right;treeNode.value=treeNode.left.value;treeNode.left=treeNode.left.left;treeNode.right=newNode;}/*** @Author mabo* @Description 左旋转*/private void rotateLeft(BRNode treeNode) {BRNode newNode = new BRNode(treeNode.key,treeNode.value);newNode.left=treeNode.left;newNode.right=treeNode.right.left;treeNode.value=treeNode.right.value;treeNode.right=treeNode.right.right;treeNode.left=newNode;}public void putByNode(BRNode treeNode,K key, V value) {if (root.key==null){root =new BRNode(key,value);}else {int compare = treeNode.keypareTo(key);if (compare> 0) {if (treeNode.left==null||treeNode.left.value==null){treeNode.left=new BRNode(key,value);}else {putByNode(treeNode.left,key,value);}}else if(compare< 0){if (treeNode.right==null||treeNode.right.value==null){treeNode.right=new BRNode(key,value);}else {putByNode(treeNode.right,key,value);}}}//左情况 右旋转if (treeNode.leftHeight()-treeNode.rightHeight()>=2){if (treeNode.left.leftHeight()<treeNode.left.rightHeight()){//左子树的右边大于左边，先左旋再右旋转BRNode node=treeNode.left;rotateLeft(node);}rotateRight(treeNode);}//右情况 左旋转if (treeNode.leftHeight()-treeNode.rightHeight()<=-2){if (treeNode.right.leftHeight()>treeNode.right.rightHeight()){//左子树的左边大于右边，先右旋再左旋转BRNode node=treeNode.right;rotateRight(node);}rotateLeft(treeNode);}}public void frontShow(BRNode treeNode) {System.out.print(treeNode.value+"  ");if ( treeNode.left!=null){frontShow(treeNode.left);}if ( treeNode.right!=null){frontShow(treeNode.right);}}public void put( K key,V value) {putByNode(root,key,value);}public static void main(String[] args) {BalancedBinaryTree tree=new BalancedBinaryTree();//测试左左
//        tree.put(8,8);
//        tree.put(9,9);
//        tree.put(6,6);
//        tree.put(7,7);
//        tree.put(5,5);
//        tree.);
//        System.out.println();
//        tree.put(4,4);
//测试右右
//        tree.put(5,5);
//        tree.put(2,2);
//        tree.put(7,7);
//        tree.put(6,6);
//        tree.put(8,8);
//        tree.);
//        System.out.println();
//        tree.put(9,9);//        //测试左旋再右旋
//        tree.put(10,10);
//        tree.put(6,6);
//        tree.put(11,11);
//        tree.put(5,5);
//        tree.put(7,7);
//        tree.);
//        System.out.println();
//        tree.put(8,8);测试右旋再左旋tree.put(7,7);tree.put(6,6);tree.put(10,10);tree.put(11,11);tree.put(9,9);tree.);System.out.println();tree.put(8,8);//        int height = height();
//        System.out.println(height);tree.);System.out.println();}}