树
约 14024 字大约 47 分钟
二叉树的存储方式
- 二叉树链式存储方式就用指针， 顺序存储的方式就是用数组。
- 顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。
- 顺序存储就是用数组来存储二叉树，用数组来存储二叉树如何遍历的呢？
- 如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。父 = floor((子 - 1) / 2)
递归什么时候需要返回值
需要返回值
目标是计算某个值：如果递归的目的是通过多个子问题的解来计算一个整体的解（例如计算斐波那契数列、树的最大深度等），递归函数通常需要返回值，以将子问题的结果逐层传递回去。
查找并返回结果：如果递归的目的是查找某个值或路径并返回（例如在树中查找某个节点是否存在），那么递归函数通常需要返回值，以便在找到结果时立即返回，并终止进一步的递归。
路径汇总：在某些情况下，你需要汇总来自子树或子问题的多个结果，并将其返回给上一层。例如，计算树中所有路径和等于某个值的路径数量。
不需要返回值
目标是修改全局状态：如果递归的目的是修改某些全局状态，或直接对某些数据结构进行操作，而不需要从子问题中获取结果，那么递归函数通常不需要返回值。例如，在遍历过程中填充某个列表、集合、或字典。
只做处理，不需要结果：如果递归的目的是执行某些操作，但这些操作的结果不需要传递回调用者，那么就不需要返回值。例如，前序遍历、中序遍历、后序遍历时，只需要访问每个节点并执行一些操作即可。
二叉树遍历及其相关题目√
深度优先遍历（Depth-first order）先往深走，遇到叶子节点再往回走。前中后序指的就是中间节点的位置
- 前序遍历: 先输出父节点，再遍历左子树和右子树（递归法√，迭代法）中左右
- 中序遍历: 先遍历左子树，再输出父节点，再遍历右子树（递归法√，迭代法）左中右
- 后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点（递归法√，迭代法）左右中
广度优先BFS遍历（Breadth-first order）：一层一层的去遍历。
- 层次遍历（迭代法√）队列先进先出
//递归实现前中后序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);//前序遍历
preorder(root.left, result);
//result.add(root.val);//中序遍历
preorder(root.right, result);
//result.add(root.val);//后序遍历
}
}
//层序遍历，本身加入队列，然后遍历队列依次取出并把左右节点加入队列，直到队列为null
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();
int currentLevelSize = queue.size();
for (int i = 1; i <= currentLevelSize; ++i) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
ret.add(level);
}
return ret;
}
- 107二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）最后把result数组反转一下就可以了,也可以使用linkedlist的addFirst
List<List<Integer>> result = new ArrayList<>();
for (int i = list.size() - 1; i >= 0; i-- ) {
result.add(list.get(i));
}
- 637二叉树的层平均值->for循环里面求和就行
- 429N叉树的层序遍历->left和right入队列改为for循环遍历子节点即可
- 515在每个树行中找最大值->for循环里面求和就行
- 116填充每个节点的下一个右侧节点指针
- 117填充每个节点的下一个右侧节点指针II
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
// 二叉树之层次遍历
class Solution {
public Node connect(Node root) {
Queue<Node> queue = new LinkedList<>();
if (root != null) {
queue.add(root);
}
while (!queue.isEmpty()) {
int size = queue.size();
Node node = null;
Node nodePre = null;
for (int i = 0; i < size; i++) {
if (i == 0) {
nodePre = queue.poll(); // 取出本层头一个节点
node = nodePre;
} else {
node = queue.poll();
nodePre.next = node; // 本层前一个节点 next 指向当前节点
nodePre = nodePre.next;
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
nodePre.next = null; // 本层最后一个节点 next 指向 null
}
return root;
}
}
t114二叉树展开为链表√
提示 给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
preorderTraversal(root, list);
int size = list.size();
for (int i = 1; i < size; i++) {
TreeNode prev = list.get(i - 1), curr = list.get(i);
prev.left = null;
prev.right = curr;
}
}
public void preorderTraversal(TreeNode root, List<TreeNode> list) {
if (root != null) {
list.add(root);
preorderTraversal(root.left, list);
preorderTraversal(root.right, list);
}
}
}
t199二叉树的右视图/树左下角的值√
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
//广度优先
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result =new ArrayList<Integer>();
if(root==null){
return result;
}
LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
int n=queue.size();
for(int i=0;i<n;i++){
TreeNode temp=queue.poll();
if(temp.left!=null){
queue.add(temp.left);
}
if(temp.right!=null){
queue.add(temp.right);
}
if(i==n-1){
result.add(temp.val);
}
//if (i == 0) result = temp.val;//左下角的值
}
}
return result;
}
}
t104二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
可以使用前序（中左右）/后序遍历（左右中），前序求深度，后序求高度。
深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
而根节点的高度就是二叉树的最大深度，可通过后序求的根节点高度来求的二叉树最大深度。
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
111二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
使用后序遍历求根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离也是最小深度。
注意，没有左孩子的分支会不算为最短深度
所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。
最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (root.left == null) {
return rightDepth + 1;
}
if (root.right == null) {
return leftDepth + 1;
}
// 左右结点都不为null
return Math.min(leftDepth, rightDepth) + 1;
}
}
222求完全二叉树节点个数
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
t543求二叉树的直径
直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
int ans;
public int diameterOfBinaryTree(TreeNode root) {
ans = 1;//怎么样都会有一个节点
depth(root);//求经过的节点数
return ans - 1;//-1为边数
}
public int depth(TreeNode node) {
if (node == null) {
return 0; // 访问到空节点了，返回0
}
int L = depth(node.left); // 左儿子为根的子树的深度
int R = depth(node.right); // 右儿子为根的子树的深度
ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ans
return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
}
t266翻转二叉树
- 左右子树对调
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
invertTree(root.left);
invertTree(root.right);
swapChildren(root);
return root;
}
private void swapChildren(TreeNode root) {
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
}
t101对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
public boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}
t105从前序与中序遍历序列构造二叉树（或者中后序）
给定两个整数数组preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
时间复杂度O(n)，n是树中的节点个数。
空间复杂度O(n)，除去返回的答案需要的O(n)空间之外，使用O(n)存储哈希映射，
O(h)（h是树的高度）的空间表示递归时栈空间。这里 h<n，所以总空间复杂度为 O(n)。
前序遍历第一个节点就是根节点
中序遍历root左边是左子树，右边是右子树
public class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTreeHelper(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1);
}
private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
// 如果没有元素了，返回 null
if (preStart > preEnd || inStart > inEnd) {
return null;
}
// 前序遍历的第一个元素是根节点
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
// 在中序遍历中找到根节点的位置
int inRootIndex = inStart;
while (inorder[inRootIndex] != rootVal) {
inRootIndex++;
}
// 计算左子树的大小
int leftTreeSize = inRootIndex - inStart;
// 递归构造左子树
root.left = buildTreeHelper(preorder, preStart + 1, preStart + leftTreeSize,
inorder, inStart, inRootIndex - 1);
// 递归构造右子树
root.right = buildTreeHelper(preorder, preStart + leftTreeSize + 1, preEnd,
inorder, inRootIndex + 1, inEnd);
return root;
}
}
654最大二叉树
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructMaximumBinaryTree1(nums, 0, nums.length);
}
public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
if (rightIndex - leftIndex < 1) {// 没有元素了
return null;
}
if (rightIndex - leftIndex == 1) {// 只有一个元素
return new TreeNode(nums[leftIndex]);
}
int maxIndex = leftIndex;// 最大值所在位置
int maxVal = nums[maxIndex];// 最大值
for (int i = leftIndex + 1; i < rightIndex; i++) {
if (nums[i] > maxVal){
maxVal = nums[i];
maxIndex = i;
}
}
TreeNode root = new TreeNode(maxVal);
// 根据maxIndex划分左右子树
root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
return root;
}
}
617合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
注意: 合并必须从两个树的根节点开始。
class Solution {
// 递归
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
root1.val += root2.val;
root1.left = mergeTrees(root1.left,root2.left);
root1.right = mergeTrees(root1.right,root2.right);
return root1;
}
}
112路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和 sum = 22，
class solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
// 减去当前节点的值
targetSum -= root.val;
// 如果是叶子节点且当前路径和等于 targetSum，返回 true
if (root.left == null && root.right == null) {
return targetSum == 0;
}
// 递归检查左子树或右子树
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
}
}
113路径总和2
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和 sum = 22，
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
List<Integer> path = new LinkedList<>();
dfs(root, targetSum, res, path);
return res;
}
private void dfs(TreeNode root, int targetSum,
List<List<Integer>> res, List<Integer> path) {
path.add(root.val);
// 判断是否为叶子节点且路径和等于 targetSum
if (root.left == null && root.right == null && targetSum == root.val) {
res.add(new ArrayList<>(path));
} else {
// 递归调用左右子树
if (root.left != null) {
dfs(root.left, targetSum - root.val, res, path);
}
if (root.right != null) {
dfs(root.right, targetSum - root.val, res, path);
}
}
// 回溯，移除当前节点
path.remove(path.size() - 1);
}
}
t437路径总和3
给定一个二叉树的根节点 root 和整数targetSum ，求节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
//时间复杂度：O(N)，其中 N 为二叉树中节点的个数。利用前缀和只需遍历一次二叉树即可。
//空间复杂度：O(N)。
前缀和
class Solution {
public int pathSum(TreeNode root, int targetSum) {
// 使用 Long 来处理大数问题
Map<Long, Integer> prefix = new HashMap<>();
prefix.put(0L, 1); // 初始化前缀和为 0 的情况
return dfs(root, prefix, 0L, targetSum);
}
private int dfs(TreeNode node, Map<Long, Integer> prefix, long currSum, int targetSum) {
if (node == null) {
return 0;
}
currSum += node.val;
// 计算符合条件的路径数量
int count = prefix.getOrDefault(currSum - targetSum, 0);
// 更新当前前缀和的出现次数
prefix.put(currSum, prefix.getOrDefault(currSum, 0) + 1);
// 递归遍历左右子树并累加结果
count += dfs(node.left, prefix, currSum, targetSum);
count += dfs(node.right, prefix, currSum, targetSum);
// 回溯：减去当前节点的贡献
prefix.put(currSum, prefix.get(currSum) - 1);
return count;
}
}
t124二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
时间复杂度：O(N)，其中 N 是二叉树中的节点个数。对每个节点访问不超过 2 次。
空间复杂度：O(N)，其中 N 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，
最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
public int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 0 时，才会选取对应子节点
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
int priceNewpath = node.val + leftGain + rightGain;
// 更新答案
maxSum = Math.max(maxSum, priceNewpath);
// 返回节点的最大贡献值
return node.val + Math.max(leftGain, rightGain);
}
}
257二叉树的所有路径
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
//方式一
class Solution {
/**
* 递归法
*/
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>(); // 存储最终的结果
if (root != null) {
traversal(root, "", res);
}
return res;
}
private void traversal(TreeNode root, String path, List<String> res) {
// 当前节点值添加到路径中
path += root.val;
// 如果是叶子节点，直接将路径添加到结果中
if (root.left == null && root.right == null) {
res.add(path);
return;
}
// 如果不是叶子节点，继续递归遍历子节点
if (root.left != null) {
traversal(root.left, path + "->", res);
}
if (root.right != null) {
traversal(root.right, path + "->", res);
}
}
}
404左叶子之和
计算给定二叉树的所有左叶子之和。左叶子的明确定义：节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
int leftValue = sumOfLeftLeaves(root.left); // 左
int rightValue = sumOfLeftLeaves(root.right); // 右
int midValue = 0;
if (root.left != null && root.left.left == null && root.left.right == null) {
midValue = root.left.val;
}
int sum = midValue + leftValue + rightValue; // 中
return sum;
}
}
t236二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，
从 p 和 q 节点往上跳经过的祖先节点个数不会超过 N，因此总的时间复杂度为 O(N)。
空间复杂度：O(N) ，其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，
二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)，
哈希表存储每个节点的父节点也需要 O(N) 的空间复杂度，因此最后总的空间复杂度为 O(N)。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 递归基例：如果 root 为空，或者 root 是 p 或 q，则返回 root
if (root == null || root == p || root == q) {
return root;
}
// 递归查找左子树和右子树
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 如果在左子树和右子树分别找到 p 和 q，则 root 就是最近公共祖先
if (left != null && right != null) {
return root;
}
// 如果在其中一个子树找到最近公共祖先，返回该子树的结果
return left != null ? left : right;
}
}
平衡二叉树AVL树及其实现
AVL树解决了BST树退化成链表导致查询最坏复杂度变为O(n)的问题
平衡因子：AVL树中每个节点的左右子树高度差的绝对值不超过1。这个高度差称为平衡因子（Balance Factor），其取值可以是-1, 0, 或1。插入、查找、删除的复杂度都为O(log n)
失衡
LL
- 失衡节点（图中 8 红色）的 bf > 1，即左边更高
- 失衡节点的左孩子（图中 6）的 bf >= 0 即左孩子这边也是左边更高或等高
LR
- 失衡节点（图中 8）的 bf > 1，即左边更高
- 失衡节点的左孩子（图中 6 红色）的 bf < 0 即左孩子这边是右边更高
对称的还有两种情况
RL
- 失衡节点（图中 3）的 bf <-1，即右边更高
- 失衡节点的右孩子（图中 6 红色）的 bf > 0，即右孩子这边左边更高
RR
- 失衡节点（图中 3）的 bf <-1，即右边更高
- 失衡节点的右孩子（图中 6 红色）的 bf <= 0，即右孩子这边右边更高或等高
/**
* This file contains an implementation of an AVL tree. An AVL tree is a special type of binary tree
* which self balances itself to keep operations logarithmic.
*
* @author William Fiset, william.alexandre.fiset@gmail.com
*/
public class AVLTreeRecursive<T extends Comparable<T>> implements Iterable<T> {
public class Node implements PrintableNode {
// 'bf' is short for Balance Factor
public int bf;
// The value/data contained within the node.
public T value;
// The height of this node in the tree.
public int height;
// The left and the right children of this node.
public Node left, right;
public Node(T value) {
this.value = value;
}
@Override
public PrintableNode getLeft() {
return left;
}
@Override
public PrintableNode getRight() {
return right;
}
@Override
public String getText() {
return value.toString();
}
}
// The root node of the AVL tree.
public Node root;
// Tracks the number of nodes inside the tree.
private int nodeCount = 0;
// The height of a rooted tree is the number of edges between the tree's
// root and its furthest leaf. This means that a tree containing a single
// node has a height of 0.
public int height() {
if (root == null) return 0;
return root.height;
}
// Returns the number of nodes in the tree.
public int size() {
return nodeCount;
}
// Returns whether or not the tree is empty.
public boolean isEmpty() {
return size() == 0;
}
// Return true/false depending on whether a value exists in the tree.
public boolean contains(T value) {
return contains(root, value);
}
// Recursive contains helper method.
private boolean contains(Node node, T value) {
if (node == null) return false;
// Compare current value to the value in the node.
int cmp = value.compareTo(node.value);
// Dig into left subtree.
if (cmp < 0) return contains(node.left, value);
// Dig into right subtree.
if (cmp > 0) return contains(node.right, value);
// Found value in tree.
return true;
}
// Insert/add a value to the AVL tree. The value must not be null, O(log(n))
public boolean insert(T value) {
if (value == null) return false;
if (!contains(root, value)) {
root = insert(root, value);
nodeCount++;
return true;
}
return false;
}
// Inserts a value inside the AVL tree.
private Node insert(Node node, T value) {
// Base case.
if (node == null) return new Node(value);
// Compare current value to the value in the node.
int cmp = value.compareTo(node.value);
// Insert node in left subtree.
if (cmp < 0) {
node.left = insert(node.left, value);
;
// Insert node in right subtree.
} else {
node.right = insert(node.right, value);
}
// Update balance factor and height values.
update(node);
// Re-balance tree.
return balance(node);
}
// Update a node's height and balance factor.
private void update(Node node) {
int leftNodeHeight = (node.left == null) ? -1 : node.left.height;
int rightNodeHeight = (node.right == null) ? -1 : node.right.height;
// Update this node's height.
node.height = 1 + Math.max(leftNodeHeight, rightNodeHeight);
// Update balance factor.
node.bf = rightNodeHeight - leftNodeHeight;
}
// Re-balance a node if its balance factor is +2 or -2.
private Node balance(Node node) {
// Left heavy subtree.
if (node.bf == -2) {
// Left-Left case.
if (node.left.bf <= 0) {
return leftLeftCase(node);
// Left-Right case.
} else {
return leftRightCase(node);
}
// Right heavy subtree needs balancing.
} else if (node.bf == +2) {
// Right-Right case.
if (node.right.bf >= 0) {
return rightRightCase(node);
// Right-Left case.
} else {
return rightLeftCase(node);
}
}
// Node either has a balance factor of 0, +1 or -1 which is fine.
return node;
}
private Node leftLeftCase(Node node) {
return rightRotation(node);
}
private Node leftRightCase(Node node) {
node.left = leftRotation(node.left);
return leftLeftCase(node);
}
private Node rightRightCase(Node node) {
return leftRotation(node);
}
private Node rightLeftCase(Node node) {
node.right = rightRotation(node.right);
return rightRightCase(node);
}
private Node leftRotation(Node node) {
Node newParent = node.right;
node.right = newParent.left;//失衡节点的右节点变为失衡节点的右节点的左节点
newParent.left = node;//失衡节点变为失衡节点的右节点的左节点
update(node);
update(newParent);
return newParent;
}
private Node rightRotation(Node node) {
Node newParent = node.left;
node.left = newParent.right;
newParent.right = node;
update(node);
update(newParent);
return newParent;
}
// Remove a value from this binary tree if it exists, O(log(n))
public boolean remove(T elem) {
if (elem == null) return false;
if (contains(root, elem)) {
root = remove(root, elem);
nodeCount--;
return true;
}
return false;
}
// Removes a value from the AVL tree.
private Node remove(Node node, T elem) {
if (node == null) return null;
int cmp = elem.compareTo(node.value);
// Dig into left subtree, the value we're looking
// for is smaller than the current value.
if (cmp < 0) {
node.left = remove(node.left, elem);
// Dig into right subtree, the value we're looking
// for is greater than the current value.
} else if (cmp > 0) {
node.right = remove(node.right, elem);
// Found the node we wish to remove.
} else {
// This is the case with only a right subtree or no subtree at all.
// In this situation just swap the node we wish to remove
// with its right child.
if (node.left == null) {
return node.right;
// This is the case with only a left subtree or
// no subtree at all. In this situation just
// swap the node we wish to remove with its left child.
} else if (node.right == null) {
return node.left;
// When removing a node from a binary tree with two links the
// successor of the node being removed can either be the largest
// value in the left subtree or the smallest value in the right
// subtree. As a heuristic, I will remove from the subtree with
// the greatest hieght in hopes that this may help with balancing.
} else {
// Choose to remove from left subtree
if (node.left.height > node.right.height) {
// Swap the value of the successor into the node.
T successorValue = findMax(node.left);
node.value = successorValue;
// Find the largest node in the left subtree.
node.left = remove(node.left, successorValue);
} else {
// Swap the value of the successor into the node.
T successorValue = findMin(node.right);
node.value = successorValue;
// Go into the right subtree and remove the leftmost node we
// found and swapped data with. This prevents us from having
// two nodes in our tree with the same value.
node.right = remove(node.right, successorValue);
}
}
}
// Update balance factor and height values.
update(node);
// Re-balance tree.
return balance(node);
}
// Helper method to find the leftmost node (which has the smallest value)
private T findMin(Node node) {
while (node.left != null) node = node.left;
return node.value;
}
// Helper method to find the rightmost node (which has the largest value)
private T findMax(Node node) {
while (node.right != null) node = node.right;
return node.value;
}
// Returns as iterator to traverse the tree in order.
public java.util.Iterator<T> iterator() {
final int expectedNodeCount = nodeCount;
final java.util.Stack<Node> stack = new java.util.Stack<>();
stack.push(root);
return new java.util.Iterator<T>() {
Node trav = root;
@Override
public boolean hasNext() {
if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();
return root != null && !stack.isEmpty();
}
@Override
public T next() {
if (expectedNodeCount != nodeCount) throw new java.util.ConcurrentModificationException();
while (trav != null && trav.left != null) {
stack.push(trav.left);
trav = trav.left;
}
Node node = stack.pop();
if (node.right != null) {
stack.push(node.right);
trav = node.right;
}
return node.value;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
@Override
public String toString() {
return TreePrinter.getTreeDisplay(root);
}
// Make sure all left child nodes are smaller in value than their parent and
// make sure all right child nodes are greater in value than their parent.
// (Used only for testing)
public boolean validateBSTInvarient(Node node) {
if (node == null) return true;
T val = node.value;
boolean isValid = true;
if (node.left != null) isValid = isValid && node.left.value.compareTo(val) < 0;
if (node.right != null) isValid = isValid && node.right.value.compareTo(val) > 0;
return isValid && validateBSTInvarient(node.left) && validateBSTInvarient(node.right);
}
}
顺序存储二叉树->堆排序
- 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组
- 顺序二叉树通常只考虑完全二叉树,n为索引，从0开始
- 第n个元素的左子节点为 2 * n + 1
- 第n个元素的右子节点为 2 * n + 2
- 第n个元素的父节点为 (n-1) / 2
class ArrBinaryTree {
private int[] arr;//存储数据结点的数组
public ArrBinaryTree(int[] arr) {
this.arr = arr;
}
public void preOrder() {
this.preOrder(0);
}
public void preOrder(int index) {//index 数组的下标 前序遍历
if(index < arr.length){
//前序遍历 System.out.println(arr[index]); 1,2,4,5,3,6,7
preOrder(2 * index + 1 );//向左递归遍历
//中序遍历 System.out.println(arr[index]);
preOrder(2 * index + 2);//向右递归遍历
//后序遍历 System.out.println(arr[index]);
}
}
}
霍夫曼树
- 给定n个权值作为n个叶子结点，构造的带权路径长度(wpl)达到最小的二叉树，称为为最优二叉树或霍夫曼树(Huffman Tree), 带权路径长度最短的树，权值较大的结点离根较近。
- 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1
- 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积
- 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weighted path length),权值越大的结点离根结点越近的二叉树才是最优二叉树。
- WPL最小的就是赫夫曼树
- 构成赫夫曼树的步骤：
- 1.从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
- 2.取出根节点权值最小的两颗二叉树
- 3.组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
- 4.再将这颗新的二叉树，以根节点的权值大小再次排序， 不断重复1-2-3-4的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
/**
* @param arr 需要创建成哈夫曼树的数组
* @return 创建好后的赫夫曼树的root结点
*/
public static Node createHuffmanTree(int[] arr) {
List<Node> nodes = new ArrayList<Node>();
for (int value : arr) {
nodes.add(new Node(value));
}
while(nodes.size() > 1) {
//排序 从小到大
Collections.sort(nodes);
//取出根节点权值最小的两颗二叉树
//(1) 取出权值最小的结点（二叉树）
Node leftNode = nodes.get(0);
//(2) 取出权值第二小的结点（二叉树）
Node rightNode = nodes.get(1);
//(3)构建一颗新的二叉树
Node parent = new Node(leftNode.value + rightNode.value);
parent.left = leftNode;
parent.right = rightNode;
//(4)从ArrayList删除处理过的二叉树
nodes.remove(leftNode);
nodes.remove(rightNode);
//(5)将parent加入到nodes
nodes.add(parent);
}
//返回哈夫曼树的root结点
return nodes.get(0);
}
霍夫曼编码
- 赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法
- 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
- 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间
- 赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码
- 通信领域中信息的处理方式
定长编码
i like like like java do you like a java // 共40个字符(包括空格)
105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118
97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97 //对应Ascii码
01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100
01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101
00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111
00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011
01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 //对应的二进制
按照二进制来传递信息，总的长度是 359 (包括空格)
在线转码 工具 ：https://www.mokuge.com/tool/asciito16/
变长编码
i like like like java do you like a java // 共40个字符(包括空格)
d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d
说明：按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小，比如 空格出现了9 次， 编码为0 ,其它依次类推.
按照上面给各个字符规定的编码，则我们在传输 "i like like like java do you like a java" 数据时，编码就是 10010110100...
字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码， 即不能匹配到重复的编码
赫夫曼编码
i like like like java do you like a java // 共40个字符(包括空格)
d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值.
public class HuffmanCode {
public static void main(String[] args) {
//测试压缩文件
// String srcFile = "d://Uninstall.xml";
// String dstFile = "d://Uninstall.zip";
//
// zipFile(srcFile, dstFile);
// System.out.println("压缩文件ok~~");
//测试解压文件
String zipFile = "d://Uninstall.zip";
String dstFile = "d://Uninstall2.xml";
unZipFile(zipFile, dstFile);
System.out.println("解压成功!");
/*
String content = "i like like like java do you like a java";
byte[] contentBytes = content.getBytes();
System.out.println(contentBytes.length); //40
byte[] huffmanCodesBytes= huffmanZip(contentBytes);
System.out.println("压缩后的结果是:" + Arrays.toString(huffmanCodesBytes) + " 长度= " + huffmanCodesBytes.length);
//测试一把byteToBitString方法
//System.out.println(byteToBitString((byte)1));
byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);
System.out.println("原来的字符串=" + new String(sourceBytes)); // "i like like like java do you like a java"
*/
//如何将 数据进行解压(解码)
//分步过程
/*
List<Node> nodes = getNodes(contentBytes);
System.out.println("nodes=" + nodes);
//测试一把，创建的赫夫曼树
System.out.println("赫夫曼树");
Node huffmanTreeRoot = createHuffmanTree(nodes);
System.out.println("前序遍历");
huffmanTreeRoot.preOrder();
//测试一把是否生成了对应的赫夫曼编码
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
System.out.println("~生成的赫夫曼编码表= " + huffmanCodes);
//测试
byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes));//17
//发送huffmanCodeBytes 数组 */
}
//编写一个方法，完成对压缩文件的解压
/**
*
* @param zipFile 准备解压的文件
* @param dstFile 将文件解压到哪个路径
*/
public static void unZipFile(String zipFile, String dstFile) {
//定义文件输入流
InputStream is = null;
//定义一个对象输入流
ObjectInputStream ois = null;
//定义文件的输出流
OutputStream os = null;
try {
//创建文件输入流
is = new FileInputStream(zipFile);
//创建一个和 is关联的对象输入流
ois = new ObjectInputStream(is);
//读取byte数组 huffmanBytes
byte[] huffmanBytes = (byte[])ois.readObject();
//读取赫夫曼编码表
Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
//解码
byte[] bytes = decode(huffmanCodes, huffmanBytes);
//将bytes 数组写入到目标文件
os = new FileOutputStream(dstFile);
//写数据到 dstFile 文件
os.write(bytes);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
} finally {
try {
os.close();
ois.close();
is.close();
} catch (Exception e2) {
// TODO: handle exception
System.out.println(e2.getMessage());
}
}
}
//编写方法，将一个文件进行压缩
/**
*
* @param srcFile 你传入的希望压缩的文件的全路径
* @param dstFile 我们压缩后将压缩文件放到哪个目录
*/
public static void zipFile(String srcFile, String dstFile) {
//创建输出流
OutputStream os = null;
ObjectOutputStream oos = null;
//创建文件的输入流
FileInputStream is = null;
try {
//创建文件的输入流
is = new FileInputStream(srcFile);
//创建一个和源文件大小一样的byte[]
byte[] b = new byte[is.available()];
//读取文件
is.read(b);
//直接对源文件压缩
byte[] huffmanBytes = huffmanZip(b);
//创建文件的输出流, 存放压缩文件
os = new FileOutputStream(dstFile);
//创建一个和文件输出流关联的ObjectOutputStream
oos = new ObjectOutputStream(os);
//把 赫夫曼编码后的字节数组写入压缩文件
oos.writeObject(huffmanBytes); //我们是把
//这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用
//注意一定要把赫夫曼编码 写入压缩文件
oos.writeObject(huffmanCodes);
}catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}finally {
try {
is.close();
oos.close();
os.close();
}catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
}
}
//完成数据的解压
//思路
//1. 将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
// 重写先转成 赫夫曼编码对应的二进制的字符串 "1010100010111..."
//2. 赫夫曼编码对应的二进制的字符串 "1010100010111..." =》 对照 赫夫曼编码 =》 "i like like like java do you like a java"
//编写一个方法，完成对压缩数据的解码
/**
*
* @param huffmanCodes 赫夫曼编码表 map
* @param huffmanBytes 赫夫曼编码得到的字节数组
* @return 就是原来的字符串对应的数组
*/
private static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes) {
//1. 先得到 huffmanBytes 对应的 二进制的字符串 ， 形式 1010100010111...
StringBuilder stringBuilder = new StringBuilder();
//将byte数组转成二进制的字符串
for(int i = 0; i < huffmanBytes.length; i++) {
byte b = huffmanBytes[i];
//判断是不是最后一个字节
boolean flag = (i == huffmanBytes.length - 1);
stringBuilder.append(byteToBitString(!flag, b));
}
//把字符串安装指定的赫夫曼编码进行解码
//把赫夫曼编码表进行调换，因为反向查询 a->100 100->a
Map<String, Byte> map = new HashMap<String,Byte>();
for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
//创建要给集合，存放byte
List<Byte> list = new ArrayList<>();
//i 可以理解成就是索引,扫描 stringBuilder
for(int i = 0; i < stringBuilder.length(); ) {
int count = 1; // 小的计数器
boolean flag = true;
Byte b = null;
while(flag) {
//1010100010111...
//递增的取出 key 1
String key = stringBuilder.substring(i, i+count);//i 不动，让count移动，指定匹配到一个字符
b = map.get(key);
if(b == null) {//说明没有匹配到
count++;
}else {
//匹配到
flag = false;
}
}
list.add(b);
i += count;//i 直接移动到 count
}
//当for循环结束后，我们list中就存放了所有的字符 "i like like like java do you like a java"
//把list 中的数据放入到byte[] 并返回
byte b[] = new byte[list.size()];
for(int i = 0;i < b.length; i++) {
b[i] = list.get(i);
}
return b;
}
/**
* 将一个byte 转成一个二进制的字符串, 如果看不懂，可以参考我讲的Java基础 二进制的原码，反码，补码
* @param b 传入的 byte
* @param flag 标志是否需要补高位如果是true ，表示需要补高位，如果是false表示不补, 如果是最后一个字节，无需补高位
* @return 是该b 对应的二进制的字符串，（注意是按补码返回）
*/
private static String byteToBitString(boolean flag, byte b) {
//使用变量保存 b
int temp = b; //将 b 转成 int
//如果是正数我们还存在补高位
if(flag) {
temp |= 256; //按位与 256 1 0000 0000 | 0000 0001 => 1 0000 0001
}
String str = Integer.toBinaryString(temp); //返回的是temp对应的二进制的补码
if(flag) {
return str.substring(str.length() - 8);
} else {
return str;
}
}
//使用一个方法，将前面的方法封装起来，便于我们的调用.
/**
*
* @param bytes 原始的字符串对应的字节数组
* @return 是经过 赫夫曼编码处理后的字节数组(压缩后的数组)
*/
private static byte[] huffmanZip(byte[] bytes) {
List<Node> nodes = getNodes(bytes);
//根据 nodes 创建的赫夫曼树
Node huffmanTreeRoot = createHuffmanTree(nodes);
//对应的赫夫曼编码(根据 赫夫曼树)
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
//根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
return huffmanCodeBytes;
}
//编写一个方法，将字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte[]
/**
*
* @param bytes 这时原始的字符串对应的 byte[]
* @param huffmanCodes 生成的赫夫曼编码map
* @return 返回赫夫曼编码处理后的 byte[]
* 举例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
* 返回的是 字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
* => 对应的 byte[] huffmanCodeBytes ，即 8位对应一个 byte,放入到 huffmanCodeBytes
* huffmanCodeBytes[0] = 10101000(补码) => byte [推导 10101000=> 10101000 - 1 => 10100111(反码)=> 11011000= -88 ]
* huffmanCodeBytes[1] = -88
*/
private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
//1.利用 huffmanCodes 将 bytes 转成 赫夫曼编码对应的字符串
StringBuilder stringBuilder = new StringBuilder();
//遍历bytes 数组
for(byte b: bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
//System.out.println("测试 stringBuilder~~~=" + stringBuilder.toString());
//将 "1010100010111111110..." 转成 byte[]
//统计返回 byte[] huffmanCodeBytes 长度
//一句话 int len = (stringBuilder.length() + 7) / 8;
int len;
if(stringBuilder.length() % 8 == 0) {
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
//创建 存储压缩后的 byte数组
byte[] huffmanCodeBytes = new byte[len];
int index = 0;//记录是第几个byte
for (int i = 0; i < stringBuilder.length(); i += 8) { //因为是每8位对应一个byte,所以步长 +8
String strByte;
if(i+8 > stringBuilder.length()) {//不够8位
strByte = stringBuilder.substring(i);
}else{
strByte = stringBuilder.substring(i, i + 8);
}
//将strByte 转成一个byte,放入到 huffmanCodeBytes
huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
//生成赫夫曼树对应的赫夫曼编码
//思路:
//1. 将赫夫曼编码表存放在 Map<Byte,String> 形式
// 生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();
//2. 在生成赫夫曼编码表示，需要去拼接路径, 定义一个StringBuilder 存储某个叶子结点的路径
static StringBuilder stringBuilder = new StringBuilder();
//为了调用方便，我们重载 getCodes
private static Map<Byte, String> getCodes(Node root) {
if(root == null) {
return null;
}
//处理root的左子树
getCodes(root.left, "0", stringBuilder);
//处理root的右子树
getCodes(root.right, "1", stringBuilder);
return huffmanCodes;
}
/**
* 功能：将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入到huffmanCodes集合
* @param node 传入结点
* @param code 路径： 左子结点是 0, 右子结点 1
* @param stringBuilder 用于拼接路径
*/
private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
//将code 加入到 stringBuilder2
stringBuilder2.append(code);
if(node != null) { //如果node == null不处理
//判断当前node 是叶子结点还是非叶子结点
if(node.data == null) { //非叶子结点
//递归处理
//向左递归
getCodes(node.left, "0", stringBuilder2);
//向右递归
getCodes(node.right, "1", stringBuilder2);
} else { //说明是一个叶子结点
//就表示找到某个叶子结点的最后
huffmanCodes.put(node.data, stringBuilder2.toString());
}
}
}
//前序遍历的方法
private static void preOrder(Node root) {
if(root != null) {
root.preOrder();
}else {
System.out.println("赫夫曼树为空");
}
}
/**
*
* @param bytes 接收字节数组
* @return 返回的就是 List 形式 [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],
*/
private static List<Node> getNodes(byte[] bytes) {
//1创建一个ArrayList
ArrayList<Node> nodes = new ArrayList<Node>();
//遍历 bytes , 统计 每一个byte出现的次数->map[key,value]
Map<Byte, Integer> counts = new HashMap<>();
for (byte b : bytes) {
Integer count = counts.get(b);
if (count == null) { // Map还没有这个字符数据,第一次
counts.put(b, 1);
} else {
counts.put(b, count + 1);
}
}
//把每一个键值对转成一个Node 对象，并加入到nodes集合
//遍历map
for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
//可以通过List 创建对应的赫夫曼树
private static Node createHuffmanTree(List<Node> nodes) {
while(nodes.size() > 1) {
//排序, 从小到大
Collections.sort(nodes);
//取出第一颗最小的二叉树
Node leftNode = nodes.get(0);
//取出第二颗最小的二叉树
Node rightNode = nodes.get(1);
//创建一颗新的二叉树,它的根节点 没有data, 只有权值
Node parent = new Node(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
//将已经处理的两颗二叉树从nodes删除
nodes.remove(leftNode);
nodes.remove(rightNode);
//将新的二叉树，加入到nodes
nodes.add(parent);
}
//nodes 最后的结点，就是赫夫曼树的根结点
return nodes.get(0);
}
}
//创建Node ,待数据和权值
class Node implements Comparable<Node> {
Byte data; // 存放数据(字符)本身，比如'a' => 97 ' ' => 32
int weight; //权值, 表示字符出现的次数
Node left;//
Node right;
public Node(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
// 从小到大排序
return this.weight - o.weight;
}
public String toString() {
return "Node [data = " + data + " weight=" + weight + "]";
}
//前序遍历
public void preOrder() {
System.out.println(this);
if(this.left != null) {
this.left.preOrder();
}
if(this.right != null) {
this.right.preOrder();
}
}
}
class BinarySortTree {
private Node root;
public Node getRoot() {return root;}
public Node search(int value) {
if(root == null) {
return null;
} else {
return root.search(value);
}
}
public Node searchParent(int value) {
if(root == null) {
return null;
} else {
return root.searchParent(value);
}
}
//返回以node 为根结点的二叉排序树的最小结点的值并删除该最小节点
/**
* @param node 传入的结点(当做二叉排序树的根结点)
* @return 返回的 以node 为根结点的二叉排序树的最小结点的值
*/
public int delRightTreeMin(Node node) {
Node target = node;
//循环的查找左子节点，就会找到最小值
while(target.left != null) {
target = target.left;
}
//这时 target就指向了最小结点
delNode(target.value);//删除最小结点
return target.value;
}
//删除结点
public void delNode(int value) {
if(root == null) {
return;
}else {
Node targetNode = search(value);
if(targetNode == null) {
return;
}
//当二叉排序树只有一个结点
if(root.left == null && root.right == null) {
root = null;
return;
}
//去找到targetNode的父结点
Node parent = searchParent(value);
//如果要删除的结点是叶子结点
if(targetNode.left == null && targetNode.right == null) {
//判断targetNode 是父结点的左子结点，还是右子结点
if(parent.left != null && parent.left.value == value) { //是左子结点
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {//是由子结点
parent.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) { //删除有两颗子树的节点
int minVal = delRightTreeMin(targetNode.right);
targetNode.value = minVal;
} else { // 删除只有一颗子树的结点
//如果要删除的结点有左子结点
if(targetNode.left != null) {
if(parent != null) {
//如果 targetNode 是 parent 的左子结点
if(parent.left.value == value) {
parent.left = targetNode.left;
} else { // targetNode 是 parent 的右子结点
parent.right = targetNode.left;
}
} else {
root = targetNode.left;
}
} else { //如果要删除的结点有右子结点
if(parent != null) {
//如果 targetNode 是 parent 的左子结点
if(parent.left.value == value) {
parent.left = targetNode.right;
} else { //如果 targetNode 是 parent 的右子结点
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
//添加结点的方法
public void add(Node node) {
if(root == null) {
root = node;//如果root为空则直接让root指向node
} else {
root.add(node);
}
}
//中序遍历
public void infixOrder() {
if(root != null) {
root.infixOrder();
} else {
System.out.println("二叉排序树为空，不能遍历");
}
}
}
class Node {
int value;
Node left;
Node right;
public Node(int value) {this.value = value;}
//toString
public Node search(int value) {
if(value == this.value) { //找到就是该结点
return this;
} else if(value < this.value) {//如果查找的值小于当前结点，向左子树递归查找
//如果左子结点为空
if(this.left == null) {
return null;
}
return this.left.search(value);
} else { //如果查找的值不小于当前结点，向右子树递归查找
if(this.right == null) {
return null;
}
return this.right.search(value);
}
}
//查找要删除结点的父结点
public Node searchParent(int value) {
//如果当前结点就是要删除的结点的父结点，就返回
if((this.left != null && this.left.value == value) ||
(this.right != null && this.right.value == value)) {
return this;
} else {
//如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
if(value < this.value && this.left != null) {
return this.left.searchParent(value); //向左子树递归查找
} else if (value >= this.value && this.right != null) {
return this.right.searchParent(value); //向右子树递归查找
} else {
return null; // 没有找到父结点
}
}
}
//递归的形式添加结点，注意需要满足二叉排序树的要求
public void add(Node node) {
if(node == null) {return;}
if(node.value < this.value) {
if(this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
if(this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
}
//中序遍历
public void infixOrder() {
if(this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if(this.right != null) {
this.right.infixOrder();
}
}
}
class AVLTree {
private Node root;
public Node getRoot() {return root;}
public Node search(int value) {
if (root == null) {
return null;
} else {
return root.search(value);
}
}
public Node searchParent(int value) {
if (root == null) {
return null;
} else {
return root.searchParent(value);
}
}
// 返回的以node为根结点的二叉排序树的最小结点的值并删除该节点
public int delRightTreeMin(Node node) {
Node target = node;
while (target.left != null) {
target = target.left;
}
// 这时 target就指向了最小结点
// 删除最小结点
delNode(target.value);
return target.value;
}
public void delNode(int value) {
if (root == null) {
return;
} else {
// 1.需求先去找到要删除的结点 targetNode
Node targetNode = search(value);
// 如果没有找到要删除的结点
if (targetNode == null) {
return;
}
// 如果我们发现当前这颗二叉排序树只有一个结点
if (root.left == null && root.right == null) {
root = null;
return;
}
// 去找到targetNode的父结点
Node parent = searchParent(value);
// 如果要删除的结点是叶子结点
if (targetNode.left == null && targetNode.right == null) {
// 判断targetNode 是父结点的左子结点，还是右子结点
if (parent.left != null && parent.left.value == value) { // 是左子结点
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {// 是由子结点
parent.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) { // 删除有两颗子树的节点
int minVal = delRightTreeMin(targetNode.right);
targetNode.value = minVal;
} else { // 删除只有一颗子树的结点
// 如果要删除的结点有左子结点
if (targetNode.left != null) {
if (parent != null) {
// 如果 targetNode 是 parent 的左子结点
if (parent.left.value == value) {
parent.left = targetNode.left;
} else { // targetNode 是 parent 的右子结点
parent.right = targetNode.left;
}
} else {
root = targetNode.left;
}
} else { // 如果要删除的结点有右子结点
if (parent != null) {
// 如果 targetNode 是 parent 的左子结点
if (parent.left.value == value) {
parent.left = targetNode.right;
} else { // 如果 targetNode 是 parent 的右子结点
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
// 添加结点的方法
public void add(Node node) {
if (root == null) {
root = node;// 如果root为空则直接让root指向node
} else {
root.add(node);
}
}
// 中序遍历
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("二叉排序树为空，不能遍历");
}
}
}
// 创建Node结点
class Node {
int value;
Node left;
Node right;
public Node(int value) {this.value = value;}
//toString()
// 返回左子树的高度
public int leftHeight() {
if (left == null) {return 0;}
return left.height();
}
// 返回右子树的高度
public int rightHeight() {
if (right == null) {return 0;}
return right.height();
}
// 返回 以该结点为根结点的树的高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
//左旋转方法
private void leftRotate() {
//创建新的结点，以当前根结点的值
Node newNode = new Node(value);
//把新的结点的左子树设置成当前结点的左子树
newNode.left = left;
//把新的结点的右子树设置成带你过去结点的右子树的左子树
newNode.right = right.left;
//把当前结点的值替换成右子结点的值
value = right.value;
//把当前结点的右子树设置成当前结点右子树的右子树
right = right.right;
//把当前结点的左子树(左子结点)设置成新的结点
left = newNode;
}
//右旋转
private void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
// 查找要删除的结点
public Node search(int value) {
if (value == this.value) { // 找到就是该结点
return this;
} else if (value < this.value) {// 如果查找的值小于当前结点，向左子树递归查找
// 如果左子结点为空
if (this.left == null) {
return null;
}
return this.left.search(value);
} else { // 如果查找的值不小于当前结点，向右子树递归查找
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
// 查找要删除结点的父结点
public Node searchParent(int value) {
// 如果当前结点就是要删除的结点的父结点，就返回
if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
return this;
} else {
// 如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
if (value < this.value && this.left != null) {
return this.left.searchParent(value); // 向左子树递归查找
} else if (value >= this.value && this.right != null) {
return this.right.searchParent(value); // 向右子树递归查找
} else {
return null; // 没有找到父结点
}
}
}
// 添加结点的方法
// 递归的形式添加结点，注意需要满足二叉排序树的要求
public void add(Node node) {
if (node == null) {
return;
}
// 判断传入的结点的值，和当前子树的根结点的值关系
if (node.value < this.value) {
// 如果当前结点左子结点为null
if (this.left == null) {
this.left = node;
} else {
// 递归的向左子树添加
this.left.add(node);
}
} else { // 添加的结点的值大于 当前结点的值
if (this.right == null) {
this.right = node;
} else {
// 递归的向右子树添加
this.right.add(node);
}
}
//当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转
if(rightHeight() - leftHeight() > 1) {
//如果它的右子树的左子树的高度大于它的右子树的右子树的高度
if(right != null && right.leftHeight() > right.rightHeight()) {
//先对右子结点进行右旋转
right.rightRotate();
//然后在对当前结点进行左旋转
leftRotate(); //左旋转..
} else {
//直接进行左旋转即可
leftRotate();
}
return ; //必须要!!!
}
//当添加完一个结点后，如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
if(leftHeight() - rightHeight() > 1) {
//如果它的左子树的右子树高度大于它的左子树的高度
if(left != null && left.rightHeight() > left.leftHeight()) {
//先对当前结点的左结点(左子树)->左旋转
left.leftRotate();
//再对当前结点进行右旋转
rightRotate();
} else {
//直接进行右旋转即可
rightRotate();
}
}
}
// 中序遍历
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
}
B树
- 二叉树需要加载到内存的，如果二叉树的节点很多(比如1亿)， 就存在如下问题:
- 在构建二叉树时，需要多次进行i/o操作(海量数据存在数据库或文件中)，节点海量，构建二叉树时，速度有影响
- 节点海量，也会造成二叉树的高度很大，会降低操作速度.
- 多叉树
- 在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树（multiway tree）
- 2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。
- B树
- B树通过重新组织节点，降低树的高度，并且减少i/o读写次数来提升效率。
- 文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(页得大小通常为4k)，这样每个节点只需要一次I/O就可以完全载入
- 将树的度M设置为1024，在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素, B树(B+)广泛应用于文件存储系统以及数据库系统中
- 2-3树(最简单的B树结构)
- 由二节点和三节点构成的树，所有叶子节点都在同一层.(只要是B树都满足这个条件)
- 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点.
- 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点.
- 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面3个条件。
- 三节点的子树的值大小遵守(BST 二叉排序树)的规则，即左子树的值都小于三节点的第一个值，中间子树的值都介于三节点的第一个值和第二个值。右子树的值，都大于三节点的第二个值.
- B树(B-树)的说明:
- B树的阶：节点的最多子节点个数。比如2-3树的阶是3，2-3-4树的阶是4
- B树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点
- 关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据.
- 搜索有可能在非叶子结点结束
- 其搜索性能等价于在关键字全集内做一次二分查找
- B+树
- B+树是B树的变体，也是一种多路搜索树。
- B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找
- 所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据)恰好是有序的。
- 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
- 更适合文件索引系统
- B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然.
- B*树
- B树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。B树分配新结点的概率比B+树要低，空间使用率更高
- B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3，而B+树的块的最低使用率为B+树的1/2。
二叉树深度优先遍历（迭代法）了解
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null){
stack.push(node.right);
}
if (node.left != null){
stack.push(node.left);
}
}
return result;
}
}
// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()){
if (cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
}
// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.left != null){
stack.push(node.left);
}
if (node.right != null){
stack.push(node.right);
}
}
Collections.reverse(result);
return result;
}
}
//同一迭代方法
LinkedList<TreeNode> stack = new LinkedList<>();
TreeNode curr = root; // 代表当前节点
TreeNode pop = null; // 最近一次弹栈的元素
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
colorPrintln("前: " + curr.val, 31);
stack.push(curr); // 压入栈，为了记住回来的路
curr = curr.left;
} else {
TreeNode peek = stack.peek();
// 右子树可以不处理, 对中序来说, 要在右子树处理之前打印
if (peek.right == null) {
colorPrintln("中: " + peek.val, 36);
pop = stack.pop();
colorPrintln("后: " + pop.val, 34);
}
// 右子树处理完成, 对中序来说, 无需打印
else if (peek.right == pop) {
pop = stack.pop();
colorPrintln("后: " + pop.val, 34);
}
// 右子树待处理, 对中序来说, 要在右子树处理之前打印
else {
colorPrintln("中: " + peek.val, 36);
curr = peek.right;
}
}
}
public static void colorPrintln(String origin, int color) {
System.out.printf("\033[%dm%s\033[0m%n", color, origin);
}