查找算法

1. 链式查找
2. 二分查找
   前提是有序集合，通过比较中间值确定擦找的具体范围

   public static void main(String[] args) {
       int[] array = {
               1, 3, 5, 7, 9, 11, 13, 15, 17, 19
       };
       HalfSerach hs = new HalfSerach();
       int value = 3;
       int index = hs.halfSerach(array, 0, array.length - 1, value);
       System.out.println(value + "-index :" + index);
   }

   private int halfSerach(int[] array, int start, int end, int value) {
       if (start > end) {
           return -1;
       }
       int mid = (start + end) / 2;
       if (value > array[mid]) {
           return halfSerach(array, mid + 1, end, value);
       } else if (value < array[mid]) {
           return halfSerach(array, start, mid - 1, value);
       } else {
           return mid;
       }
   }

3. 插值查找
   和二分查找系共同，只是对中间值的一个动态匹配，对于均匀的结合效率较高

int mid = start + (value - array[start]) / (array[end] - array[start]) * (end - start);

4. 斐波那契查找
5. 树查找
   树的前、中、后序遍历，查找，删除

public class BinaryTree {

    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        TreeNode root = new TreeNode(1, "Ralap01");
        TreeNode ralap02 = new TreeNode(2, "Ralap02");
        TreeNode ralap03 = new TreeNode(3, "Ralap03");
        TreeNode ralap04 = new TreeNode(4, "Ralap04");
        TreeNode ralap05 = new TreeNode(5, "Ralap05");
        root.left = ralap02;
        root.right = ralap03;
        ralap03.left = ralap05;
        ralap03.right = ralap04;
        bt.setRoot(root);
        System.out.println("前序");
        bt.preOrder();
        System.out.println("中序");
        bt.infixOrder();
        System.out.println("后续");
        bt.laterOrder();
        System.out.println("==================================================");
        int serach = 5;
        TreeNode treeNode = bt.preSerach(serach);
        System.out.println(treeNode);
        treeNode = bt.infixSerach(serach);
        System.out.println(treeNode);
        treeNode = bt.laterSerach(serach);
        System.out.println(treeNode);
        System.out.println("=====================");
        TreeNode del = bt.del(5);
        System.out.println(del);
        System.out.println("-----------");
        bt.preOrder();

    }


    private TreeNode root;

    public BinaryTree setRoot(TreeNode root) {
        this.root = root;
        return this;
    }

    public void preOrder() {
        if (root != null) {
            root.preOrder();
        }
    }

    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        }
    }

    public void laterOrder() {
        if (root != null) {
            root.laterOrder();
        }
    }

    public TreeNode preSerach(int no) {
        return root.preSerach(no);
    }

    public TreeNode infixSerach(int no) {
        return root.infixSerach(no);
    }

    public TreeNode laterSerach(int no) {
        return root.laterSerach(no);
    }


    public TreeNode del(int no) {
        TreeNode delNode = null;
        if (root != null) {
            if (root.no != no) {
                delNode = root.del(no);
            } else {
                delNode = root;
                root = null;
            }
        } else {
            System.out.println("数不能为空");
        }
        return delNode;
    }
}

class TreeNode {

    public int no;
    public String name;
    public TreeNode left;
    public TreeNode right;

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

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("TreeNode{");
        sb.append("no=").append(no);
        sb.append(", name='").append(name).append('\'');
        sb.append('}');
        return sb.toString();
    }

    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    public void laterOrder() {
        if (this.left != null) {
            this.left.laterOrder();
        }
        if (this.right != null) {
            this.right.laterOrder();
        }
        System.out.println(this);
    }

    public TreeNode preSerach(int no) {
        TreeNode resNode = null;
        System.out.println("一一一一一一一一一");
        if (this.no == no) {
            return this;
        }
        if (this.left != null) {
            resNode = this.left.preSerach(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.preSerach(no);
        }
        return resNode;
    }

    public TreeNode infixSerach(int no) {
        TreeNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixSerach(no);
        }

        if (resNode != null) {
            return resNode;
        }
        System.out.println("二二二二二二二二");

        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            resNode = this.right.infixSerach(no);
        }
        return resNode;
    }

    public TreeNode laterSerach(int no) {
        TreeNode resNode = null;
        if (this.left != null) {
            resNode = this.left.laterSerach(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.laterSerach(no);
        }
        if (resNode != null) {
            return resNode;
        }
        System.out.println("三三三三三三");
        if (this.no == no) {
            return this;
        }
        return resNode;
    }

    TreeNode delNode = null;

    public TreeNode del(int no) {
        if (this.left != null) {
            if (this.left.no == no) {
                delNode = this.left;
                this.left = null;
            } else {
                delNode = this.left.del(no);
            }
        }
        if (delNode != null) {
            return delNode;
        }
        if (this.right != null) {
            if (this.right.no == no) {
                delNode = this.right;
                this.right = null;
            } else {
                delNode = this.right.del(no);
            }
        }
        return delNode;
    }
}