01 DSA-- 二叉树

• 二叉树本身是比较简单的基础数据结构，但是很多复杂的数据结构都是基于二叉树的，比如红黑树（二叉搜索树）、多叉树、二叉堆、图、字典树、并查集、线段树等等。把二叉树玩明白了，这些数据结构都不是问题；如果不把二叉树搞明白，这些高级数据结构你也很难驾驭。
• 二叉树不单纯是一种数据结构，更代表着递归的思维方式。一切递归算法，比如 回溯算法、BFS 算法、动态规划 本质上也是把具体问题抽象成树结构，你只要抽象出来了，这些问题最终都回归二叉树的问题。

import java.util.LinkedList;class HashTable<K, V> {private static final int INITIAL_CAPACITY = 16;private LinkedList<Entry<K, V>>[] table;private int size;// 构造函数public HashTable() {table = new LinkedList[INITIAL_CAPACITY];for (int i = 0; i < table.length; i++) {table[i] = new LinkedList<>();}size = 0;}// 内部类，表示哈希表中的条目static class Entry<K, V> {K key;V value;Entry(K key, V value) {this.key = key;this.value = value;}}// 哈希函数private int hash(K key) {return key.hashCode() % table.length;}// 插入键值对public void put(K key, V value) {int index = hash(key);LinkedList<Entry<K, V>> bucket = table[index];// 检查键是否已存在，如果存在则更新值for (Entry<K, V> entry : bucket) {if (entry.key.equals(key)) {entry.value = value;return;}}// 如果键不存在，添加新条目bucket.add(new Entry<>(key, value));size++;}// 根据键查找值public V get(K key) {int index = hash(key);LinkedList<Entry<K, V>> bucket = table[index];for (Entry<K, V> entry : bucket) {if (entry.key.equals(key)) {return entry.value;}}return null; // 如果未找到，返回null}// 根据键删除条目public void remove(K key) {int index = hash(key);LinkedList<Entry<K, V>> bucket = table[index];// 查找并删除条目for (Entry<K, V> entry : bucket) {if (entry.key.equals(key)) {bucket.remove(entry);size--;return;}}}// 获取当前哈希表大小public int size() {return size;}// 检查哈希表是否为空public boolean isEmpty() {return size == 0;}
}public class Main {public static void main(String[] args) {HashTable<String, Integer> hashTable = new HashTable<>();// 插入一些键值对hashTable.put("apple", 1);hashTable.put("banana", 2);hashTable.put("orange", 3);// 查找键System.out.println("Value for 'apple': " + hashTable.get("apple")); // 输出: Value for 'apple': 1// 删除键hashTable.remove("banana");System.out.println("Value for 'banana' after removal: " + hashTable.get("banana")); // 输出: Value for 'banana' after removal: null// 获取哈希表大小System.out.println("Size of hash table: " + hashTable.size()); // 输出: Size of hash table: 2}
}

链法中用来存储每个哈希桶中的元素。
java
复制代码
class HashTable<K, V> {
声明 HashTable 类，它是一个泛型类，使用两个类型参数 K 和 V，分别表示键的类型和值的类型。
java
复制代码
private static final int INITIAL_CAPACITY = 16;
定义一个 INITIAL_CAPACITY 常量，表示哈希表的初始容量。这个值表示哈希表的桶（链表）数组的长度。
java
复制代码
private LinkedList<Entry<K, V>>[] table;
private int size;
定义了两个成员变量：
table 是一个数组，其中的每个元素是一个 LinkedList，用来存储哈希表中的元素。
size 记录哈希表中的元素总数。
java
复制代码
public HashTable() {
table = new LinkedList[INITIAL_CAPACITY];
for (int i = 0; i < table.length; i++) {
table[i] = new LinkedList<>();
}
size = 0;
}
构造函数 HashTable() 初始化哈希表：
创建一个 LinkedList 数组 table，长度为 INITIAL_CAPACITY。
使用一个循环为 table 中的每个桶（链表）分配一个新的 LinkedList 实例。
将 size 初始化为 0，因为刚创建的哈希表为空。
java
复制代码
static class Entry<K, V> {
K key;
V value;

    Entry(K key, V value) {this.key = key;this.value = value;}
}

Entry 类是一个静态嵌套类，用于表示哈希表中的一个键值对。
key 表示键，value 表示与键关联的值。
构造函数 Entry(K key, V value) 初始化 key 和 value。
java
复制代码
private int hash(K key) {
return key.hashCode() % table.length;
}
hash 方法计算哈希值：
调用 key 的 hashCode() 方法计算其哈希值。
使用取模运算 % 将哈希值限制在数组的长度范围内，确保得到一个有效的索引。
java
复制代码
public void put(K key, V value) {
int index = hash(key);
LinkedList<Entry<K, V>> bucket = table[index];
put 方法用于插入一个键值对。
首先调用 hash 方法，计算 key 的哈希值 index，得到在 table 数组中的位置。
获取 table 数组中该位置的 LinkedList，即 bucket。
java
复制代码
for (Entry<K, V> entry : bucket) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
}
遍历 bucket 中的每个元素，检查是否已存在指定 key：
如果找到了相同的 key，更新该 entry 的 value，然后退出方法（不再插入新元素）。
java
复制代码
bucket.add(new Entry<>(key, value));
size++;
}
如果 bucket 中不存在该 key，创建一个新的 Entry 并将其添加到 bucket。
增加 size，表示哈希表中元素的数量增加了一个。
java
复制代码
public V get(K key) {
int index = hash(key);
LinkedList<Entry<K, V>> bucket = table[index];
get 方法用于根据键查找值：
计算 key 的哈希值 index，找到 table 中对应的 bucket。
java
复制代码
for (Entry<K, V> entry : bucket) {
if (entry.key.equals(key)) {
return entry.value;
}
}
return null;
}
遍历 bucket 中的每个 entry，找到与 key 相等的条目并返回其 value。
如果 bucket 中没有该 key，返回 null。
java
复制代码
public void remove(K key) {
int index = hash(key);
LinkedList<Entry<K, V>> bucket = table[index];
remove 方法用于删除键值对。
计算 key 的哈希值 index，找到 table 中对应的 bucket。
java
复制代码
for (Entry<K, V> entry : bucket) {
if (entry.key.equals(key)) {
bucket.remove(entry);
size–;
return;
}
}
}
遍历 bucket 中的每个 entry，找到与 key 相等的条目并将其从 bucket 中移除。
减少 size，表示哈希表中的元素数量减少了一个。
java
复制代码
public int size() {
return size;
}
size 方法返回哈希表中的元素总数。
java
复制代码
public boolean isEmpty() {
return size == 0;
}
isEmpty 方法检查哈希表是否为空，返回一个布尔值。
测试代码
java
复制代码
public class Main {
public static void main(String[] args) {
HashTable<String, Integer> hashTable = new HashTable<>();
创建一个 Main 类的 main 方法，用于测试 HashTable 的功能。
声明一个 HashTable 实例，键类型为 String，值类型为 Integer。
java
复制代码
hashTable.put(“apple”, 1);
hashTable.put(“banana”, 2);
hashTable.put(“orange”, 3);
插入三个键值对。
java
复制代码
System.out.println("Value for ‘apple’: " + hashTable.get(“apple”));
打印 apple 的值。预期输出为 1。
java
复制代码
hashTable.remove(“banana”);
System.out.println("Value for ‘banana’ after removal: " + hashTable.get(“banana”));
删除 banana 后，尝试获取其值，预期输出为 null。
java
复制代码
System.out.println("Size of hash table: " + hashTable.size());
}
}
打印哈希表的大小。