作为程序员，难道你心里没点“B树”？

• 顺序存储

• 链式存储

• 树

树的概述

如上图是一个二叉树, 当然树还能有三叉,四叉等等...

• 根节点: 最顶上的节点 即A
  层: 根节点在第一层 BE在第二层
  高度: 最大的层数
  森林: 多个树的组合
  权: 节点上的值 如根节点的权是 A
  叶子节点: 下层上的节点是上一层的叶子节点
  双亲节点: 上层的节点是下层的节点的双亲节点(单个节点又是爸又是妈)
  路径: 找到C的路径是 A-B-C
  度: 就是直接子节点的个数

• 什么是二叉树?

• 什么是满二叉树?

• 什么是完全二叉树?

• 封装二叉树节点

public class TreeNode {
 // 权
 private int value;
 // 左节点
 private TreeNode leftNode;
 // 右节点
 private TreeNode rightNode;
}

• 封装二叉树

public class BinaryTree {
 TreeNode root;

 public void setRoot(TreeNode root) {
 this.root = root;
 }

 public TreeNode getRoot() {
 return this.getRoot();
 }
}

遍历

像这样一颗二叉树,通过不同的书序遍历会得到不同的结果

前中后的顺序说的是root节点的顺序,前序的话就是先遍历父节点, 中序就是左父右 后续就是左右父

• 前序遍历

 public void frontShow() {
 System.out.println(this.value);
 if (leftNode != null)
 leftNode.frontShow();

 if (rightNode != null)
 rightNode.frontShow();
 }

• 中序遍历

 public void middleShow() {
 if (leftNode != null)
 leftNode.middleShow();

 System.out.println(value);

 if (rightNode != null)
 rightNode.middleShow();
 }

• 后续遍历

 public void backShow() {
 if (leftNode != null)
 leftNode.backShow();

 if (rightNode != null)
 rightNode.backShow();

 System.out.println(value);
 }

查找

其实有了上面三种遍历的方式, 查找自然存在三种, 一遍遍历一遍查找

 public TreeNode frontSeach(int num) {
 TreeNode node = null;
 // 当前节点不为空,返回当前节点
 if (num == this.value) {
 return this;
 } else {
 // 查找左节点
 if (leftNode != null) {
 node = leftNode.frontSeach(num);
 }
 if (node != null)
 return node;
 // 查找右节点
 if (rightNode != null)
 node = rightNode.frontSeach(num);
 }
 return node;
 }

删除节点

删除节点也是, 不考虑特别复杂的情况, 删除节点就有两种情况, 第一种要删除的节点就是根节点, 那么让根节点=null就ok, 第二种情况要删除的节点不是根节点,就处理它的左右节点, 左右节点还不是需要删除的元素的话那么就得递归循环这个过程

 // 先判断是否是根节点,在调用如下方法

 public void deleteNode(int i) {
 TreeNode parent = this;
 // 处理左树
 if (parent.leftNode!=null&&parent.leftNode.value==i){
 parent.leftNode=null;
 return;
 }
 // 处理左树
 if (parent.rightNode!=null&&parent.rightNode.value==i){
 parent.rightNode=null;
 return;
 }
 // 递归-重置父节点
 parent=leftNode;
 if (parent!=null)
 parent.deleteNode(i);
 // 递归-重置父节点
 parent=rightNode;
 if (parent!=null)
 parent.deleteNode(i);

 }

顺序存储二叉树

文章一开始刚说了, 顺序存储的数据结构的典型代表就是数组, 就像这样

[1,2,3,4,5,6,7]

什么是顺序存储的二叉树呢? 其实就是将上面的数组看成了一颗树,就像下图这样

• 第n个元素的左子节点是 2n-1
• 第n个元素的右子节点是 2n-2
• 第n个元素的父节点是 (n-1)/2
• 遍历顺序存储的二叉树

 public void frontShow(int start){
 if (data==null||data.length==0){
 return;
 }
 // 遍历当前节点
 System.out.println(data[start]);
 // 遍历左树
 if (2*start+1<data.length)
 frontShow(2*start+1);
 // 遍历右树
 if (2*start+2<data.length)
 frontShow(2*start+2);
 }

• 问题1: 虽然可以正确的遍历出 4,2,5,1,3,6 , 但是当我们遍历到2时, 我们是不知道2的前一个是谁的,(哪怕我们刚才遍历到了它的前一个节点就是4)
• 问题2: node4,5,6,3的左右节点的引用存在空闲的情况

