Java编程入门：探索二叉树与哈希表的奥秘

8 0 0

数据结构入门指南

内容导航
数据结构概述
 树形结构解析
 树的基本定义
 树的相关术语
 二叉树详解
 基本概念
 特殊类型二叉树
 二叉树特性
 构建基础二叉树
 二叉树访问方法
 前序访问
 中序访问
 后序访问
 层级访问
 搜索树与平衡树
 二叉搜索树
 AVL平衡树
 红黑树原理
 哈希表实现

树形结构解析

基本定义：

树是一种层次化的非线性数据组织方式， 由若干节点（n≥0）按照层级关系构成。因其形态类似自然界中倒置的树木而得名，具有以下典型特征：
1. 存在唯一的起始节点，称为根节点，该节点没有上级节点
2. 除根节点外，其他节点被划分为M(M>0)个互不重叠的子集T1、T2、…Tm，每个子集Ti(1≤i≤m)本身也是一棵树
节点度数： 某节点拥有的子树数量即为该节点的度；示例图中A节点的度为6
整体度数： 树中所有节点度数的最大值；示例图中树的整体度数为6
叶节点： 度数为0的节点；示例中B、C、H、I等节点属于叶节点
父节点： 包含子节点的节点；示例中A是B的父节点
子节点： 某节点下属子树的根节点；示例中B是A的子节点
层级定义： 从根节点开始计算，根为第1层，其子节点为第2层，依此类推
树的高度： 树中节点的最大层级数；示例中树高为4
补充概念说明：
分支节点： 度数非零的节点；示例中D、E、F、G等属于分支节点
同胞节点： 共享同一父节点的节点；示例中B、C互为同胞节点
同辈节点： 父节点处于同一层级的节点；示例中H、I互为同辈节点
祖先路径： 从根节点到某节点的完整路径上的所有节点；示例中A是所有节点的祖先
后代节点： 以某节点为根的子树中的所有节点；示例中所有节点都是A的后代
多树集合： 由多棵互不关联的树组成的集合称为森林

二叉树详解

基本概念：

二叉树是节点的有限集合，满足以下条件之一：
1. 空集合
2. 由根节点及其左右两棵子树（也是二叉树）组成
重要特性：
– 节点最大度数为2
– 左右子树有严格顺序区分，属于有序树
所有二叉树都由以下基本形态组合而成：
Java编程入门：探索二叉树与哈希表的奥秘

特殊类型：

1. 满二叉树: 各层节点数均达到最大值。即深度为K的满二叉树，节点总数为2^K-1
2. 完全二叉树: 高效的数据结构，其节点排列与同深度的满二叉树编号完全对应。满二叉树是特殊的完全二叉树
Java编程入门：探索二叉树与哈希表的奥秘

重要特性：

1. 设根节点为第1层，则第i层最多有2^(i-1)个节点(i>0)
2. 深度为K的二叉树最多包含2^K-1个节点(k≥0)
3. 叶节点数n0与度为2的节点数n2满足：n0=n2+1
4. n个节点的完全二叉树深度为⌈log₂(n+1)⌉
5. 完全二叉树节点编号规则：
– 父节点编号：(i-1)/2（i>0）
– 左子节点：2i+1（存在时）
– 右子节点：2i+2（存在时）

基础构建示例：

public class BinaryTreeDemo {
public static void main(String[] args) {
TreeNode root = new TreeNode<>('A');
TreeNode b = new TreeNode<>('B');
TreeNode c = new TreeNode<>('C');
TreeNode d = new TreeNode<>('D');
TreeNode e = new TreeNode<>('E');
root.setLeft(b);
root.setRight(c);
b.setLeft(d);
b.setRight(e);
System.out.println(root.getLeft().getLeft().getValue());
}
static class TreeNode<T> {
private T value;
private TreeNode<T> left, right;
public TreeNode(T value) {
this.value = value;
}
// 省略getter/setter方法
}
}
// 输出：D

二叉树访问方法

遍历是指按照特定顺序访问树中每个节点一次的操作，是二叉树其他操作的基础。
Java编程入门：探索二叉树与哈希表的奥秘

前序遍历：

访问根节点
前序遍历左子树
前序遍历右子树

public void preOrderTraversal(TreeNode root) {
if(root == null) return;
System.out.print(root.value + " ");
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
// 示例输出：A B D E H C F G

中序遍历：

中序遍历左子树
访问当前节点
中序遍历右子树

public void inOrderTraversal(TreeNode root) {
if(root == null) return;
inOrderTraversal(root.left);
System.out.print(root.value + " ");
inOrderTraversal(root.right);
}
// 示例输出：D B H E A F C G

后序遍历：

后序遍历左子树
后序遍历右子树
访问当前节点

public void postOrderTraversal(TreeNode root) {
if(root == null) return;
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.print(root.value + " ");
}
// 示例输出：D H E B F G C A

层级遍历：

使用队列实现：
1. 根节点入队
2. 循环执行：
– 出队并访问节点
– 将左右子节点入队

public void levelOrderTraversal(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.value + " ");
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
}
// 示例输出：A B C D E F G H

搜索树与平衡树

二叉搜索树：

又称二叉排序树，特性：
1. 左子树所有节点值小于根节点值
2. 右子树所有节点值大于根节点值
3. 所有子树也是二叉搜索树

AVL平衡树：

为避免树结构退化为链表，引入平衡概念：
1. 首先是二叉搜索树
2. 任意节点的左右子树高度差不超过1
3. 通过平衡因子（左高-右高）判断平衡状态
调整策略：
1. LL型：右旋
2. RR型：左旋
3. RL型：先右后左
4. LR型：先左后右

红黑树原理

红黑树是自平衡二叉搜索树的实现，节点着色规则：
1. 节点为红色或黑色
2. 根节点必为黑色
3. 红色节点的父子节点不能同为红色
4. 空节点视为黑色叶节点
5. 任意路径黑色节点数相同

哈希表实现

哈希表通过散列函数建立键值与存储位置的映射关系，实现高效查找。
核心特性：
– 相同输入永远产生相同哈希值
– 不同输入尽可能产生不同哈希值
– 常见哈希函数：MD5、SHA-1等
基础实现示例：

public class SimpleHashTable {
private static final int SIZE = 10;
private Object[] table = new Object[SIZE];
public void add(E item) {
int index = hash(item);
table[index] = item;
}
public boolean contains(E item) {
int index = hash(item);
return item.equals(table[index]);
}
private int hash(E item) {
return Math.abs(item.hashCode()) % SIZE;
}
}

哈希冲突处理：
常见解决方案是链地址法，将冲突元素组织成链表：

public class ChainedHashTable {
private static final int SIZE = 10;
private LinkedList<E>[] table;
public ChainedHashTable() {
table = new LinkedList[SIZE];
// 初始化各链表
}
public void insert(E item) {
int index = hash(item);
table[index].addFirst(item);
}
// 其他方法实现...
}

哈希表在理想情况下提供O(1)时间复杂度的查找效率，是高效的数据存储结构。

# 未分类