树论基础&归并排序

  1 //代表结点node
  2 class Node{
  3     private char data;//代表字母
  4     private Node leftNode;//左边node
  5     private Node rightNode;//右边node
  6     //构造方法
  7     public Node(char data, Node leftNode, Node rightNode) {
  8         super();
  9         this.data = data;
 10         this.leftNode = leftNode;
 11         this.rightNode = rightNode;
 12     }
 13     //get set方法
 14     public char getData() {
 15         return data;
 16     }
 17 
 18     public void setData(char data) {
 19         this.data = data;
 20     }
 21 
 22     public Node getLeftNode() {
 23         return leftNode;
 24     }
 25 
 26     public void setLeftNode(Node leftNode) {
 27         this.leftNode = leftNode;
 28     }
 29 
 30     public Node getRightNode() {
 31         return rightNode;
 32     }
 33 
 34     public void setRightNode(Node rightNode) {
 35         this.rightNode = rightNode;
 36     }
 37 }
 38 /**
 39  * 二叉树遍历
 40  */
 41 public class BinaryTree {
 42 
 43     //输出方法
 44     public static void print(Node node){
 45         System.out.print(node.getData());
 46     }
 47     
 48     //前序遍历 根结点→左子树→右子树
 49     public void pre(Node root){
 50         print(root);
 51         if(root.getLeftNode()!=null){
 52             pre(root.getLeftNode());
 53         }
 54         if(root.getRightNode()!=null){
 55             pre(root.getRightNode());
 56         }
 57     }
 58     //中序遍历 左子树→根结点→右子树
 59     public void in(Node root){
 60         if(root.getLeftNode()!=null){
 61             in(root.getLeftNode());
 62         }
 63         print(root);
 64         if(root.getRightNode()!=null){
 65             in(root.getRightNode());
 66         }
 67     }
 68     //后续遍历 左子树→右子树→根结点
 69     public void post(Node root){
 70         if(root.getLeftNode()!=null){
 71             post(root.getLeftNode());
 72         }
 73         if(root.getRightNode()!=null){
 74             post(root.getRightNode());
 75         }
 76         print(root);
 77     }
 78 
 79     public static void main(String[] args) {
 80         //初始化树结构数据
 81         Node D=new Node('D',null,null);
 82         Node H=new Node('H',null,null);
 83         Node K=new Node('K',null,null);
 84         Node C=new Node('C',D,null);
 85         Node B=new Node('B',null,C);
 86         Node G=new Node('G',H,K);
 87         Node F=new Node('F',G,null);
 88         Node E=new Node('E',null,F);
 89         Node A=new Node('A',B,E);
 90 
 91         //调用前序遍历
 92         BinaryTree tree=new BinaryTree();
 93         System.out.println("前序遍历");
 94         tree.pre(A);
 95         System.out.println();
 96 
 97         //中序遍历
 98         System.out.println("中序遍历");
 99         tree.in(A);
100         System.out.println();
101 
102         //后续遍历
103         System.out.println("后序遍历");
104         tree.post(A);
105 
106     }
107 }

 1 import java.util.Arrays;
 2 
 3 /**
 4  * 归并排序
 5  */
 6 public class MergeSort {
 7 
 8     public static void main(String[] args) {
 9         int[] data=new int[]{1,5,2,7,0,4,100};
10         mergeSort(data,0,data.length-1);
11         //打印输出
12         System.out.println(Arrays.toString(data));
13     }
14 
15     //拆分，按照中间索引位置分为左边部分和右边部分，拆分完后进行合并
16     public static void mergeSort(int[] data,int left,int right){
17         if(left<right){
18 
19             int mid=(left+right)/2;
20             System.out.println(mid);
21 
22             //左边继续拆分，递归
23             mergeSort(data,left,mid);
24             System.out.println("左边分好了");
25 
26             //右边继续拆分，递归
27             mergeSort(data,mid+1,right);
28             System.out.println("右边分好了");
29 
30             //左右拆分完成和进行合并
31             merge(data,left,mid,right);
32         }
33     }
34 
35 
36     /**
37      * 比较左右子树并进行合并
38      * @param data 传入的数组
39      * @param left 左子树的最左边索引
40      * @param mid 拆分位置的索引
41      * @param right 右子树的最右边索引
42      */
43     public static void merge(int[] data,int left,int mid,int right){
44         int[] tmp=new int[data.length];//临时存储比较后的数字
45         int loc=left;//存进去临时数组的起始位置，从left开始
46         int point1=left;//左子树的起始位置
47         int point2=mid+1;//右子树的起始位置
48         //左右子树开始轮流取值比较，将更小的放到临时数组里去
49         while(point1<=mid&&point2<=right){
50             if(data[point1]<data[point2]){
51                 tmp[loc]=data[point1];
52                 loc++;
53                 point1++;
54             }else{
55                 tmp[loc]=data[point2];
56                 loc++;
57                 point2++;
58             }
59         }
60         //上面比较完后最理想情况是左右子树所有的数都放到了临时数组，但是实际情况不是这么完美的，总会有一个子树会多留一点数据
61         //多留的一部分数据直接加到临时数组的后面
62         while (point1<=mid) {
63             tmp[loc++]=data[point1++];
64         }
65         while(point2<=right){
66             tmp[loc++]=data[point2++];
67         }
68         //最后将临时数组按照索引一一更新到原数组中
69         for (int i = left; i <=right; i++) {
70             data[i]=tmp[i];
71         }
72     }
73 }