• 如果这个节点的右节点为空,我们就让它让它指向自己的后继节点, 例如上图的红线
• 如何节点的左节点为空, 就让这个空闲的节点指向它的前驱节点,例如上图的蓝色线

 // 临时保存上一个节点
 private TreeNode preNode;

 // 中序线索化二叉树
 void threadNode(TreeNode node) {
 if (node == null)
 return;

 // 处理左边
 threadNode(node.getLeftNode());

 // 左节点为空,说明没有左子节点, 让这个空出的左节点指向它的上一个节点
 if (node.getLeftNode() == null) {
 // 指向上一个节点
 node.setLeftNode(preNode);
 // 标识节点的类型
 node.setLeftType(1);
 }

 // 处理前驱节点的右指针
 // 比如现在遍历到了1, 1的上一个节点是5, 5的右边空着了, 于是让5的有节点指向1
 if (preNode != null && preNode.getRightNode() == null) {
 preNode.setRightNode(node);
 preNode.setRightType(1);
 }

 // 每次递归调用一次这个方法就更新前驱节点
 preNode = node;
 // 处理右边
 threadNode(node.getRightNode());
 }

遍历二叉树

 public void threadIterator() {
 TreeNode node = root;
 while (node != null) {
 // 循环找
 while (node.getLeftType() == 0)
 node = node.getLeftNode();
 // 打印当前节点
 System.out.println(node.getValue());
 // 如果当前的节点的右type=1说明它有指针指向自己的前一个节点
 // 比如现在位置是4, 通过下面的代码可以让node=2
 while (node.getRightType() == 1) {
 node = node.getRightNode();
 System.out.println(node.getValue());
 }

 // 替换遍历的节点, 可以让 node从2指向 5, 或者从3指向1
 node = node.getRightNode();
 }

 }

赫夫曼树(最优二叉树)

• 什么是叶子节点的带权路径?

• 树的带权路径长度(weight path length) 简称 WPL

• 思路:

假设我们现在已经有了数组 [3,5,7,8,11,14,23,29], 如何将这个数组转换成赫夫曼树呢?

如此往复,最终得到的树就是huffman树

• java实现:

public class TreeNode implements Comparable{
 // 权
 private int value;
 private TreeNode leftNode;
 private TreeNode rightNode;

 @Override
 public int compareTo(Object o) {
 TreeNode node = (TreeNode) o;
 return this.value-node.value;
 }

 // 创建赫夫曼树
 private static TreeNode buildHuffmanTree(int[] arr) {
 // 创建一个集合,存放将arr转换成的二叉树
 ArrayList<TreeNode> list = new ArrayList<>();
 for (int i : arr) {
 list.add(new TreeNode(i));
 }
 // 开始循环, 当集合中只剩下一棵树时
 while (list.size() > 1) {
 // 排序
 Collections.sort(list);
 // 取出权值最小的数
 TreeNode leftNode = list.get(list.size() - 1);
 // 取出权值次要小的数
 TreeNode rightNode = list.get(list.size() - 2);
 // 移除取出的两棵树
 list.remove(leftNode);
 list.remove(rightNode);

 // 创建新的树根节点
 TreeNode parentNode = new TreeNode(leftNode.getValue() + rightNode.getValue(), leftNode, rightNode);
 // 将新树放到原树的集合中
 list.add(parentNode);
 }
 return list.get(0);
 }

1. 将原字符串的每一个char强转换成 byte == ASCII
99 97 110 32 121 111 117 32 99 97 110 32 97 32 99 97 110 32 97 115 32 97 32 99 97 110 110 101 114 32 99 97 110 32 97 32 99 97 110

2. 将byte toBinaryString 转换成01串如下:
1100011110000111011101000001111001110111111101011
0000011000111100001110111010000011000011000001100
0111100001110111010000011000011110011100000110000
1100000110001111000011101110100000110001111000011
1011101101110110010111100101000001100011110000111
011101000001100001100000110001111000011101110101110

public class TreeNode implements Comparable{
 // 存放权重就是字符出现的次数
 private int weight;
 // 存放英文数值
 private Byte data; //
 private TreeNode leftNode;
 private TreeNode rightNode;

封装完成后, 按照权重的大小倒序排序,各个节点长成这样:

a:11 :11 n:8 c:7 o:1 .:1 y:1 e:1 u:1 s:1 r:1

将赫夫曼树画出来长这样:

特征,我们让左侧的路径上的值是0, 右边是1. 因此通过这个赫夫曼树其实我们可以得到一张赫夫曼编码表,

比如像下面这样:

n: 00
 : 01
a: 10
c: 111
// 每一个字符的编码就是从根节点到它的路径

1111000xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

使用前缀就是先取出1 去查查编码表有没有这个数? 有的话就返回对应的字符, 没有的话就用11再去匹配

大家可以看看上面的那颗霍夫曼树, 所有的data都在叶子节点上,所以使用前缀匹配完全可以,绝对不会出现重复的情况

• 使用java实现这个过程

思路概览:

1. 将原生的字节数组转化成一个个的TreeNode

2. 取出所有的TreeNode封装成赫夫曼树

3. 通过赫夫曼树踢去出赫夫曼编码表

4. 使用这个编码表进行编码

5. 解码

