数据结构与算法(六,哈希表和二叉树)

哈希表

哈希表的概念:

是通过关键码值(key value)来直接访问的数据结构,他通过将关键码值映射到表中的一个位置来访问记录,以加快查找速度.

其中关键码值(key value)也可以当做key的hash值
映射函数叫做散列函数
存放记录的数组叫做散列表

如何解决hash冲突:

1. 装填因子:设置装填因子,如0.8,即,当删列表达到80%,就对删列表扩容,因为越接近数组最大值,发生hash冲突概率越大
2. 采用数组加链表方式保存,相同的数组位置后面加上两边的形式保存下一个散列值,当数据量过大时,用红黑树的方式

拉链法:

image.png image.png

缺点:扩容需要消费大量的空间和性能
应用:电话号码，字典，点歌系统，QQ，微信的好友等

二叉树

二叉树概念

image.png

二叉树的创建

二叉树的遍历(中序(LDR),前序(DLR),后序(LRD))

public class BinaryTree {

    Node<String> root;
    public BinaryTree(String data){
        root=new Node<>(data,null,null);
    }
    public void createTree(){
        Node<String> nodeB=new Node<String>("B",null,null);
        Node<String> nodeC=new Node<String>("C",null,null);
        Node<String> nodeD=new Node<String>("D",null,null);
        Node<String> nodeE=new Node<String>("E",null,null);
        Node<String> nodeF=new Node<String>("F",null,null);
        Node<String> nodeG=new Node<String>("G",null,null);
        Node<String> nodeH=new Node<String>("H",null,null);
        Node<String> nodeJ=new Node<String>("J",null,null);
        Node<String> nodeI=new Node<String>("I",null,null);
        root.leftChild=nodeB;
        root.rightChild=nodeC;
        nodeB.leftChild=nodeD;
        nodeC.leftChild=nodeE;
        nodeC.rightChild=nodeF;
        nodeD.leftChild=nodeG;
        nodeD.rightChild=nodeH;
        nodeE.rightChild=nodeJ;
        nodeH.leftChild=nodeI;

    }

    /**
     * 中序遍历
     * @param root
     */
    public  void  middleSortTravel(Node root){
        if (root==null){
            return;
        }
        middleSortTravel(root.leftChild);
        System.out.println("mid "+root.e);
        middleSortTravel(root.rightChild);
    }

    /**
     * 前序遍历
     * @param root
     */
    public void preSortTravel(Node root){
        if (root==null){
            return;
        }
        System.out.println("pre "+root.e);
        preSortTravel(root.leftChild);
        preSortTravel(root.rightChild);
    }

    /**
     * 后序遍历
     * @param root
     */
    public void postSortTravel(Node root){
        if (root==null){
            return;
        }

        postSortTravel(root.leftChild);
        postSortTravel(root.rightChild);
        System.out.println("post "+root.e);
    }



    public class Node<T>{
        T e;
        Node<T> leftChild;
        Node<T> rightChild;

        public Node(T e, Node<T> leftChild, Node<T> rightChild) {
            this.e = e;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
    }
}