哈希表
介绍
首先哈希表是一种数据结构，又称散列表，在jdk底层中像HashSet，HashTable，HashMap的底层都使用了哈希表来实现。
我理解哈希表就是在一个数组中存放链表或者其他的数据结构(比如jdkl1.8之后对于数据较多时HashMap使用的是红黑树)，数组的每一个元素都是一个链表。通过一个hash函数来求出存储的数据的某一个关键字的哈希值，通过这个哈希值来寻找该数据属于数组的哪一个元素，将其放入。
这样做可以大幅度减少，查询，添加，删除等操作的效率。
图示
百度上找的QAQ
_Hash%E8%A1%A8_1594128630675.png?x-oss-process=byfree)
简易实现Hash表
首先确定我们在HashTab的数组中存储链表，所以我们先要创建一个链表
要想是实现一个链表首先要创建一个Node节点
Node节点编写
这里我们节点用来模拟一个雇员，为了简便只编写两个信息，id和姓名
class Emp {
public int id;
public String name;
public Emp next; // next默认为空
public Emp(int id, String name) {
this.id = id;
this.name = name;
}
}
实现链表
这里我们定义链表的头节点存储第一个有效数据
class EmpLinkedList {
private Emp head; // 默认为空
}
编写add(添加员工方法)
假定，当添加雇员时id是自增长，即id的分配总是从小到大因此我们将该雇员直接加入到本链表的最后即可
public void add(Emp emp) {
// 如果是添加第一个雇员
if(head == null) {
head = emp;
return;
}
// 如果不是第一个雇员则需要一个辅助的指针帮助定位到最后
Emp cur = head;
while (cur.next != null) {
cur = cur.next;
}
// 退出时候将emp加入到最后即可
cur.next = emp;
}
遍历list方法
这里传入no是代表，在hashtab中的第几个链表，为了打印出来的样式美观
// 遍历链表的雇员信息
public void list(int no) {
if (head == null) {
System.out.println("第" + no + "链表为空");
return;
}
System.out.print("第" + no + "链表的信息为：");
Emp cur = head;
while (true) {
if (cur == null) {
return;
}
System.out.printf("->id=%d name=%s\t", cur.id, cur.name);
cur = cur.next;
}
}
查找方法
// 根据id查找雇员
public Emp findEmpById(int id) {
// 判断链表是否为空
if (head == null) {
return null;
}
Emp cur = head;
while (true) {
if(cur.id == id) {
break;
}
if(cur.next == null) {
cur = null;
break;
}
cur = cur.next;
}
return cur;
}
HashTab实现
构造器中传入size，用来决定empLinkedListArray的大小
注意不要忘记实例化数组中的每一个链表，不然会报空指针
// 创建hashTable
class HashTab {
private EmpLinkedList[] empLinkedListArray;
private int size;
// 构造器
public HashTab(int size) {
this.size = size;
// 初始化链表
empLinkedListArray = new EmpLinkedList[size];
// 实例化每一个链表
for (int i = 0; i < size; i++) {
empLinkedListArray[i] = new EmpLinkedList();
}
}
}
散列方法编写
这里使用最简单的膜除法来编写散列函数
// 编写一个散列函数，使用简单的取模法
public int hashFun(int id) {
return id % size;
}
添加方法编写
这个就很简单了，用散列方法来判断待添加的元素需要添加到那个链表中，再调用链表中的添加方法就好了
public void add(Emp emp) {
// 首先根据员工的id，得到该员工应该添加到那条链表
int empLinkedListNo = hashFun(emp.id);
// 将emp添加到对应的链表中
empLinkedListArray[empLinkedListNo].add(emp);
}
遍历方法编写
这个也很简单，遍历所有的链表，调用链表的list方法即可
// 遍历哈希表
public void list() {
for (int i = 0; i < size; i++) {
empLinkedListArray[i].list(i);
System.out.println();
}
}
查找方法编写
先用散列方法判断，待查找数据在哪个链表中，然后使用链表中的查找方法即可
// 查找雇员
public void findEmpById(int id) {
// 使用散列函数到那条链表查找
int empLinkedListNo = hashFun(id);
Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id);
if (emp != null) {
System.out.println("在第" + empLinkedListNo + "链表找到");
} else {
System.out.println("未找到");
}
}
测试代码
public class HashTableDemo {
public static void main(String[] args) {
HashTab h = new HashTab(5);
Emp e1 = new Emp(1, "张三");
Emp e2 = new Emp(2, "李四");
Emp e3 = new Emp(3, "王五");
Emp e4 = new Emp(4, "赵六");
Emp e5 = new Emp(5, "钱七");
Emp e6 = new Emp(6, "魏八");
h.add(e1);
h.add(e2);
h.add(e3);
h.add(e4);
h.add(e5);
h.add(e6);
h.list();
h.findEmpById(5);
}
}
结果
_HashTab%E7%BB%93%E6%9E%9C_1594186653325.png?x-oss-process=byfree)
树(二叉树)
基本概念介绍(树)
研究树结构通常是研究二叉树结构这里就先介绍二叉树的基本概念和性质。
定义
递归定义：二叉树(binary tree) 是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
基本形态
- 空二叉树
- 只有一个根节点的二叉树
- 只有左子树
- 只有右子树
- 完全二叉树
图片来源于百度
_%E6%A0%91%E7%9A%84%E5%9F%BA%E6%9C%AC%E5%BD%A2%E6%80%81_1595062364576.gif?x-oss-process=byfree)
术语介绍
- 节点：包含一个数据元素及若干指向子树分支的信息
- 节点的度：一个结点拥有子树的数目称为结点的度
- 叶子节点：也称为终端结点，没有子树的结点或者度为零的结点
- 层次：根节点为第1层，一次类推，根节点的子节点为第2层
- 树的高度：当前树的最大层次，即为树的高度
- 森林：简单来说就是由多个不相交的树就能构成一个森林
二叉树的性质
- 二叉树的第i层上至多有$2^{i+1}$ (i>=1)个节点
- 深度为h的二叉树中之多含有$2^h-1$个节点
- 若在任意一颗二叉树中，有$n_1$个叶子节点，有$n_2$个度为2的节点，则必有$n_1=n_2+1$
- 具有n个节点的完全二叉树高度为$log_2(n-1)+1$个节点
二叉树的遍历
前序/中序/后序遍历的实现
这里遍历中的先中后指的是根节点的遍历优先度，所以也叫先根/中根/后根遍历
思想
- 前序遍历
先输出根节点，然后判断左子树是否为空，不为空则前序遍历左子树，在判断右子树是否为空，不为空再先序遍历右子树
- 中序遍历
先判断左子树是否为空，不为空则中序遍历左子树，然后输出根节点，在判断右子树是否为空，不为空再中序遍历右子树
- 后序遍历
先判断左子树是否为空，不为空则后序遍历左子树，然后判断右子树是否为空，不为空再后序遍历右子树，最后输出根节点
例如
图中前序遍历为：宋江->吴用->卢俊义->关胜->林冲
中序遍历为：吴用->宋江->关胜->卢俊义->林冲
后序遍历为：吴用->关胜->林冲->卢俊义->宋江
实现
节点类编写
class HeroNode {
private int no;
private String name;
private HeroNode left; // 默认null
private HeroNode right; // 默认null
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
// 略写了Get和Set方法
@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);
}
}
二叉树编写
// 定义一个BinaryTree二叉树
class BinaryTree {
private HeroNode root;
public void setRoot(HeroNode root) {
this.root = root;
}
// 前序遍历
public void preOrder() {
if (this.root != null) {
this.root.preOrder();
} else {
System.out.println("二叉树为空");
}
}
// 中序遍历
public void infixOrder() {
if (this.root != null) {
this.root.infixOrder();
} else {
System.out.println("二叉树为空");
}
}
// 后序遍历
public void postOrder() {
if (this.root != null) {
this.root.postOrder();
} else {
System.out.println("二叉树为空");
}
}
}
测试主方法编写
public class BinaryTreeDemo {
public static void main(String[] args) {
// 创建一棵二叉树
BinaryTree binaryTree = new BinaryTree();
// 创建节点
HeroNode root = new HeroNode(1, "宋江");
HeroNode node2 = new HeroNode(2, "吴用");
HeroNode node3 = new HeroNode(3, "卢俊义");
HeroNode node4 = new HeroNode(4, "林冲");
binaryTree.setRoot(root);
// 说明，我们先手动创建二叉树
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
System.out.println("前序遍历");
binaryTree.preOrder();
System.out.println("中序遍历");
binaryTree.infixOrder();
System.out.println("后序遍历");
binaryTree.postOrder();
}
}
二叉树的节点删除
规定
因为这里只是简单的体验一下二叉树的删除节点操作，所以使用简单的规定，以后再使用复杂的规定来优化。
- 如果待删除的节点为叶子节点，则直接删除该节点
- 如果待删除的节点不是叶子节点，则删除节点代表的子树
思想分析
首先我们要解决的就是单向链表的局限性，如果待删除节点我们找到为当前节点，就需要当前节点的父节点才能删除，所以我们需要找到待删除节点的父节点即可。(和之前单向链表的删除节点思想是一个道理)
- 因为我们的二叉树是单向的，所以我们要找的是待删除节点的父节点(类似于单向链表的删除)
- 如果当前节点的左子节点，不为空且左子节点是待删除节点，就删除该节点或者该子树(this.left=null)且递归结束
- 如果当前节点的右子节点，不为空且右子节点是待删除节点，就删除该节点或者该子树(this.right=null)且递归结束
- 如果第2步和第3步没有删除节点，那么我们需要向左子树进行递归删除
- 如果第4步也没有删除节点，则需要向右子树进行递归删除
代码实现
节点类代码
这里实现的是思想中的5条也就规则中的第2条
public void delNode(int no) {
if (this.left != null && this.left.no == no) {
this.left = null;
return;
}
if (this.right != null && this.right.no == no) {
this.right = null;
return;
}
// 向左子树进行递归删除
if (this.left != null) {
this.left.delNode(no);
}
// 向右子树进行递归删除
if (this.right != null) {
this.right.delNode(no);
}
}
二叉树类代码
这里实现的是规则中的第一条，并负责调用节点中的方法
// 删除节点
public void delNode(int no) {
if (root != null) {
// 如果只有一个root节点，这里要判断root是否为待删除节点
if (root.getNo() == no) {
root = null;
} else {
// 进行递归删除
root.delNode(no);
}
} else {
System.out.println("空树不可以删除");
}
}
测试代码
public class BinaryTreeDemo {
public static void main(String[] args) {
// 创建一棵二叉树
BinaryTree binaryTree = new BinaryTree();
// 创建节点
HeroNode root = new HeroNode(1, "宋江");
HeroNode node2 = new HeroNode(2, "吴用");
HeroNode node3 = new HeroNode(3, "卢俊义");
HeroNode node4 = new HeroNode(4, "林冲");
binaryTree.setRoot(root);
// 说明，我们先手动创建二叉树
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
System.out.println("删除前的前序遍历");
binaryTree.preOrder();
binaryTree.delNode(4);
System.out.println("-------");
System.out.println("删除后的前序遍历");
binaryTree.preOrder();
}
}
顺序存储二叉树
介绍
顺序存储二叉树，其实就是在逻辑结构上是一个二叉树，而存储结构上则是一个线性表(数组)
图例
也就是说本质上是一个数组，但是在操作上要使用二叉树的方式操作，比如可以进行前序/中序/后序遍历等。
性质
- 顺序存储二叉树，通常情况只考虑完全二叉树
- 第n个元素的左子节点索引为 2 * n + 1
- 第n个元素的右子节点索引为 2 * n + 2
- 第n个元素的父节点索引为 (n - 1) / 2
- 上述n代表的是在顺序存储二叉树中是第几个元素，也可以理解为数组的下标，在上述图中也就是圆圈外的数字
代码实现案例
整体实现代码
实现顺序存储二叉树还是很简单的
这里只实现了前序遍历一个方法，跟之前的二叉树前序遍历思想一样，只不过套用了上述性质中的公式
class ArrBinaryTree {
private int[] arr; // 用于存储二叉树
public ArrBinaryTree(int[] arr) {
this.arr = arr;
}
// 暴露重载的方法不用输入索引简化操作
public void preOrder() {
this.preOrder(0);
}
// 编写方法用于遍历顺序存储的二叉树的前序遍历
public void preOrder(int i) {
// 数组为空或者arr.length=0
if (arr == null || arr.length == 0) {
System.out.println("数组为空无法遍历！");
}
// 首先打印本元素
System.out.print(arr[i]);
// 对左子树进行前序遍历，注意判断公式不能超出数组边界
if ((i * 2 + 1) < arr.length) {
preOrder(i * 2 + 1);
}
// 对右子树进行前序遍历，注意判断公式不能超出数组边界
if ((i * 2 + 2) < arr.length) {
preOrder(i * 2 + 2);
}
}
}
测试代码
public class ArrBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
ArrBinaryTree abt = new ArrBinaryTree(arr);
abt.preOrder();
}
}
线索化二叉树
线索化二叉树介绍
在普通的二叉树中，叶子节点，的左引用和右引用，是没有作用的
在右n个节点的二叉树中有n+1个空指针域，利用这些空指针域存储，在某种遍历方法(前序/中序/后续)下的前驱或者后继节点的引用（这种附加的指针称之为线索）
这种使用了线索的二叉树就叫线索二叉树
根据线索的不同又可以分为中序线索二叉树，前序线索二叉树，后续线索二叉树
图示
线索二叉树的实现
线索化二叉树和普通的二叉树，在结构上是基本相同的，只不过前者会多一个线索化的方法
问题
这样指针域中指向的元素既有子树的还有指向前驱或者后继节点的，没有办法分辨。
在原本的HeroNode节点中添加两个属性用来表示，是子树还是前驱后继节点
// 说明：
// 如果leftType=0表示指向的是左子树如果是1表示指向前驱节点
// rightType同理
private int leftType;
private int rightType;
另外在二叉树类中添加一个pre节点来表示上一个节点
// 为了实现线索化需要创建一个指向当前节点的前驱节点的一个指针
// 在递归进行线索化时，这个pre总是保留前一个节点
private HeroNode pre = null;
方法整体代码
这里的难点大概只有一个，就是线索化当前节点中的处理后继节点
这里梳理后继节点并不是处理的当前的节点的后继节点而是上一个节点的后继节点
明白了这点这段代码就没什么难度了！
// 编写对二叉树进行中序线索化的方法
public void threadedNodes(HeroNode node) {
// 如果当前线索化的节点为空就不能线索化
if (node == null) {
return;
}
// 1. 先线索化左子树
threadedNodes(node.getLeft());
// 2. 线索化当前节点[有点难度]
// 处理当前节点的前驱节点
if (node.getLeft() == null) {
// 让当前节点的左指针指向前驱节点
node.setLeft(pre);
// 修改当前节点的左指针的类型
node.setLeftType(1); // 指向的时前驱节点
}
// 处理后继节点
if (pre != null && pre.getRight() == null) {
// 让前驱节点的右指针指向当前节点
pre.setRight(node);
// 修改前驱节点的右指针类型
pre.setRightType(1);
}
// !!! 每处理一个节点后，让当前节点时下一个节点的前驱节点
pre = node;
// 3. 线索化右子树
threadedNodes(node.getRight());
}
小作业
根据中序线索化二叉树，编写前序后序线索化二叉树
图示
前序线索化
图片少画了空的左指向为可颂
后续线索化
实现代码
前序
这里如果只改变线索化当前节点/左子树/右子树的顺序的话会出现死递归。因为先线索化当前的节点，将本来没使用的左域或者右域指向了别的引用，虽然我们明白这是指向的前驱节点或者后继节点，但是程序会一致认为这是指向子树就会形成死递归。
这里再进行线索化左子树或者右子树的时候加入判断指针域是否指向的是子树就可以了，如果指向的是子树就继续递归，如果指向的是线索则不进行递归。
public void preThreadedNodes(HeroNode node) {
if (node == null) {
return;
}
// 1. 线索化当前节点
// 处理当前节点的前驱节点
if (node.getLeft() == null) {
// 让当前节点的左指针指向前驱节点
node.setLeft(pre);
// 修改当前节点的左指针的类型
node.setLeftType(1); // 指向的时前驱节点
}
// 处理后继节点
if (pre != null && pre.getRight() == null) {
// 让前驱节点的右指针指向当前节点
pre.setRight(node);
// 修改前驱节点的右指针类型
pre.setRightType(1);
}
// !!! 每处理一个节点后，让当前节点时下一个节点的前驱节点
pre = node;
// 2. 线索化左子树
if (node.getLeftType() == 0) {
preThreadedNodes(node.getLeft());
}
// 3. 线索化右子树
if (node.getRightType() == 0) {
preThreadedNodes(node.getRight());
}
}
后序
public void postThreadedNodes(HeroNode node) {
if (node == null) {
return;
}
// 1. 线索化左子树
postThreadedNodes(node.getLeft());
// 2. 线索化右子树
postThreadedNodes(node.getRight());
// 3. 线索化当前节点
// 处理当前节点的前驱节点
if (node.getLeft() == null) {
// 让当前节点的左指针指向前驱节点
node.setLeft(pre);
// 修改当前节点的左指针的类型
node.setLeftType(1); // 指向的时前驱节点
}
// 处理后继节点
if (pre != null && pre.getRight() == null) {
// 让前驱节点的右指针指向当前节点
pre.setRight(node);
// 修改前驱节点的右指针类型
pre.setRightType(1);
}
// !!! 每处理一个节点后，让当前节点时下一个节点的前驱节点
pre = node;
}
线索化二叉树的遍历
中序线索化二叉树的遍历
中序线索化的遍历也是老师在教程中唯一演示的一种遍历方式，我就只展开记录实现这一种方式。而对于其他的两种遍历方式，就只贴出我实现的代码(含注释)毕竟是拓展内容不适合展开叙述。
ps 实现后两种遍历方式(尤其是后序的，真的很难)，参考了很多网上大佬写的文章。
// 中序线索化二叉树遍历方法一
public void threadedList1() {
// 定义一个变量，存储当前遍历的节点，从root开始
HeroNode node = root;
while(node != null) {
while (node.getLeftType() == 0) {
node = node.getLeft();
}
System.out.println(node);
// 如果当前节点的右指针指向的是后继节点，就一直输出
while (node.getRightType() == 1) {
node = node.getRight();
System.out.println(node);
}
// 替换这个遍历的节点
node = node.getRight();
}
}
具体思想：
- 首先，从root节点开始往左进行查找，直到当前节点也就是node的左面存储的不再是左子树而是存储的线索。这也是第一个内循环做的事情。
- 打印当前node
- 再查看当前节点的右面存储的是否是线索，是的话就把线索指向的节点作为当前节点打印后再查看是否为线索
- 如果右面不是线索，也就是说右面指向的是一个子树，就把当前节点变为这个子树，外循环结束，如果这个子树不为空，就继续执行外循环，直到下次外循环的这个子树为空，外循环结束，就遍历完成。
在查资料中发现Chrix9大佬实现了第二种方案这里贴出分析一下
public void threadedList2() {
HeroNode node = root;
while(node != null) {
if(node.getLeftType() == 0) {
node = node.getLeft();
}else {
System.out.println(node);
if(node.getRightType() == 1) {
node = node.getRight();
System.out.println(node);
}
node = node.getRight();
}
}
}
如果是理解了第一种方案，再看大佬写的方案二的话就很容易可以看懂，这里就写一下对这个算法的看法。
- 首先我认为，这两种算法都是用的一个内核，也就是一个思想，只是在小操作上不同
- 虽然我也看不出在实际应用中那个更胜，但是就我浅显的来看我更喜欢第二种，这样写看似少写了两个循环但是在循环次数上应该和第一种差不多，因为它把第一种的3个循环集成在了一个上，每一句代码都利用到了极致，真的是写的精彩。
前序线索化二叉树的遍历
public void threadedListBefore() {
// 定义一个变量，存储当前遍历的节点，从root开始
HeroNode node = root;
while (node != null) {
while (node.getLeftType() == 0) {
System.out.println(node);
node = node.getLeft();
}
System.out.println(node);
node = node.getRight();
}
}
后序线索化二叉树的遍历
首先后序的遍历要比中序和前序复杂的多，看很多大佬都说没有必要研究这个，但是还是忍不住好奇研究了一下，确实对比前两者要难很多。
代码是引用的yushiwh大佬的文章中的代码
首先需要在节点类中加入一个父节点的指向，并在遍历前这个父节点的指向要实现完成。
// 父节点 后序线索化遍历时使用
private HeroNode parent;
实现代码
// 后序线索化二叉树遍历
public void threadedListAfter() {
//1、找后序遍历方式开始的节点
HeroNode node = root;
while ( node != null && node.getLeftType() == 0 ) {
node = node.getLeft();
}
while ( node != null ) {
//右节点是线索
if (node.getRightType() == 1) {
System.out.println(node);
pre = node;
node = node.getRight();
} else {
//如果上个处理的节点是当前节点的右节点
if (node.getRight() == pre) {
System.out.println(node);
if (node == root) {
return;
}
pre = node;
node = node.getParent();
} else {
//如果从左节点的进入则找到有子树的最左节点
node = node.getRight();
while ( node != null && node.getLeftType() == 0 ) {
node = node.getLeft();
}
}
}
}
}
注意在测试代码前要将parent属性真正的指向才可以
BinaryTree binaryTree = new BinaryTree();
binaryTree.setRoot(root);
binaryTree.postThreadedNodes(root);
node1.setParent(root);
node2.setParent(root);
node3.setParent(node1);
node4.setParent(node1);
node5.setParent(node2);
binaryTree.threadedListAfter();
Q.E.D.