 private static byte[] huffmanZip(byte[] bytes) {
 // 先统计每个byte出现的次数,放入集合中
 List<TreeNode> treeNodes = buildNodes(bytes);
 // 创建赫夫曼树
 TreeNode node = createHuffmanTree(treeNodes);
 // 创建huffman编码表
 Map<Byte, String> codes = createHuffmanCodeTable(node);
 // 编码, 将每一个byte替换成huffman编码表中的V
 byte[] encodeBytes = encodeHuffmanByte(bytes, codes);

 // 使用huffman编码进行解码
 byte[] decodeBytes = decode(encodeBytes);
 return decodeBytes;
 }

将原生的byte数组,封装成一个个的TreeNode节点,保存在一个容器中,并且记录下这个节点出现的次数, 因此我们需要将出现次数多的节点靠近根节点

 /**
 * 将byte转换成node集合
 *
 * @param bytes
 * @return
 */
 private static List<TreeNode> buildNodes(byte[] bytes) {
 ArrayList<TreeNode> list = new ArrayList<>();
 HashMap<Byte, Integer> countMap = new HashMap<>();
 // 统计每一个节点的出现的次数
 for (byte aByte : bytes) {
 Integer integer = countMap.get(aByte);
 if (integer == null) {
 countMap.put(aByte, 1);
 } else {
 countMap.put(aByte, integer + 1);
 }
 }
 // 将k-v转化成node
 countMap.forEach((k, v) -> {
 list.add(new TreeNode(v, k));
 });
 return list;
 }

构建赫夫曼树

 /**
 * 创建huffman树
 *
 * @param treeNodes
 * @return
 */
 private static TreeNode createHuffmanTree(List<TreeNode> treeNodes) {
 // 开始循环, 当集合中只剩下一棵树时
 while (treeNodes.size() > 1) {
 // 排序
 Collections.sort(treeNodes);
 // 取出权值最小的数
 TreeNode leftNode = treeNodes.get(treeNodes.size() - 1);
 // 取出权值次要小的数
 TreeNode rightNode = treeNodes.get(treeNodes.size() - 2);
 // 移除取出的两棵树
 treeNodes.remove(leftNode);
 treeNodes.remove(rightNode);

 // 创建新的树根节点
 TreeNode parentNode = new TreeNode(leftNode.getWeight() + rightNode.getWeight(), leftNode, rightNode);
 // 将新树放到原树的集合中
 treeNodes.add(parentNode);
 }
 return treeNodes.get(0);
 }

 static StringBuilder stringBuilder = new StringBuilder();
 static Map<Byte, String> huffCode = new HashMap<>();

 /**
 * 创建huffman便编码表
 *
 * @param node
 * @return
 */
 private static Map<Byte, String> createHuffmanCodeTable(TreeNode node) {
 if (node == null)
 return null;
 getCodes(node.getLeftNode(), "0", stringBuilder);
 getCodes(node.getRightNode(), "1", stringBuilder);
 return huffCode;
 }

 /**
 * 根据node, 获取编码
 *
 * @param node
 * @param code
 * @param stringBuilder
 */
 private static void getCodes(TreeNode node, String code, StringBuilder stringBuilder) {
 StringBuilder sb = new StringBuilder(stringBuilder);
 sb.append(code);
 // 如果节点的data为空,说明根本不是叶子节点,接着递归
 if (node.getData() == null) {
 getCodes(node.getLeftNode(), "0", sb);
 getCodes(node.getRightNode(), "1", sb);
 } else {
 // 如果是叶子节点,就记录它的data和路径
 huffCode.put(node.getData(), sb.toString());
 }
 }

怎么转换呢? 比如不是-23, 而是-1
真值 1
原码:1,0001
补码: 2^(4+1) +1 = 100000 + (-1) = 1,1111
我们获取到的结果就是1111

