目录
一.为什么需要树
1)数组存储方式的分析
优点:通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
缺点:如果要检素具体某个值，或者插入值(按一定顺序)会整体移动，效率较低
2)链式存储方式的分析
优点:在一定程度上对数组存储方式有优化(比如:插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好)。
缺点:在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)
3)树存储方式的分析
能提高数据存储，读取的效率,比如利用二叉排序树(Binary Sort Tree),数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。
案例:[7.3.10.1.5.9.12]
二.二叉树的概念和基本术语
1.树的示意图和概念
树的常用术语(结合示意图理解):1)节点 2)根节点 3)父节点 4)子节点
5)叶子节点(没有子节点的节点) 6)节点的权(节点值)
7)路径(从root节点找到该节点的路线) 8)层
9)子树 10)树的高度(最大层数) 11)森林:多颗子树构成森林
2.二叉树
1)树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树
2)二叉树的子节点分为左节点和右节点。
满二叉树
3)如果该二叉树的所有叶子节点都在最后一层，并且结点总数=2^n-1, n为层数，则我们称为满二叉树。
4)如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。
T1是满二叉树,T2因为C的没有左结点,而存在右结点,不连续了,所以不是满二叉树,T3因为D结点不存在子结点
满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树
三.二叉树的遍历
1.前中后序遍历
使用前序，中序和后序对下面的二叉树进行遍历.
前序遍历:先输出父节点，再遍历左子树和右子树
中序遍历:先遍历左子树，再输出父节点，再遍历右子树
后序遍历:先遍历左子树，再遍历右子树，最后输出父节点
小结:看输出父节点的顺序，就确定是前序，中序还是后序
分析二叉树的前序，中序，后序的遍历步骤
1.创建一颗二叉树
2.前序遍历
2.1先输出当前节点(初始的时候是root节点)2.2如果左子节点不为空,则递归继续前序遍历
2.3如果右子节点不为空，则递归继卖前序遍历
3.中序遍历
3.1如果当前节点的左子节点不为空,则递归中序遍历,3.2输出当前节点
3.3如果当前节点的右子节点不为空，则递归中序遍历4.后序遍历
4.1如果当前节点的左子节点不为空,则递归后序遍历4.2如果当前节点的右子节点不为空,则递归后序遍历
4.3输出当前节点
2.代码实现
public class BinaryTreeDemo {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
DataTree treeNode1 = new DataTree(1);
DataTree treeNode2 = new DataTree(2);
DataTree treeNode3 = new DataTree(3);
DataTree treeNode4 = new DataTree(4);
DataTree treeNode5 = new DataTree(5);
DataTree treeNode6 = new DataTree(6);
//先手动创建二叉树,之后学习递归创建二叉树
treeNode1.setLeft(treeNode2);
treeNode1.setRight(treeNode3);
treeNode2.setLeft(treeNode4);
treeNode2.setRight(treeNode5);
treeNode3.setLeft(treeNode6);
tree.setRoot(treeNode1);
System.out.println("前序遍历结果为:");
tree.preOrder(tree.getRoot()); //1,2,4,5,3,6
System.out.println("-------------------------------------");
System.out.println("中序遍历结果为:");
tree.infixOrder(tree.getRoot());//4,2,5,1,6,3
System.out.println("-------------------------------------");
System.out.println("后序遍历结果为:");
tree.postOrder(tree.getRoot());//4,5,2,6,3,1
}
}
//定义一个二叉树
class BinaryTree {
private DataTree root;
public void setRoot(DataTree root) {
this.root = root;
}
public DataTree getRoot() {
return root;
}
//前序遍历
public void preOrder(DataTree tree) {
if (tree == null)
return;
System.out.println(tree);
//遍历左子树
preOrder(tree.getLeft());
//遍历右子树
preOrder(tree.getRight());
}
//中序遍历
public void infixOrder(DataTree tree) {
if (tree == null)
return;
//遍历左子树
infixOrder(tree.getLeft());
//打印
System.out.println(tree);
//遍历右子树
infixOrder(tree.getRight());
}
//后序遍历
public void postOrder(DataTree tree) {
if (tree == null)
return;
//遍历左子树
postOrder(tree.getLeft());
//遍历右子树
postOrder(tree.getRight());
//打印
System.out.println(tree);
}
}
//先创建结点
class DataTree {
private int num;
private DataTree left;
private DataTree right;
public void setNum(int num) {
this.num = num;
}
public int getNum() {
return num;
}
public DataTree getLeft() {
return left;
}
public void setLeft(DataTree left) {
this.left = left;
}
public DataTree getRight() {
return right;
}
public void setRight(DataTree right) {
this.right = right;
}
public DataTree(int num) {
this.num = num;
}
@Override
public String toString() {
return "DataTree{" +
"num=" + num +
'}';
}
}输出结果:
前序遍历结果为:
DataTree{num=1}
DataTree{num=2}
DataTree{num=4}
DataTree{num=5}
DataTree{num=3}
DataTree{num=6}
-------------------------------------
中序遍历结果为:
DataTree{num=4}
DataTree{num=2}
DataTree{num=5}
DataTree{num=1}
DataTree{num=6}
DataTree{num=3}
-------------------------------------
后序遍历结果为:
DataTree{num=4}
DataTree{num=5}
DataTree{num=2}
DataTree{num=6}
DataTree{num=3}
DataTree{num=1}
四.二叉树的查找
1.前中后序查找
前序查找
1.先判断当前结点的no是否等于要查找的
2.如果是相等，则返回当前结点
3.如果不等，则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找4.如果左递归前序查找，找到结点，则返回，否继续判断，当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
中序查找
1.判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
2.如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点,否则继续进行右递归的中序查找
3.如果右递归中序查找，找到就返回，否则返回null后序查找
1.判断当前结点的左子节点是否为空，如果不为空，则递归
2.如果找到，就返回，如果没有找到，就判断当前结点的右子节点是否为空，如果不为空，则右递归进行后序查找,如果找到，就返回
3.就和当前结点进行，比如，如果是则返回，否则返回null
2.代码实现
//前序查找
public DataTree preSearch(DataTree tree, int num) {
if (tree.getNum() == num) {
return tree;
}
DataTree result = null;
//判断当前节点的左子树是否为空,不为空则前序查找
if (tree.getLeft() != null)
result = preSearch(tree.getLeft(), num);
if (result != null)//说明在左子树
return result;
//判断当前节点的左子树是否为空,不为空则前序查找
if (tree.getRight() != null)
result = preSearch(tree.getRight(), num);
return result;
}
//中序查找
public DataTree infixSearch(DataTree tree, int num) {
DataTree result = null;
//判断当前节点的左子树是否为空,不为空则中序查找
if (tree.getLeft() != null)
result = infixSearch(tree.getLeft(), num);
if (result != null)//说明在左子树
return result;
if (tree.getNum() == num) {
return tree;
}
//判断当前节点的左子树是否为空,不为空则中序查找
if (tree.getRight() != null)
result = infixSearch(tree.getRight(), num);
return result;
}
//后序查找
public DataTree postSearch(DataTree tree, int num) {
DataTree result = null;
//判断当前结点的左子树是否为空,不为空则递归后序查找
if (tree.getLeft() != null)
result = postSearch(tree.getLeft(), num);
if (result != null)//说明在左子树
return result;
if (tree.getRight() != null)
result = postSearch(tree.getRight(), num);
if (result != null)//说明在右子树
return result;
if (tree.getNum() == num) {
return tree;
}
return result;
}结果测试:
System.out.println("前序查找的结果:");
DataTree dataTree = tree.preSearch(tree.getRoot(), 5);
System.out.println(dataTree);
System.out.println("中序查找的结果:");
DataTree dataTree1 = tree.infixSearch(tree.getRoot(), 2);
System.out.println(dataTree1);
System.out.println("后序查找的结果:");
DataTree dataTree2 = tree.postSearch(tree.getRoot(), 10);
System.out.println(dataTree2);DataTree{num=1}
前序查找的结果:
DataTree{num=5}
中序查找的结果:
DataTree{num=2}
后序查找的结果:
null
五.二叉树的删除结点
1.思路分析
二叉树-删除节点要求
1)如果删除的节点是叶子节点，则删除该节点
2)如果删除的节点是非叶子节点，则删除该子树.
3)测试，删除掉5号叶子节点和3号子树.
思路:
1.因为我们的三叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点.
2.如果当前结点的左子结点不为空，并且左子结点就是要册除结点，就将this.left =null;并且就返回(结束递归删除).
3.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null;并且就返回(结束递归删除).
4.如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
5．如果第4步也没有删除结点，则应当向右子树进行递归删除.
6.考虑如果树是空树root，如果只有一个root结点，则等价将二叉树置空
2.代码实现
1.无返回值删除
//删除指定结点
public void deleteNode(DataTree tree, int num){
if(root==null)
return;
if(root.getNum()==num)
root=null;
if(tree.getLeft()!=null&&tree.getLeft().getNum()==num){
tree.setLeft(null);
return;
}
if(tree.getRight()!=null&&tree.getRight().getNum()==num){
tree.setRight(null);
return;
}
if(tree.getLeft()!=null){
deleteNode(tree.getLeft(),num);
}
if(tree.getRight()!=null){
deleteNode(tree.getRight(),num);
}
}
此种方法就算在左子树找到删除的结点了,依然回去右子树查找
打印结果:
tree.deleteNode(tree.getRoot(),2); tree.preOrder(tree.getRoot());打印结果:
DataTree{num=1}
DataTree{num=3}
DataTree{num=6}
3.有返回值删除
判断是否删除结点成功,如果树的结点中含有,找到并删除成功返回true,否则找不到没有删除返回false.
//删除指定结点
public boolean deleteNode(DataTree tree, int num){
if(root==null)
return false;
if(root.getNum()==num){
root=null;
return true;
}
if(tree.getLeft()!=null&&tree.getLeft().getNum()==num){
tree.setLeft(null);
return true;
}
if(tree.getRight()!=null&&tree.getRight().getNum()==num){
tree.setRight(null);
return true;
}
boolean flag=false;
if(tree.getLeft()!=null){
flag = deleteNode(tree.getLeft(), num);
}
if(flag==true){
return flag;
}
if(tree.getRight()!=null){
flag = deleteNode(tree.getRight(),num);
}
return flag;
}
此种方法就算在左子树找到删除的结点了,直接返回true,不会去右子树查找了
打印结果:
System.out.println(tree.deleteNode(tree.getRoot(), 10)); tree.preOrder(tree.getRoot());结果:
false
DataTree{num=1}
DataTree{num=2}
DataTree{num=4}
DataTree{num=5}
DataTree{num=3}
DataTree{num=6}
或者:
System.out.println(tree.deleteNode(tree.getRoot(), 3)); tree.preOrder(tree.getRoot());结果:
true
DataTree{num=1}
DataTree{num=2}
DataTree{num=4}
DataTree{num=5}
六.顺序存储二叉树
1.顺序存储二叉树的概念
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，看右面的示意图。
1)上图的二叉树的结点，要求以数组的方式来存放arr : [1,2,3,4,5,6,6]
2)要求在遍历数组arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历
2.顺序存储二叉树的特点:
1)顺序二叉树通常只考虑完全二叉树
2)如果第n个元素存在左子节点,则其左子节点为2*n+ 1
3)如果第n个元素存在右子节点,则其右子节点为2*n+2
4)如果第n个元素存在父节点,则其父节点为(n-1)/2
5) n:表示二叉树中的第几个元素(按0开始编号,如图所示)
3.代码实现
public class ArrBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
System.out.println("顺序存储二叉树的前序遍历:");
arrBinaryTree.preOrder();
System.out.println("顺序存储二叉树的中序遍历:");
arrBinaryTree.infixOrder();
System.out.println("顺序存储二叉树的后序遍历:");
arrBinaryTree.postOrder();
}
}
//编写一个ArrBinaryTree,实现顺序存储二叉树遍历
class ArrBinaryTree {
private int[] arr;
public ArrBinaryTree(int[] arr) {
this.arr = arr;
}
//重载preOrder方法
public void preOrder() {
preOrder(0);
}
//编写一个方法,完成顺序存储二叉树的前序遍历
/**
* @param index 表示数组的下标
*/
public void preOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("数组为空,不能按照二叉树前序遍历");
}
//输出当前的结点
System.out.println(arr[index]);
//向左递归遍历
if (2 * index + 1 < arr.length) {
preOrder(2 * index + 1);
}
//向右递归遍历
if (2 * index + 2 < arr.length) {
preOrder(2 * index + 2);
}
}
//中序
public void infixOrder() {
infixOrder(0);
}
public void infixOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("数组为空,不能按照二叉树前序遍历");
}
//向左递归遍历
if (2 * index + 1 < arr.length) {
infixOrder(2 * index + 1);
}
//输出当前的结点
System.out.println(arr[index]);
//向右递归遍历
if (2 * index + 2 < arr.length) {
infixOrder(2 * index + 2);
}
}
//后序
public void postOrder() {
postOrder(0);
}
public void postOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("数组为空,不能按照二叉树前序遍历");
}
//向左递归遍历
if (2 * index + 1 < arr.length) {
postOrder(2 * index + 1);
}
//向右递归遍历
if (2 * index + 2 < arr.length) {
postOrder(2 * index + 2);
}
//输出当前的结点
System.out.println(arr[index]);
}
}打印结果:
顺序存储二叉树的前序遍历:
1
2
4
5
3
6
7
顺序存储二叉树的中序遍历:
4
2
5
1
6
3
7
顺序存储二叉树的后序遍历:
4
5
2
6
7
3
1
七.线索化二叉树
1.问题引出
将数列{1,3,6,8,10,14 }构建成一颗二叉树.
问题分析:
1)当我们对上面的二叉树进行中序遍历时，数列为{8,3,10,1,14,6}
2)但是6,8,10,14这几个节点的左右指针，并没有完全的利用上.
3)如果我们希望充分的利用各个节点的左右指针，让各个节点可以指向自己的前后节点怎么办
4)解决方案线索二叉树
2.线索二叉树的基本介绍
1) n个结点的二叉链表中含有n+1【公式2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索")
2)这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
3)一个结点的前一个结点，称为前驱结点
4)一个结点的后一个结点，称为后继结点
3.线索化二叉树思路分析
说明:当线索化二叉树后，Node节点的属性left和right，有如下情况:
1)left指向的是左子树，也可能是指回的前驱结点，比如①结点left指向的左子树，而⑩结点指向的就是前驱节点.
2) right指向的是右子树，也可能是指向后继节点，比如①节点right指向的是右子树，而⑩节点的
right指向的是后继节点.
4.代码实现
public class ThreadedBinaryTreeDemo {
public static void main(String[] args) {
NumNode root = new NumNode(1);
NumNode numNode2 = new NumNode(3);
NumNode numNode3 = new NumNode(6);
NumNode numNode4 = new NumNode(8);
NumNode numNode5 = new NumNode(10);
NumNode numNode6 = new NumNode(14);
//二叉树,后面我们要递归创建,现在简单处理使用手动创建
root.setLeft(numNode2);
root.setRight(numNode3);
numNode2.setLeft(numNode4);
numNode2.setRight(numNode5);
numNode3.setLeft(numNode6);
ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
threadedBinaryTree.setRoot(root);
//测试线索化
threadedBinaryTree.threadedNode();
//以10号结点做测试
System.out.println(numNode5.getLeft());
System.out.println(numNode5.getRight());
}
}
//定义ThreadedBinaryTree实现了线索化功能的二叉树
class ThreadedBinaryTree {
private NumNode root;
//为了实现线索化,需要创建要给指向当前结点的前驱结点的指针
//在递归进行线索化的时候,pre总是保留前一个结点
private NumNode pre;
public void setRoot(NumNode root) {
this.root = root;
}
//编写对二叉树进行中序线索化的方法
public void threadedNode() {
threadedNode(root);
}
public void threadedNode(NumNode node) {
//如果Node==null,就不能线索化,退出
if (node == null)
return;
//先线索化左子树
threadedNode(node.getLeft());
//线索化当前结点
//处理当前结点的前驱节点
if (node.getLeft() == null) {
node.setLeft(pre);
//修改当前结点左指针的类型
node.setLeftType(1);
}
//处理后继节点
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
//每处理一个结点后，让当前结点是下一个结点的前驱结点
pre = node;
//线索化右子树
threadedNode(node.getRight());
}
}
//先创建结点
class NumNode {
private int num;
private NumNode left;
private NumNode right;
//1.如果leftType==0表示指向的是左子树,如果是1则表示指向的是前驱节点
//2.如果rightType==0表示指向的是右子树,如果是1则表示指向的是后继节点
private int leftType;
private int rightType;
public int getLeftType() {
return leftType;
}
public void setLeftType(int leftType) {
this.leftType = leftType;
}
public int getRightType() {
return rightType;
}
public void setRightType(int rightType) {
this.rightType = rightType;
}
public void setNum(int num) {
this.num = num;
}
public int getNum() {
return num;
}
public NumNode getLeft() {
return left;
}
public void setLeft(NumNode left) {
this.left = left;
}
public NumNode getRight() {
return right;
}
public void setRight(NumNode right) {
this.right = right;
}
public NumNode(int num) {
this.num = num;
}
@Override
public String toString() {
return "NumNode{" +
"num=" + num +
'}';
}
}
打印结果:
NumNode{num=3}
NumNode{num=1}
5.遍历线索化二叉树
说明:对前面的中序线索化的二叉树，进行遍历
分析:因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致。
//遍历线索化二叉树的方法
public void threadList() {
NumNode 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();
}
}测试:
//线索化遍历二叉树
threadedBinaryTree.threadList();
打印结果:
NumNode{num=8}
NumNode{num=3}
NumNode{num=10}
NumNode{num=1}
NumNode{num=14}
NumNode{num=6}
八.赫夫曼树
1.基本介绍
1）给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(HuffmanTree),还有的书翻译为霍夫曼树。
2)赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
2.几个概念
1)路径和路径长度:在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1.
2)结点的权及带权路径长度:若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积
3)树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和，记
为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
4)WPL最小的就是赫夫曼树
3.思路图解
赫夫曼树创建思路图解
给你一个数列{13,7,8,3,29,6,1}，要求转成一颗赫夫曼树.
构成赫夫曼树的步骤:
1)从小到大进行排序,将每一个数据，每个数据都是一个节点，每个节点可以看成是
一颗最简单的二叉树
2)取出根节点权值最小的两颗二叉树
3)组成─颗新的二叉树,该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
4)再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复1-2-3-4的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
{13,7,8,3,29,6,1} 排序后:{1,3,6,7,8,13,29}
----1
-----2
-------3
-----4
----5
4.代码实现
public class HuffmanTreeDemo {
public static void main(String[] args) {
int[] arr={13,7,8,3,29,6,1};
Node node = huffmanTree(arr);
node.preOrder();
}
//创建哈夫曼树的方法
public static Node huffmanTree(int[] arr){
//1.遍历arr数组
//2.将arr的每个元素构成成一个Node
//3.将Node放入到ArrayList中
ArrayList<Node> nodes = new ArrayList<>();
for (int value : arr) {
nodes.add(new Node(value));
}
while (nodes.size()!=1){
Collections.sort(nodes);
//取出根节点权值最小的两颗二叉树
Node left = nodes.get(0);
Node right = nodes.get(1);
//创建一个新的二叉树
Node parent = new Node(left.value + right.value);
parent.left=left;
parent.right=right;
//移除处理过的二叉树,加入处理后的二叉树
nodes.remove(left);
nodes.remove(right);
nodes.add(parent);
}
return nodes.get(0);
}
}
//创建结点类
class Node implements Comparable<Node>{
int value; //结点权值
Node left; //左节点
Node right; //右节点
public Node(int value){
this.value=value;
}
public void preOrder(){
System.out.println(this);
if(this.left!=null){
this.left.preOrder();
}
if(this.right!=null){
this.right.preOrder();
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
@Override
public int compareTo(Node o) {
//表示从小到大进行排序
return this.value-o.value;
}
}
打印结果:
Node{value=67}
Node{value=29}
Node{value=38}
Node{value=15}
Node{value=7}
Node{value=8}
Node{value=23}
Node{value=10}
Node{value=4}
Node{value=1}
Node{value=3}
Node{value=6}
Node{value=13}
九.赫夫曼编码
1.基本介绍
1)赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，属于一种程序算法
2)赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之
3)赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%90%之间
4)赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，
称之为最佳编码
2.原理剖析
通信领域中信息的处理方式1-定长编码
i like like like java do you like a java //共40个字符(包括空格)
105 32 108 105 107 10132 108 105 107 10132 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 97118 97//对应Ascii码
01101001 00100000 01101100 01101001 01101011 0110010100100000 01101100
01101001 01101011 01100101 00100000 01101100 01101001011010110110010100100000 0110101 00110 00010 11101100110 00010010000001100100 01101111 00100000 01111 0010110 1111011101010010 0000 011011000110 10010110 1011
01100101001000 0001100001 0010000 0 0110101001100001011101100 1100001//对应的二进制
按照二进制来传递信息，总的长度是359(包括空格)
通信领域中信息的处理方式2-变长编码
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,其它依次类推.
按照上面给各个字符规定的编码，则我们在传输"ilike like like java do you like a java"数据时，编码就是10010110100...
字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码，即不能匹配到重复的编码
通信领域中信息的处理方式3-赫夫曼编码
共40个字符(包括空格)
i like like like java do you like a java
d:1 y:1 u:1 j:2 v2 o:2 l:4 k:4 e:4 i:5 a:5 空格:9 //各个字符对应的个数按照上面字符出现的次数构建一颗赫夫曼树,次数作为权值.
4)根据赫夫曼树，给各个字符,规定编码，向左的路径为o向右的路径为1，编码如下:
o: 1000 u: 10010 d: 100110 y: 100111 i: 101 a: 110 k: 1110 e:1111 j: 0000 v: 0001
i: 001 空格:01
5)按照上面的赫夫曼编码，我们的"i like like like java do you like a java”字符串对应的编码为(注意这里我们使用的无损压缩）
101010011011110111101001101111011110100110111101111010000110000111001100111100001100111100010010010011011110111011100100001100001110
长度为133
说明:
1)原来长度是359，压缩了(359-133)/ 359=62.9%此编码满足前缀编码，即字符的编码都不能是其
他字符编码的前缀。不会造成匹配的多义性
注意,这个赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是wpl是一样的，都是最小的,比如:如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树为:
3.赫夫曼的数据压缩
功能:根据赫夫曼编码压缩数据的原理，需要创建"i like like like java do you like a java"对应的赫夫曼树
思路:
(1) Node { data (存放数据)，weight(权值) left 和right }
//创建结点类
class Node implements Comparable<Node>{
int value; //结点权值
Node left; //左节点
Node right; //右节点
public Node(int value){
this.value=value;
}
public void preOrder(){
System.out.println(this);
if(this.left!=null){
this.left.preOrder();
}
if(this.right!=null){
this.right.preOrder();
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
@Override
public int compareTo(Node o) {
//表示从小到大进行排序
return this.value-o.value;
}
}
(2)得到"i like like like java do you like a java”对应的 byte[]数组
String s="i like like like java do you like a java";
byte[] bytes = s.getBytes();
System.out.println(bytes.length);//40
(3)编写一个万法,将准备构建赫夫曼树的Node结点放到List,形式[Node[date=97 weight = 5], Node[date=32,weight = 9]....], 体现d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9
public static List<Node> getNodes(byte[] bytes){
ArrayList<Node> nodes = new ArrayList<>();
//遍历bytes ,统计每一个byte出现的次数->map[key,value]
HashMap<Byte, Integer> map = new HashMap<>();
for (byte aByte : bytes) {
Integer count = map.get(aByte);
if(count==null){
map.put(aByte,1);
}
else
map.put(aByte,count+1);
}
//把每一个键值对转换为Node,并存放在node集合中
//遍历map
for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
Node node = new Node(entry.getKey(), entry.getValue());
nodes.add(node);
}
return nodes;
}
(4)可以通过List创建对应的赫夫曼树
//通过list创建对应的哈夫曼树
public static Node createHuffmanTree(List<Node> nodes){
while(nodes.size()!=1){
Collections.sort(nodes);
Node left = nodes.get(0);
Node right = nodes.get(1);
Node parent = new Node(left.weight + right.weight);
parent.left=left;
parent.right=right;
//不能简单的写remove(0),remove(1),因为当remove(0)的时候,仅剩一个角标为0
nodes.remove(left);
nodes.remove(right);
nodes.add(parent);
}
return nodes.get(0);
}测试
public static void main(String[] args) {
String s="i like like like java do you like a java";
byte[] bytes = s.getBytes();
System.out.println(bytes.length);//40
List<Node> nodes = getNodes(bytes);
Node huffmanTree = createHuffmanTree(nodes);
huffmanTree.preOrder();
}
Node{data=null, weight=40}
Node{data=null, weight=17}
Node{data=null, weight=8}
Node{data=108, weight=4}
Node{data=null, weight=4}
Node{data=106, weight=2}
Node{data=111, weight=2}
Node{data=32, weight=9}
Node{data=null, weight=23}
Node{data=null, weight=10}
Node{data=97, weight=5}
Node{data=105, weight=5}
Node{data=null, weight=13}
Node{data=null, weight=5}
Node{data=null, weight=2}
Node{data=100, weight=1}
Node{data=117, weight=1}
Node{data=null, weight=3}
Node{data=121, weight=1}
Node{data=118, weight=2}
Node{data=null, weight=8}
Node{data=101, weight=4}
Node{data=107, weight=4}
我们已经生成了赫夫曼树，下面我们继续完成任务1)生成赫夫曼树对应的赫夫曼编码，如下表:
空格=01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
2)使用赫夫曼编码来生成赫夫曼编码数据,即按照上面的赫夫曼编码，将
"i like like like java do you like a java”字符串生成对应的编码数据,形式如:下.1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
(5)生成赫夫曼编码表
public static Map<Byte, String> huffmanCodes = new HashMap<>();
public static StringBuilder builder = new StringBuilder();
public static void getCodes(Node node) {
if(node==null)
return;
getCodes(node,"",builder);
}
//生成哈夫曼树对应的哈夫曼编码表
/**
* 功能:将传入的node结点的所有叶子结点的哈夫曼编码得到,并放入到huffmanCodes集合中
* @param node 传入的根结点
* @param code 路径:左子结点是0,右子结点是1
* @param builder 用于拼接路径
*/
public static void getCodes(Node node, String code, StringBuilder builder) {
StringBuilder stringBuilder = new StringBuilder(builder);
stringBuilder.append(code);
if(node!=null){//当前结点不为空
//判断当前结点是不是叶子结点
if(node.data==null){
//向左递归
getCodes(node.left,"0",stringBuilder);
//向右递归
getCodes(node.right,"1",stringBuilder);
}
else {//当为叶子节点时
//表示找到了某个结点的最后
huffmanCodes.put(node.data,stringBuilder.toString());
}
}
}
测试:
//测试哈夫曼编码
getCodes(huffmanTree);
//生成的huffmanCodes
System.out.println("huffmanCodes:"+huffmanCodes);
huffmanCodes:{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
(6)赫夫曼编码字节数组
//将字符串对应的byte数组,通过生成的哈夫曼编码表,返回哈夫曼编码后的字节数组
public static int zeroCount=0;
/**
* @param huffmanCodes 生成的哈夫曼编码表
* @param bytes 原始字符串对应的byte数组
* @return 返回哈夫曼编码处理后的byte数组
*/
public static byte[] zip(Map<Byte, String> huffmanCodes, byte[] bytes) {
//1.利用huffmanCodes将 bytes转成赫夫曼编码对应的字符串
StringBuilder stringBuilder = new StringBuilder();
for (byte aByte : bytes) {
stringBuilder.append(huffmanCodes.get(aByte));
}
//将stringbuilder里面的内容(1010100010111111110.....)转换为byte数组
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;
for (int i = 0; i < stringBuilder.length(); i += 8) {
String strByte;
if (i + 8 > stringBuilder.length()){
strByte = stringBuilder.substring(i);
// 如果最后一次是00110010、0110等情况，需要记录前面有多少个0
for (int j = 0; j < strByte.length(); j++) {
if (strByte.length() == 1) {
break;
}
if (strByte.charAt(j) == '0') {
zeroCount++;
} else {
break;
}
}
}
else
strByte = stringBuilder.substring(i, i + 8);
huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}测试:
byte[] zip = zip(huffmanCodes, bytes);
System.out.println("zip:"+Arrays.toString(zip));
System.out.println(zip.length);//17打印结果
zip:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
17
赫夫曼字节数组的封装
/**
*
* @param bytes 原始的字节数组
* @return 经过哈夫曼处理后的数组
*/
public static byte[] huffmanZip(byte[] bytes){
//1.统计每个字母出现的次数,并将权重封装到node里面,构建成list集合
List<Node> nodes = getNodes(bytes);
//2.根据node创建赫夫曼树
Node huffmanTree = createHuffmanTree(nodes);
//3.根据哈夫曼树生成对应的哈夫曼编码
Map<Byte, String> huffmanCodes = getCodes(huffmanTree);
//4.根据生成的哈夫曼编码,压缩得到压缩后的赫夫曼编码字节数组
byte[] zip = zip(huffmanCodes, bytes);
return zip;
}4.赫夫曼的数据解压
使用赫夫曼编码来解码数据，具体要求是前面我们得到了赫夫曼编码和对应的编码
即byte[-88,-65,-56,-65,-56,-65,-55,77,57,6,-24,-14,-117,-4,-60,-90,28]
2)现在要求使用赫夫曼编码，进行解码，又重新得到原来的字符串"i like like like
java do you like a java"
将huffmanCodeBytes [-88， -65， -56，-65，-56，-65,-55，77， -57，6，-24，-14，-117， -4,-60，-90，28]重写先转成赫夫曼编码对应的二进制的字符串"1010100010111...
赫夫曼编码对应的二进制的字符串“1010100010111...”=》对照赫夫曼编码=》"i like like like java do you like a java"
(1)将一个byte转换为二进制的字符串
/**
* 将一个byte转换为二进制的字符串
*
* @param flag 标志是否要补高位,如果是true表示要,最后一个子节无需补高位
* @param b 传入的byte
* @return 返回二进制的字符串(补码返回)
*/
public static String byteToStringBit(boolean flag, Byte b) {
int temp = b;
//如果是整数补高位
if (flag)
temp |= 256; // 1 0000 0000 可以自动将前面为补0
String s = Integer.toBinaryString(temp);//返回的是temp对应的二进制补码
if (flag||temp<0){
return s.substring(s.length() - 8);
}
//最后一位前边是否要补0
else{
for (int i = 0; i < zeroCount; i++) {
s = "0" + s;
}
return s;
}
}(2)huffmanCodeBytes [-88，-65 -56,-65,-56,-65,-55,77, -57,6,-24,-14,-117,-4,-60,-90,28]==========>赫夫曼编码对应的二进制的字符串"1010100010111...
然后经过huffmanCodes对比可以找出对应的Byte
//压缩数据解码
/**
*
* @param huffmanCodes 哈夫曼编码表
* @param huffmanBytes 压缩后的byte数组
* @return 原来的字符串对应的数组
*/
public static byte[] decode(Map<Byte, String> huffmanCodes,byte[] huffmanBytes){
//1.先得到 huffmanBytes对应的二进制的字符串，形式1010100010111...
StringBuilder stringBuilder = new StringBuilder();
for(int i=0;i<huffmanBytes.length;i++){
boolean flag=(i!=huffmanBytes.length-1);
stringBuilder.append(byteToStringBit(flag,huffmanBytes[i]));
}
//把字符串按照指定的赫夫曼编码进行解码
//把赫夫曼编码表进行调换,因为反向查询a->100 100->a
HashMap<String, Byte> map = new HashMap<>();
for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
ArrayList<Byte> list = new ArrayList<>();
for(int i=0;i<stringBuilder.length();){
int count=1;
Byte aByte=null;
while(aByte==null){
String substring = stringBuilder.substring(i, i + count);
aByte = map.get(substring);
if(aByte==null){
count++;
}
else {
break;
}
}
list.add(aByte);
i+=count; //i直接移动到count位置
}
//当for循环结束后，我们list中就存放了所有的字符“"i like like like java do you like a java"
//把list中的数据放入到byte[]并返回
byte[] bytes=new byte[list.size()];
for(int i=0;i<list.size();i++){
bytes[i]=list.get(i);
}
return bytes;
}测试:
byte[] decode = decode(huffmanCodes, bytes1);
System.out.println(Arrays.toString(decode));
System.out.println(new String(decode));
[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]
i like like like java do you like a java
5.赫夫曼编码压缩文件
/**
*
* @param srcFile 你传入需要压缩文件的全路径
* @param desFile 压缩文件后的全路径
*/
public static void zipFile(String srcFile,String desFile){
//创建文件输入流
FileInputStream is=null;
//创建文件输出流
FileOutputStream os=null;
//创建文件输出流相关的
ObjectOutputStream oos=null;
try {
//创建文件输入流,取出文件
is = new FileInputStream(srcFile);
byte[] bytes = new byte[is.available()];
is.read(bytes);
//获取文件的哈夫曼编码表
List<Node> nodes = getNodes(bytes);
Node huffmanTree = createHuffmanTree(nodes);
Map<Byte, String> codes = getCodes(huffmanTree);
byte[] huffmanBytes = zip(codes, bytes);
//创建文件输出流,存放文件
os=new FileOutputStream(desFile);
oos=new ObjectOutputStream(os);
//把哈夫曼编码后的字节数组写入
oos.writeObject(huffmanBytes);
//这里我们以对象流的方式写入哈弗曼编码，是为了解压的时候恢复源文件使用
//把哈夫曼编码写入压缩文件,否则不好恢复
oos.writeObject(codes);
} catch (IOException e) {
throw new RuntimeException(e);
} finally {
try {
is.close();
os.close();
oos.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
测试:
String src="C://Users//lenovo//Desktop//picture//ani4.jpg";
String des="C://Users//lenovo//Desktop//picture//zxn.zip";
zipFile(src,des);
System.out.println("压缩文件成功");结果:
6.赫夫曼编码解压文件
//对文件进行解压
/**
* @param zipFile 需要解压的文件
* @param desFile 解压后存放的位置
*/
public static void unZipFile(String zipFile, String desFile) {
//定义文件的输入流
FileInputStream is = null;
//定义对象输入流
ObjectInputStream ois = null;
//定义文件的输出流
FileOutputStream os = null;
try {
//创建文件输入流
is = new FileInputStream(zipFile);
//创建对象输入流
ois = new ObjectInputStream(is);
//读取byte数组 huffmanBytes
byte[] huffmanBytes = (byte[]) ois.readObject();
//读取哈夫曼编码表
Map<Byte, String> code = (Map<Byte, String>) ois.readObject();
//解码
byte[] decode = decode(code, huffmanBytes);
//将解码后的byte数组存入指定位置
os = new FileOutputStream(desFile);
os.write(decode);
} catch (Exception e) {
throw new RuntimeException(e);
} finally {
try {
os.close();
ois.close();
is.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
测试:
String src1="C://Users//lenovo//Desktop//picture//zxn.zip";
String des1="C://Users//lenovo//Desktop//picture//xcl.jpg";
unZipFile(src1,des1);
System.out.println("解压成功");结果:
5.赫夫曼编码压缩注意事项
1)如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化,比如视频,ppt等等文件[举例压一个.ppt]
2)赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件)[举例压一个.xml文件]
3)如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显.
十.二叉排序树(BST)
1.基本介绍
二叉排序树: BST:(Binary Sort(Search) Tree),对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
特别说明:如果有相同的值，可以将该节点放在左子节点或右子节点比如针对前面的数据(7,3,10,12,5,1,9)，对应的二叉排序树为:
2.二叉排序树遍历和添加
一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如:数组为Array(7,3,10,12,5,1,9)，创建成对应的二叉排序树为:
代码实现
class BinarySortTree {
public Node root;
//添加结点
public void add(Node node) {
if (root == null) {
root = node;
return;
}
root.add(node);
}
//中序遍历的方法
public void infixOrder() {
if (root == null) {
System.out.println("二叉排序树为空,不能遍历");
return;
}
root.infixOrder();
}
}
//创建node结点
class Node {
int value;
Node left;
Node right;
//添加结点
public void add(Node node) {
if (node == null)
return;
if (node.value > this.value) {//如果添加的结点大的
if (this.right == null) {//当前结点为叶子结点
this.right = node;
} else {
//递归右子树添加
this.right.add(node);
}
} else {//如果添加的结点小的
if (this.left == null) {//当前结点为叶子结点
this.left = node;
} else {
//递归左子树添加
this.left.add(node);
}
}
}
public void infixOrder() {
if (this.left != null)
this.left.infixOrder();
System.out.println(this);
if (this.right != null)
this.right.infixOrder();
}
public Node() {
}
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}测试:
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr = {7, 3, 10, 12, 5, 1, 9};
BinarySortTree binarySortTree = new BinarySortTree();
for (int i = 0; i < arr.length; i++) {
binarySortTree.add(new Node(arr[i]));
}
binarySortTree.infixOrder();
}
}Node{value=1}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
3.二叉排序树的删除
二叉排序树的删除情况比较复杂，有下面三种情况需要考虑
1)删除叶子节点(比如:2,5,9,12)
(1)需求先去找到要册除的结点targetNode
(2)找到targetNode的父结点parent
(3)确定targetNode是parent的左子结点还是右子结点(4）根据前面的情况来对应删除
左子结点parent.left = null右子结点parent.right = null;
2)删除只有一颗子树的节点(比如:1)
(1)需求先去找到要册除的结点targetNode
(2)找到targetNode的父结点parent
(3)确定targetNode的子结点是左子结点还是右子结点(4) targetNode是parent的左子结点还是右子结点
(5)如果targetNode有左子结点
5.1如果targetNode是parent的左子结点parent.left = targetNode.left;
5.2如果targetNode是parent的右子结点parent.right = targetNode.left;
(6)如果targetNode有右子结点
6.1如果targetNode是parent 的左子结点parent.left = targetNode.right;
6.2如果targetNode是parent 的右子结点parent.right = targetNode.right
3)删除有两颗子树的节点.(比如:7,3,10 )
(1)需求先去找到要册除的结点targetNode
(2)找到targetNode的父结点parent
(3)从targetNode的右子树找到最小的结点(或者去左子树找最大的)
(4)用一个临时变量，将最小结点的值保存temp(5)删除该最小结点
(6)targetNode.value = temp
代码实现
(1)需求先去找到要册除的结点targetNode
(2)找到targetNode的父结点parent
class Node {
int value;
Node left;
Node right;
//查找要删除的结点
public Node search(int value) {
if (this.value == value)
return this;
else if (this.value > value) {//当前结点大于要查找的,去左子树
if (this.left == null)
return null;
this.left.search(value);
} else {//当前结点小于要查找的,去右子树
if (this.right == null)
return null;
this.right.search(value);
}
return null;
}
//查找要删除的父结点
public Node searchParent(int value) {
//如果当前节点为要删除结点的父节点
if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
return this;
}
//查找的值小于当前结点的值,并且当前结点的左子节点不为空
else {
if(this.value>value&&this.left!=null)
this.left.searchParent(value);
else if(this.value<value&&this.right!=null)
this.right.searchParent(value);
else
return null;
}
return null;
}
}lass BinarySortTree {
public Node root;
//查找要删除的结点
public Node search(int value){
if(root==null)
return null;
return root.search(value);
}
//查找要删除的结点的父节点
public Node searchParent(int value){
if(root==null)
return null;
return root.searchParent(value);
}
}1)删除叶子节点(比如:2,5,9,12)
class BinarySortTree {
//删除结点
public void deleteNode(int value) {
if (root == null)
return;
//1.需求先去找到要册除的结点targetNode
Node node = search(value);
if (node == null)
return;
//2.找到targetNode的父结点parent
Node parent = searchParent(value);
//如果要删除的结点是叶子结点
if (node.left == null && node.right == null) {
//如果parent为空,说明要此树仅含有root结点
if (parent == null) {
root=null;
return;
}
//判断node是父节点的左子节点还是右子节点
if (parent.left != null && parent.left == node) {
parent.left = null;
} else if (parent.right != null && parent.right == node) {
parent.right = null;
}
}
}
}测试:
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr = {7, 3, 10, 12, 5, 1, 9,2};
BinarySortTree binarySortTree = new BinarySortTree();
for (int i = 0; i < arr.length; i++) {
binarySortTree.add(new Node(arr[i]));
}
binarySortTree.infixOrder();
binarySortTree.deleteNode(2);
System.out.println("---------------");
binarySortTree.infixOrder();
}
}Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
---------------
Node{value=1}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
2)删除只有一颗子树的节点(比如:1)
//删除结点
public void deleteNode(int value) {
if (root == null)
return;
//1.需求先去找到要册除的结点targetNode
Node node = search(value);
if (node == null)
return;
//2.找到targetNode的父结点parent
Node parent = searchParent(value);
//如果要删除的结点是叶子结点
if (node.left == null && node.right == null) {
//判断node是父节点的左子节点还是右子节点
if (parent.left != null && parent.left == node) {
parent.left = null;
} else if (parent.right != null && parent.right == node) {
parent.right = null;
}
} else if (node.left != null && node.right != null) {
} else {//删除只有一个子树的结点
//如果parent为空,说明要此树要删除的为根结点
if(parent==null){
if(node.left!=null){
root=node.left;
return;
}
else {
root=node.right;
return;
}
}
//如果有左子节点
if (node.left != null) {
//判断node是父节点的左子节点还是右子节点
if (parent.left != null && parent.left == node) {
parent.left = node.left;
} else if (parent.right != null && parent.right == node) {
parent.right = node.left;
}
}
//如果有右子节点
else {
//判断node是父节点的左子节点还是右子节点
if (parent.left != null && parent.left == node) {
parent.left = node.right;
} else if (parent.right != null && parent.right == node) {
parent.right = node.right;
}
}
}
}测试:
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
BinarySortTree binarySortTree = new BinarySortTree();
for (int i = 0; i < arr.length; i++) {
binarySortTree.add(new Node(arr[i]));
}
binarySortTree.infixOrder();
binarySortTree.deleteNode(1);
System.out.println("---------------");
binarySortTree.infixOrder();
}
}结果:
Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
---------------
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
3)删除有两颗子树的节点.(比如:7,3,10 )
//返回以node为根结点的二叉树的最小结点的值
//删除以node为根结点的二叉树的最小结点
public int delRightTreeMin(Node node){
Node target=node;
while(target.left!=null){
target=target.left;
}
deleteNode(target.value);
return target.value;
}
//返回以node为根结点的二叉树的最大结点的值
//删除以node为根结点的二叉树的最大结点
public int delLeftTreeMax(Node node){
Node target=node;
while(target.right!=null){
target=target.right;
}
deleteNode(target.value);
return target.value;
}
//删除结点
public void deleteNode(int value) {
if (root == null)
return;
//1.需求先去找到要册除的结点targetNode
Node node = search(value);
if (node == null)
return;
//2.找到targetNode的父结点parent
Node parent = searchParent(value);
//如果要删除的结点是叶子结点
if (node.left == null && node.right == null) {
//如果parent为空,说明要此树仅含有root结点
if (parent == null) {
root=null;
return;
}
//判断node是父节点的左子节点还是右子节点
if (parent.left != null && parent.left == node) {
parent.left = null;
} else if (parent.right != null && parent.right == node) {
parent.right = null;
}
} else if (node.left != null && node.right != null) {
//int temp= delRightTreeMin(node.left);
// node.value=temp;
//node结点右子树中最小的结点的值作为此时node结点的值
int temp= delRightTreeMin(node.right);
node.value=temp;
} else {//删除只有一个子树的结点
//如果parent为空,说明要此树要删除的为根结点
if(parent==null){
if(node.left!=null){
root=node.left;
return;
}
else {
root=node.right;
return;
}
}
//如果有左子节点
if (node.left != null) {
//判断node是父节点的左子节点还是右子节点
if (parent.left != null && parent.left == node) {
parent.left = node.left;
} else if (parent.right != null && parent.right == node) {
parent.right = node.left;
}
}
//如果有右子节点
else {
//判断node是父节点的左子节点还是右子节点
if (parent.left != null && parent.left == node) {
parent.left = node.right;
} else if (parent.right != null && parent.right == node) {
parent.right = node.right;
}
}
}
}
测试:
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
BinarySortTree binarySortTree = new BinarySortTree();
for (int i = 0; i < arr.length; i++) {
binarySortTree.add(new Node(arr[i]));
}
binarySortTree.infixOrder();
binarySortTree.deleteNode(7);
System.out.println("---------------");
binarySortTree.infixOrder();
}
}结果
Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
---------------
Node{value=1}
Node{value=2}
Node{value=3}
Node{value=5}
Node{value=9}
Node{value=10}
Node{value=12}
十一.平衡二叉树(AVL树)
1.二叉排序树存在的问题
给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST),并分析问题所在.
上边BST存在的问题分析:
1)左子树全部为空，从形式上看，更像一个单链表.
2)插入速度没有影响
3)查询速度明显降低(因为需要依次比较),不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢
4)解决方案-平衡二叉树(AVL)
2.平衡二叉树的介绍
1)平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为
AVL树，可以保证查询效率较高。
2)具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
3）举例说明,看看下面哪些是AVL树,为什么?
第一棵树:2-1=1 ,这棵树是的
第二棵树:2-2=0,这棵树是的
第三棵树:3-1=2>1,这棵树不是平衡二叉树
3.AVL树的高度
class Node {
int value;
Node left;
Node right;
//返回左子树的高度
public int leftHeight(){
if(this.left==null)
return 0;
return this.left.height();
}
//返回右子树的高度
public int rightHeight(){
if(this.right==null)
return 0;
return this.right.height();
}
//返回当前结点的高度,以当前结点为根结点的高度
public int height(){
return Math.max(this.left==null?0:this.left.height(), this.right==null?0: this.right.height())+1;
}
}测试:
public class AVLTreeDemo {
public static void main(String[] args) {
int[] arr = {4,3,6,5,7,8};
AVLTree aVLTree = new AVLTree();
for (int i = 0; i < arr.length; i++) {
aVLTree.add(new Node(arr[i]));
}
aVLTree.infixOrder();
System.out.println("左子树的高度:");
System.out.println(aVLTree.root.leftHeight());
System.out.println("右子树的高度:");
System.out.println(aVLTree.root.rightHeight());
}
}打印:
Node{value=3}
Node{value=4}
Node{value=5}
Node{value=6}
Node{value=7}
Node{value=8}
左子树的高度:
1
右子树的高度:
3
4.AVL单旋转(左旋转)
1)要求:给你一个数列，创建出对应的平衡二叉树.数列{4,3,6,5,7.8}
对节点A进行左旋转的步骤
怎么处理--进行左旋转.
1.创建一个新的节点newNode(以4这个值创建),创建一个新的节点，值等于当前根节点的值
把新节点的左子树设需了当前节点的左子树
newNode.left =left
2.把新节点的右子树设置为当前节点的右子树的左子树
newNode.right =right.left;
3.把当前节点的值换为右子节点的值
value=right.value;
4.把当前节点的右子树设置成右子树的右子树
right=right.right;
5.把当前节点的左子树设置为新节点
left=newLeft;
.
5.左旋转的代码实现
//创建node结点
class Node {
int value;
Node left;
Node right;
//左旋转的方法
public void leftRotate() {
//创建新的结点,以当前根结点
Node newNode = new Node(this.value);
//把新的结点的左子树,设置成当前结点的左子树
newNode.left = this.left;
//把新节点的右子树设置为当前节点的右子树的左子树
newNode.right = this.right.left;
//把当前结点的值替换成右子节点的值
this.value = this.right.value;
//把当前节点的右子树设置成右子树的右子树
this.right = this.right.right;
//把当前结点的左子结点设置为新节点
this.left = newNode;
}
}6.AVL单旋转(右旋转)
1.创建一个新的节点newNode(以10这个值创建),创建一个新的节点，值等于当前根节点的值
把新节点的右子树设置了当前节点的右子树
newNode.right = right
2.把新节点的左子树设置为当前节点的左子树的右子树
newNode.left =left.right;
3.把当前节点的值换为左子节点的值
value=left.value;
4.把当前节点的左子树设置成左子树的左子树
left=left.left;
5.把当前节点的右子树设置为新节点
right=newLeft;
7.右旋转的代码实现
//创建node结点
class Node {
int value;
Node left;
Node right;
//右旋转
public void rightRotate(){
//创建新的结点,以当前根结点的值
Node newNode = new Node(this.value);
//把新节点的右子树设置了当前节点的右子树
newNode.right=this.right;
//把新节点的左子树设置为当前节点的左子树的右子树
newNode.left=this.left.right;
//把当前节点的值换为左子节点的值
this.value=this.left.value;
//把当前节点的左子树设置成左子树的左子树
this.left=this.left.left;
//把当前节点的右子树设置为新节点
this.right=newNode;
}
}8.双旋转
1.当符号右旋转的条件时
2.如果它的左子树的右子树高度大于它的左子树的高度 3.先对当前这个结点的左节点进行左旋转
4.在对当前结点进行右旋转的操作即可
9.双旋转的代码实现
//添加结点
public void add(Node node) {
if (node == null)
return;
if (node.value > this.value) {//如果添加的结点大的
if (this.right == null) {//当前结点为叶子结点
this.right = node;
} else {
//递归右子树添加
this.right.add(node);
}
} else {//如果添加的结点小的
if (this.left == null) {//当前结点为叶子结点
this.left = node;
} else {
//递归左子树添加
this.left.add(node);
}
}
//当添加完一个结点的后,如果(右子树的高度-左子树的高度)>1,左旋转
if (this.rightHeight() - this.leftHeight() > 1) {
//如果根结点的右子树的左子树的高度大于根结点的右子树的右子树的高度
if(this.right!=null&&this.right.leftHeight()>this.right.rightHeight()){
//先对当前结点的右子树进行右旋转
this.left.rightRotate();
}
leftRotate();//左旋转
return;
}
//当添加完一个结点的后,如果(左子树的高度-右子树的高度)>1,右旋转
if(this.leftHeight()-this.rightHeight()>1){
//如果根结点的左子树的右子树的高度大于根结点的左子树的左子树的高度
if(this.left!=null&&this.left.rightHeight()>this.left.leftHeight()){
//先对当前结点的左子树进行左旋转
this.left.leftRotate();
}
rightRotate();//右旋转
}
}测试:
public class AVLTreeDemo {
public static void main(String[] args) {
int[] arr = {10,11,7,6,8,9};
AVLTree aVLTree = new AVLTree();
for (int i = 0; i < arr.length; i++) {
aVLTree.add(new Node(arr[i]));
}
aVLTree.infixOrder();
System.out.println("左子树的高度:");
System.out.println(aVLTree.root.leftHeight());
System.out.println("右子树的高度:");
System.out.println(aVLTree.root.rightHeight());
}
}打印:
Node{value=6}
Node{value=7}
Node{value=8}
Node{value=9}
Node{value=10}
Node{value=11}
左子树的高度:
2
右子树的高度:
2
十二.多叉树
1.二叉树的问题分析
二叉树的操作效率较高，但是也存在问题,请看下面的二叉树
1)二叉树需要加载到内存的，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多(比如1亿)，就存在如下问题
2)问题1:在构建二叉树时，需要多次进行i/o操作(海量数据存在数据库或文件中)，节点海量构建二叉树时,速度有影响
3)问题2:节点海量，也会造成二叉树的高度很大,会降低操作速度.
2.多叉树的介绍
1)在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以
有更多的数据项和更多的子节点，就是多叉树(multiway tree)
2)后面我们讲解的2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少
树的高度,能对二叉树进行优化。
3)举例说明(下面2-3树就是一颗多叉树)
3.B树的介绍
B树通过重新组织节点，降低树的高度，并且减少i/o读写次数来提升效率。
1)如图B树通过重新组织节点，降低了树的高度
2)文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(页
得大小通常为4k)，这样每个节点只需要一次l/o就可以完全载入
3)将树的度M设置为1024，在600亿个元素中最多只需要4次Vo操作就可以读取到想要的元素,B
树()广泛应用于文件存储系统以及数据库系统中
4.2-3树
1)2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件)
2)有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点.
3)有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点.4)2-3树是由二节点和三节点构成的树。
5.构建2-3树
将数列{16,24,12,32,14,26,34,10,8,28,38,20}构建成2-3树，并保证数据插入的大小顺序。
插入规则:
1)2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件)
2)有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点.
3)有三个子节点的节点叫三节点，三节点要么没有子节点,要么有三个子节点
4)当按照规则插入一个数到某个节点时﹐不能满足上面三个要求，就需要拆,先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面3个条件。
5)对于三节点的子树的值大小仍然遵守
①放入16
②放入24
③放入12
④放入32
⑤放入14
⑥放入26
⑦放入34
⑧放入10
⑨放入8
⑩放入28
⑪放入38
⑫放入20
6. 2-3-4树
除了23树，还有234树等，概念和23树类似，也是一种B树。如图:
7.B树
B-tree树即B树，B即Balanced，平衡的意思。有人把B-tree翻译成B-树，容易让人产生误解。会以为B-树是一种树，而B树又是另一种树。实际上，B-tree就是指的B树。
前面已经介绍了2-3树和2-3-4树，他们就是B树(英语:B-tree也写成B-树)，这里我们再做一个说明，我们在学习Mysql时，经常听到说某种类型的索引是基于B树或者B+树的，如图:
B树的说明:
1)B树的阶:节点的最多子节点个数。比如2-3树的阶是3，2-3-4树的阶是4
2)B-树的搜索，从根结点开始,对结点内的关键字(有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点;重复，直到所对应的儿子指针为空，或已经是叶子结点
3)关键字集合分布在整颗树中，即叶子节点和非叶子节点都存放数据.
4)搜索有可能在非叶子结点结束
5)其搜索性能等价于在关键字全集内做一次二分查找
8.B+树
B+树是B树的变体，也是一种多路搜索树。
B+树的说明:
1)B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找.
2)所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】)，且链表中的关键字(数据)恰好是有序的。
3)不可能在非叶子结点命中
4)非叶子结点相当于是叶子结点的索引(稀疏索引)叶子结点相当于是存储（关键字）数据的数据层
5)更适合文件索引系统
6)B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然.
9.B*树
B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。
B*树的说明:
1)B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3，而B+树的块的最低使用率为B+树的1/2.
2)从第1个特点我们可以看出，B*树分配新结点的概率比B+树要低，空间使用率更高