Java实现二叉树和常见的排序

前言

这里总结对二叉树和排序做一下笔记，记不清的时候可以翻来看看。

二叉树

二叉树分为根节点，双亲节点，叶子节点，节点的度不能超多2，左孩子小于双亲节点，右孩子大于双亲节点。

public class Tree {
public int data;
public Tree father,leftSon,rightSon;
public boolean isLeftSon = true;
public static Tree root;

public boolean hasleft(){
return leftSon!=null;
  }

public boolean hasRight(){
return rightSon!=null;
  }

public Tree(boolean isLeftSon) {
super();
this.isLeftSon = isLeftSon;
  }



public Tree() {
super();
}

public void insert(Integer data,Tree father){
//如果father为null创建根节点，root.data = data;
if(father == null){
          root = new Tree();
          root.data = data;
return;
      }
//在father节点插入的时候要判断当前树的根节点是否存在，否则返回
if(root == null){
return;
      }
//插入的data和双亲节点的data比较大小
int compare = data.compareTo(father.data);
//data相等的话，接返回，插入失败
if(compare==0)return;
//如果插入的data大于双亲节点的data，则在右子树种查找
if(compare>0){
//没有右孩子，则将data作为father的右孩子节点
if(!father.hasRight()){
              father.rightSon = new Tree(false);
              father.rightSon.data = data;
              father.rightSon.father = father;
          }else insert(data,father.rightSon);//有右孩子，就将father指向father.rightSon
      }else{
//左孩子(同理)
if(!father.hasleft()){
              father.leftSon = new Tree(false);
              father.leftSon.data = data;
              father.leftSon.father = father;
          }else insert(data,father.leftSon);
      }
  }
//这里直接将root作为插入点，不断的寻找合适的插入点
public void insert(Integer data){
if(root == null){
             root = new Tree();
             root.data = data;
return;
        }
if(data.compareTo(root.data)==0){
return;
        }
        insert(data,root);
    }
//从root节点开始遍历
public static void list(){
if(root==null)return;
        list(root);
    }
//从指定节点开始遍历(前序遍历)
public static void list(Tree tree){
if(tree==null)return;
        System.out.println(tree.data);
if(tree.hasleft())list(tree.leftSon);
if(tree.hasRight())list(tree.rightSon);
    }
}

调用

public static void main(String[] args) {
        Tree tree = new Tree();
        tree.insert(56);
        tree.insert(23);
        tree.insert(98);
        tree.insert(12);
        tree.insert(54);
        tree.insert(67);
        tree.insert(99);
        tree.insert(53);
        tree.insert(76);
        tree.insert(45);
        tree.insert(32);
        Tree.list()
    }
    结果：56 23 12 54 53 45 32 98 67 76 99 

冒泡排序

//不断和相邻的数值比较，每趟比较次数减少1，循环n次，大的数沉到右侧
public static void maopaoSort(int a[]){
for (int i = 0; i < a.length-1; i++) {
for (int j = 0; j < a.length-1-i; j++) {
if(a[j]>a[j+1]){
int max = a[j];
                    a[j] = a[j+1];
                    a[j+1] = max;
                }
            }
        }
for (int i : a) {
            System.out.print(i + " ");
        }

    } 

选择排序

//循环n次，每次找出最小的数
public static void selectSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] <a[min]) {
min = j;
                }
            }
if (min != i) {
int c = a[min];
                a[min] = a[i];
                a[i] = c;
            }
        }
            System.out.print(i + " ");
        }
    }

快速排序

public static void soonSort(int[] a,int low,int hight){
//开始第一步是从右找---第一回和找到比基准小的，交换，找不到就左移
//接下来左侧查找---找到比基准大的，交换，找不到就右移
//知道i》j结束循环
//----
//接下来分组进行查找，递归
int i, j, index;
if (low > hight) {
return;
            }
            i = low;
            j = hight;
index = a[i]; // 用子表的第一个记录做基准
while(i<j){
while(i<j && a[j]>=index)
                    j--;
if(i<j)a[i++] = a[j];
while(i<j&&a[i] <= index)
                i++;
if(i<j)a[j--] = a[i];
           }
            a[i] = index;
            soonSort(a, low, i - 1); // 对低子表进行递归排序
            soonSort(a, i + 1, hight); // 对高子表进行递归排序
    }