 /**
 * 进行编码
 *
 * @param bytes
 * @param codes
 * @return
 */
 private static byte[] encodeHuffmanByte(byte[] bytes, Map<Byte, String> codes) {
 StringBuilder builder = new StringBuilder();
 for (byte aByte : bytes) {
 builder.append(codes.get(aByte));
 }

 // 将这些byte按照每8位一组进行编码
 int length = 0;
 if (builder.length() % 8 == 0) {
 length = builder.length() / 8;
 } else {
 length = builder.length() / 8 + 1;
 }
 // 用于存储压缩后的byte
 byte[] resultByte = new byte[length];
 // 记录新byte的位置
 int index = 0;
 // 遍历新得到的串
 for (int i = 0; i < builder.length(); i += 8) {
 String str = null;
 if (i + 8 > builder.length()) {
 str = builder.substring(i);
 } else {
 str = builder.substring(i, i + 8);
 }
 // 将八位的二进制转换成byte
 // 这里出现负数了.... 涉及到补码的问题
 byte encodeByte = (byte) Integer.parseInt(str, 2);
 // 存储起来
 resultByte[index] = encodeByte;
 index++;
 }
 return resultByte;
 }

/**
 * 按照指定的赫夫曼编码表进行解码
 *
 * @param encodeBytes
 * @return
 */
 private static byte[] decode(byte[] encodeBytes) {
 List<Byte> list = new ArrayList();
 StringBuilder builder = new StringBuilder();
 for (byte encodeByte : encodeBytes) {
 // 判断是否是最后一个,如果是最后一次不用用0补全, 因此最后一位本来就不够8位
 boolean flag = encodeByte == encodeBytes[encodeBytes.length - 1];
 String s = byteToBitStr(!flag, encodeByte);
 builder.append(s);
 }
 // 调换编码表的k-v
 Map<String, Byte> map = new HashMap<>();
 huffCode.forEach((k, v) -> {
 map.put(v, k);
 });
 // 处理字符串
 for (int i = 0; i < builder.length(); ) {
 int count = 1;
 boolean flag = true;
 Byte b = null;
 while (flag){
 String key = builder.substring(i,i+count);
 b=map.get(key);
 if (b==null){
 count++;
 }else {
 flag=false;
 }
 }
 list.add(b);
 i+=count;
 }

 // 将list转数组
 byte[] bytes = new byte[list.size()];
 int i=0;
 for (Byte aByte : list) {
 bytes[i]=aByte;
 i++;
 }
 return bytes;
 }

 /**
 * 将byte转换成二进制的String
 *
 * @param b
 * @return
 */
 public static String byteToBitStr(boolean flag, byte b) {
 /**
 * 目标: 全部保留八位.正数前面就补零, 负数前面补1
 * 为什么选256呢? 因为我们前面约定好了, 按照8位进行分隔的
 * 256的二进制表示是 1 0000 0000
 * 假设我们现在是 1
 * 计算 1 0000 0000
 * 或 0 0000 0001
 * ----------------------
 * 1 0000 0001
 * 结果截取8位就是 0000 0001
 *
 * 假设我们现在是 -1
 * 转换成二进制: 1111 1111 1111 1111 1111 1111 1111 1111
 *
 * 计算 1 0000 0000
 * 或 1111 1111 1111 1111 1111 1111 1111 1111
 * ----------------------
 * 1 1111 1111
 * 结果截取8位就是 1111 1111
 *
 *
 */
 int temp = b;
 if (flag) {
 temp |= 256;
 }
 String str = Integer.toBinaryString(temp);
 if (flag) {
 return str.substring(str.length() - 8);
 } else {
 return str;
 }

 }

• 线性存储和链式存储的优缺点

• 我们的主角: 二叉搜索树

二叉排序树有如下的特点:

• 对于二叉排序树中的任意一个非叶子节点都要求他的左节点小于自己, 右节点大于自己

• 空树也是二叉排序树

将上面的无序的数组转换成二叉排序树长成下图这样

如果我们按照中序遍历的话结果是: 1 3 5 7 9 11 12 , 正好是从小到大完成排序

再看他的特征: 如果我们想查找12 , 很简单 7-10-12 , 如果我们想插入也很简单,它有链表的特性

java&二叉排序树

封装Node和Tree

// tree
public class BinarySortTree {
 Node root;
}

// node
public class Node {
 private int value;
 private Node leftNode;
 private Node rightNode;
}

-----------BinarySortTree.class---------------
/**
 * 向二叉排序树中添加节点
 */
 public void add(Node node) {
 if (root == null) {
 root = node;
 } else {
 root.add(node);
 }
 }

-------------Node.class------------
/**
 * 添加节点
 *
 * @param node
 */
 public void add(Node node) {
 if (node == null)
 return;
 //判断需要添加的节点的值比传递进来的节点的值大还是小
 // 添加的节点小于当前节点的值
 if (node.value < this.value) {
 if (this.leftNode == null) {
 this.leftNode = node;
 } else {
 this.leftNode.add(node);
 }
 } else {
 if (this.rightNode == null) {
 this.rightNode = node;
 } else {
 this.rightNode.add(node);
 }
 }
 }

情况1: 如图

这是最好处理的情况, 就是说需要删除的元素就是单个的子节点

情况2: 如图

1. 临时存储node9
2. 删除node9
3. 用临时存储的node9替换node7

1. 临时保存node9
2. 删除node9
3. 让node9的右节点替换node9
4. 让临时存储的node9替换node7

/**
 * 删除一个节点
 *
 * @param value
 * @return
 */
 public void delete(int value) {
 if (root == null) {
 return;
 } else {
 // 找到这个节点
 Node node = midleSearch(value);
 if (node == null)
 return;
 // 找到他的父节点
 Node parentNode = searchParent(value);

 // todo 当前节点是叶子节点
 if (node.getLeftNode() == null && node.getRightNode() == null) {
 if (parentNode.getLeftNode().getValue() == value) {
 parentNode.setLeftNode(null);
 } else {
 parentNode.setRightNode(null);
 }
 // todo 要删除的节点存在两个子节点
 } else if (node.getLeftNode() != null && node.getRightNode() != null) {
 // 假设就是删除7
 //1. 找到右子树中最小的节点,保存它的值,然后删除他
 int minValue = deleteMin(node.getRightNode());
 //2.替换被删除的节点值
 node.setValue(minValue);

 } else { // todo 要删除的节点有一个左子节点或者是右子节点
 // 左边有节点
 if (node.getLeftNode() != null) {
 // 要删除的节点是父节点的左节点
 if (parentNode.getLeftNode().getValue() == value) {
 parentNode.setLeftNode(node.getLeftNode());
 } else {// 要删除的节点是父节点的右节点
 parentNode.setRightNode(node.getLeftNode());
 }
 } else { // 右边有节点
 // 要删除的节点是父节点的右节点
 if (parentNode.getLeftNode().getValue() == value) {
 parentNode.setLeftNode(node.getRightNode());
 } else {// 要删除的节点是父节点的右节点
 parentNode.setRightNode(node.getRightNode());
 }
 }
 }
 }
 }

