哈希表

哈希表介绍

散列表也叫哈希表，是根据关键码值而直接进行访问的数据结构，也就是说，它通过把关键码值映射到表中一个位置来访问计录，以加快查找的速度。这个映射函数叫做散列函数，存放计录的数组叫做散列表。

import java.util.Scanner;

public class HashTabDemo {
    public static void main(String[] args) {

        //创建哈希表
        HashTab hashTab = new HashTab(7);
        //写一个简单的菜单
        String key ="";
        Scanner scanner = new Scanner(System.in);
        while (true){
            System.out.println("add:添加雇员");
            System.out.println("list:显示雇员");
            System.out.println("exit:退出系统");

            key = scanner.next();
            switch (key){
                case "add":
                    System.out.println("输入id");
                    int id = scanner.nextInt();
                    System.out.println("输入名字");
                    String name = scanner.next();
                    //创建雇员
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
            }

        }

    }
}
//创建哈希表
class  HashTab{
   private EmpLinkedList[] empLinkedListArray;
   private  int size;

   //构造器
    public  HashTab(int size){
        this.size = size;
        //初始化empLinkedListArray
        empLinkedListArray = new EmpLinkedList[size];
        //初始化每一条链表
        for (int i = 0; i <size ; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }
    //添加雇员
    public void add(Emp emp){
        //根据员工id,得到该员工应当添加到哪条了链表
        int  empLinkedListNO =hashFun(emp.id);
        //将emp 添加到对应的链表中
        empLinkedListArray[empLinkedListNO].add(emp);
    }
    //遍历所有的链表
    public void list(){
        for (int i = 0; i <size ; i++) {
            empLinkedListArray[i].list();
        }
    }

    //编写散列函数，使用一个简单取模法
    public  int hashFun(int id ){
        return id %size;
    }
}
//表示一个雇员
class  Emp{
    public int id;
    public String name;
    public Emp next;

    public Emp(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
}

//创建EmpLinkedList,表示链表
class EmpLinkedList{
    //头指针，执行第一个Emp,因此我们这个链表的head 是指向第一个Emp
    private Emp head;

    //添加雇员到链表
    public void add(Emp emp) {
        //如果是第一个雇员
        if (head == null) {
            head = emp;
            return;
        }
        //如果不是第一个雇员，则使用一个辅助的指针，帮助定位到最后
        Emp curEmp = head;
        while (true) {
            if (curEmp.next == null) {//说明到链表最后
                break;
            }
            curEmp = curEmp.next; //后移
        }
        //退出是直接将emp,加入到链表
        curEmp.next = emp;
    }
    //遍历链表的雇员信息
    public void list(){
        if (head == null){
            System.out.println("空");
            return;
        }
        System.out.println("当前链表的信息为");
        Emp curEmp = head; //辅助指针
        while (true){
            System.out.printf("=>id%d name=%s\t",curEmp.id,curEmp.name);
            if (curEmp.next == null){
                break;
            }
            curEmp =curEmp.next;
        }
    }
}

树

二叉树的概念和常用术语

1. 常用术语：节点 根节点 父节点 子节点 叶子节点（没有子节点的节点） 节点的权。。。。
2. 每个节点只能有两个子节点的一种形式成为二叉树
3. 二叉树的子节点分为左节点和右节点
4. 如果该二叉树的所有叶子节点都在最后一层，并且节点总数为2^n-1,n为层数，则称为满二叉树

二叉树的前中后序遍历

1. 前序遍历：先输出父节点，在遍历左子树和右子树
2. 中序遍历：先遍历左子树，在输出父节点，在遍历右子树
3. 后序遍历：先遍历左子树，在遍历右子树，最后输出父节点

package tree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode node1 = new HeroNode(1, "songjiang");
        HeroNode node2 = new HeroNode(2, "wuyong");
        HeroNode node3 = new HeroNode(3, "lujunyi");
        HeroNode node4 = new HeroNode(4, "linchong");

        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
        binaryTree.setRoot(node1);
        binaryTree.infixOrder();



    }
}
class  BinaryTree{
    private  HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //前序遍历
    void preOrder(){
        if (this.root != null){
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }
    //中序遍历
    void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
    //后续遍历
    void postOrder(){
        if (this.root != null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }
}
class  HeroNode{
    private  int no;
    private String name;
    private  HeroNode left;
    private  HeroNode right;

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

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //前序遍历
    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 postOrder(){
        if (this.left!=null){
            this.left.postOrder();
        }
        if (this.right!=null){
            this.right.postOrder();
        }
        System.out.println(this);//父节点
    }
}

二叉树的查找

//前序遍历查找
    public HeroNode preOrdersearch(int no){
        //比较当前结点是不是
        if (this.no == no){
            return  this;
        }
        //判断当前节点的左子节点是否为空，如果不为空，则递归前序查找
        //如果左递归前序查找，找到节点，则返回
        HeroNode resNode = null;
        if (this.left != null){
            resNode = this.left.preOrdersearch(no);
        }
        if (resNode != null){
            return  resNode;
        }
        if (this.right != null){
            resNode = this.right.preOrdersearch(no);
        }
        return resNode;
    }
    //中序遍历查找
    public HeroNode infixOrderSearch(int no){
        //判断当前节点的左子节点是否为空，如果不为空，则递归中序查找
        HeroNode resNode = null;
        if (this.left != null){
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null){
            return  resNode;
        }
        if (this.no == no){
            return this;
        }
        //否则继续进行右递归中序查找
        if (this.right != null){
            resNode = this.right.infixOrderSearch(no);
        }
        return  resNode;
    }
    //后序遍历查找
    public HeroNode postOrderSearch(int no){
        HeroNode resNode =null;
        if (this.left!=null){
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null){
            return  resNode;
        }
        if (this.right!=null){
            resNode =this.right.postOrderSearch(no);
        }
        if (resNode !=null){
            return resNode;
        }
        if (this.no == no){
            resNode = this;
        }
        return resNode;
    }

线索化二叉树

1. n个节点的二叉链表中含有n+1【公式2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该节点在某种遍历次序下的前驱和后继节点的指针