从零开始学数据结构和算法 (四) 哈希表的思想和二叉树入门
特点
数组(顺序表)：寻址容易
链表：插入与删除容易
哈希表：寻址容易，插入删除也容易的数据结构
HashTable
哈希表（HashTable, 也叫散列表）
是根据关键码值(Key value)而直接进行访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
关键码值(Key value)也可以当成是 key 的 hash 值
这个映射函数叫做散列函数
存放记录的数组叫做散列表
HashTable 例子
Key : {14, 19, 5, 7, 21, 1, 13, 0, 18} 散列表: 大小为 13 的数组 a[13]; 散列函数: f(x) = x mod 13;
hashtable 需要自定义的内容
散列函数与散列表大小 hash 冲突的解决方案 装填因子：为什么需要这个值？因为数据越接近数组最大值，可能产生冲突的情况就越多
缺点
扩容需要大量的空间和性能
应用
电话号码、字典、点歌系统、QQ、微信的好友等
设计（拉链法）
JDK 1.8 以前
JDK 1.8 开始
当链表长度超过阈值，就转成红黑树
树
什么是树
树的概念
节点与树的度
结点拥有的子树数称为结点的度。 度为 0 的结点称为叶子结点或终端结点，度不为 0 的结点称为非终端结点或分支结点。 除根结点以外，分支结点也称为内部结点。 树的度是树内各结点的度的最大值。
层次和深度
森林
树的存储结构
双亲表示法
孩子表示法
双亲孩子表示法
把每个结点的孩子结点排列起来，以单链表作为存储结构， 则 n 个结点有 n 个孩子链表，如果是叶子结点则此单链表为空， 然后 n 个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中
孩子兄弟表示法
孩子兄弟表示法为每个节点设计三个域： 一个数据域，一个该节点的第一个孩子节点域，一个该节点的下一个节点的兄弟指针域
ew2/2/w/1240)
二叉树
概念
斜树
满二叉树
完全二叉树
定义：
若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。
所有的叶结点都出现在第 k 层或 k-l 层（层次最大的两层）
对任一结点，如果其右子树的最大层次为 L，则其左子树的最大层次为 L 或 L+l。
一棵二叉树至多只有最下面的两层上的结点的度数可以小于 2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。
二叉树的存储结构
顺序存储
链式存储
二叉树的遍历
前序 ( DLR )
规则是若二叉树为空，则空操作返回，否则先访问跟结点，然后前序遍历左子树，再前序遍历右子树
中序 ( LDR )
规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点）， 中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树
后续 ( LRD )
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点
二叉树简单代码实现
public class BinarayTree {
Node<String> root;
public BinarayTree(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);
评论