 /**
 * 删除并保存以当前点为根节点的树的最小值节点
 * @param node
 * @return
 */
 private int deleteMin(Node node) {
 // 情况1: 值最小的节点没有右节点
 // 情况2: 值最小的节点存在右节点
 // 但是下面我们使用delete,原来考虑到了
 while(node.getLeftNode()!=null){
 node=node.getLeftNode();
 }
 delete(node.getValue());
 return node.getValue();
 }

 /**
 * 搜索父节点
 *
 * @param value
 * @return
 */
 public Node searchParent(int value) {
 if (root == null) {
 return null;
 } else {
 return root.searchParent(value);
 }
 }

缺点

二叉排序树其实对节点权是有要求的, 比如我们的数组就是[1,2,3,4] 那么画成平衡二叉树的话长下面这样

平衡二叉树的出现就是为了 解决上面二叉排序树[1,2,3,4,5,6]这样成单条链的略势的情况,它要求,每个树的左子树和右子树的高度之差不超过1, 如果不满足这种情况了,马上马对各个节点进行调整,这样做保证了二叉排序树的优势

• 情况1: 对于node1来说, 它的左边深度0 , 右边的深度2 , 于是我们将它调整成右边的样子

• 情况2: 在1234的情况下, 添加node5,导致node2不平衡, 进行如下的调整

• 情况3: 在12345的基础上添加node6,导致node4不平衡, 对node4进行调整, 其实就和情况1相同了

• 情况4: 在1234567的情况下,进行添加8. 打破了node5的平衡, 因此进行旋转

一个通用的旋转规律

看这个典型的有旋转的例子

1. 创建新node, 使新node.value = this.value
2. 新节点的rightNode = this.rightNode
3. 新节点的leftNode = this.leftNode.rightNode
4. this.value = this.LeftNode.value
5. this.leftNode = this.leftNode .leftNode
6. this.leftNode = 新创建的node

需要注意的情况:

    新添加6使得node8不再平衡,但是如果你按照上面的步骤进行旋转的话,会得到右边的结果, 但是右边的结果中对于node4还是不平衡的,因此需要预处理一下

    再进行右旋转时,提前进行检验一下,当前节点的左子树是否存在右边比左边高的情况, 如果右边比较高的话,就先将这个子树往左旋转, 再以node8为根,整体往右旋转。

这么多的树，你知道几个呢，不妨收藏起来，慢慢消化吧!