五、树和二叉树

一、树的引入

二、树的术语

三、二叉树

3.1 二叉树的概念

3.2 二叉树的遍历

package com.gyh.tree;/*** @author Gao YongHao* @version 1.0*/
public class BinaryTreeDemo<T> {private BinaryNode<T> root;public BinaryTreeDemo(BinaryNode<T> root) {this.root = root;}public static void main(String[] args) {BinaryNode<String> node1 = new BinaryNode<>("宋江", null, null);BinaryNode<String> node2 = new BinaryNode<>("吴用", null, null);BinaryNode<String> node3 = new BinaryNode<>("卢俊", null, null);BinaryNode<String> node4 = new BinaryNode<>("林冲", null, null);BinaryNode<String> node5 = new BinaryNode<>("关胜", null, null);node1.left = node2;node1.right = node3;node3.left = node5;node3.right = node4;BinaryTreeDemo<String> stringBinaryTreeDemo = new BinaryTreeDemo<String>(node1);System.out.println("先序遍历");stringBinaryTreeDemo.preOrder(); // 先序遍历System.out.println();System.out.println("中序遍历");stringBinaryTreeDemo.midOrder(); // 中序遍历System.out.println();System.out.println("后序遍历");stringBinaryTreeDemo.afterOrder(); // 后序遍历}// 先序遍历public void preOrder() {if (root == null) {System.out.println("二叉树为空无法判定");return;}preOrder(root);}private void preOrder(BinaryNode<T> bn) {System.out.println(bn.data);if (bn.left != null) {preOrder(bn.left);}if (bn.right != null) {preOrder(bn.right);}}// 中序遍历public void midOrder() {if (root == null) {System.out.println("二叉树为空无法判定");return;}midOrder(root);}private void midOrder(BinaryNode<T> bn) {if (bn.left != null) {midOrder(bn.left);}System.out.println(bn.data);if (bn.right != null) {midOrder(bn.right);}}// 后序遍历public void afterOrder() {if (root == null) {System.out.println("二叉树为空无法判定");return;}afterOrder(root);}private void afterOrder(BinaryNode<T> bn) {if (bn.left != null) {afterOrder(bn.left);}if (bn.right != null) {afterOrder(bn.right);}System.out.println(bn.data);}}class BinaryNode<T> {T data;BinaryNode<T> left;BinaryNode<T> right;public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {this.data = data;this.left = left;this.right = right;}
}

3.3 二叉树-查找指定结点

package com.gyh.tree;/*** @author Gao YongHao* @version 1.0*/
public class BinaryTreeSearch<T> {BinaryNode<T> root;public static void main(String[] args) {BinaryNode<String> node1 = new BinaryNode<>("宋江", null, null);BinaryNode<String> node2 = new BinaryNode<>("吴用", null, null);BinaryNode<String> node3 = new BinaryNode<>("卢俊", null, null);BinaryNode<String> node4 = new BinaryNode<>("林冲", null, null);BinaryNode<String> node5 = new BinaryNode<>("关胜", null, null);node1.left = node2;node1.right = node3;node3.left = node5;node3.right = node4;BinaryTreeSearch<String> stringBinaryTreeSearch = new BinaryTreeSearch<>(node1);System.out.println(stringBinaryTreeSearch.preSearch("1")); // 前序查找System.out.println(stringBinaryTreeSearch.midSearch("林冲")); // 中序查找System.out.println(stringBinaryTreeSearch.afterSearch("林冲")); // 后序查找}public BinaryTreeSearch(BinaryNode<T> root) {this.root = root;}public BinaryNode<T> preSearch(T d) {if (root == null) {return null;}return preSearch(root, d);}private BinaryNode<T> preSearch(BinaryNode<T> bn, T d) {if (bn.data.equals(d)) {return bn;}BinaryNode<T> resNode;if (bn.left != null) {// 左递归前序查找，找到结点，则返回，否则继续判断if ((resNode = preSearch(bn.left, d)) != null) return resNode;}if (bn.right != null) {if ((resNode = preSearch(bn.right, d)) != null) return resNode;}return null;}public BinaryNode<T> midSearch(T d) {if (root == null) {return null;}return midSearch(root, d);}private BinaryNode<T> midSearch(BinaryNode<T> bn, T d) {BinaryNode<T> resNode;if (bn.left != null) {// 左递归前序查找，找到结点，则返回，否则继续判断if ((resNode = midSearch(bn.left, d)) != null) return resNode;}if (bn.data.equals(d)) {return bn;}if (bn.right != null) {if ((resNode = midSearch(bn.right, d)) != null) return resNode;}return null;}public BinaryNode<T> afterSearch(T d) {if (root == null) {return null;}return afterSearch(root, d);}private BinaryNode<T> afterSearch(BinaryNode<T> bn, T d) {BinaryNode<T> resNode;if (bn.left != null) {// 左递归前序查找，找到结点，则返回，否则继续判断if ((resNode = midSearch(bn.left, d)) != null) return resNode;}if (bn.right != null) {if ((resNode = midSearch(bn.right, d)) != null) return resNode;}if (bn.data.equals(d)) {return bn;}return null;}}

3.3 二叉树-删除结点

package com.gyh.tree;/*** @author Gao YongHao* @version 1.0*/
public class BinaryRemove<T> {BinaryNode<T> root;public static void main(String[] args) {BinaryNode<String> node1 = new BinaryNode<>("宋江", null, null);BinaryNode<String> node2 = new BinaryNode<>("吴用", null, null);BinaryNode<String> node3 = new BinaryNode<>("卢俊", null, null);BinaryNode<String> node4 = new BinaryNode<>("林冲", null, null);BinaryNode<String> node5 = new BinaryNode<>("关胜", null, null);node1.left = node2;node1.right = node3;node3.left = node5;node3.right = node4;BinaryRemove<String> stringBinaryRemove = new BinaryRemove<String>(node1);System.out.println(stringBinaryRemove.delete("关胜"));}public BinaryRemove(BinaryNode<T> root) {this.root = root;}public boolean delete(T d) {if (root == null) {return false;}if (root.data.equals(d)) {root = null;return true;}return delete(root, d);}private boolean delete(BinaryNode<T> bn, T d) {// 已经是叶子结点，因此没有对应的数据if (bn.left == null && bn.right == null) {return false;}// 左子树的根节点是要删除的元素if (bn.left != null && bn.left.data.equals(d)) {
//            bn.left = null;if (bn.left.left == null && bn.left.right == null) {bn.left = null; // 叶子结点直接删除} else if (bn.left.left == null) {bn.left = bn.left.right; // 右边有则加入右边} else {bn.left = bn.left.left; // 左边有或两边都有则加入左边}return true;}// 右子树的根节点是要删除的元素if (bn.right != null && bn.right.data.equals(d)) {
//            bn.right = null;if (bn.right.left == null && bn.right.right == null) {bn.right = null; // 叶子结点直接删除} else if (bn.right.left == null) {bn.right = bn.right.right; // 右边有则加入右边} else {bn.right = bn.right.left; // 左边有或两边都有则加入左边}return true;}// 左递归删除if (bn.left != null) {if (delete(bn.left, d)) {return true;}}// 右递归删除if (bn.right != null) {// 若左递归没有删除结点，则右递归结果作为最终的return delete(bn.right, d);}// 没有当前结点的删除，因为当前结点在上一层递归中已作出判断return false;}}

3.4 顺序存储二叉树

package com.gyh.tree;/*** @author Gao YongHao* @version 1.0*/
public class ArrBinaryTree {int[] arr;public static void main(String[] args) {int[] arr = {1, 2, 3, 4, 5, 6, 7};new ArrBinaryTree(arr).preSearch();}public ArrBinaryTree(int[] arr) {this.arr = arr;}public void preSearch() {preSearch(0);}private void preSearch(int index) {if (arr == null || arr.length == 0) {System.out.println("数组为空，不能遍历");return;}if (index > arr.length - 1) {return;}System.out.println(arr[index]);// 遍历左子树preSearch(2 * index + 1);// 遍历右子树preSearch(2 * index + 2);}
}

3.5 线索化二叉树

• n个结点对应有n+1个空指针域（左指针域与右指针域工2n个）
  

3.5.1 线索化二叉树应用案例

• 处理核心是得到存在空指针的域的结点，设置当前结点的左指针向前驱结点；设置当前结点的前驱结点的右指针指向自己
  

package com.gyh.tree;/*** @author Gao YongHao* @version 1.0*/
public class ThreadedBinaryTreeDemo<T> {public static void main(String[] args) {ThreadBinaryNode<Integer> node1 = new ThreadBinaryNode<Integer>(1, null, null);ThreadBinaryNode<Integer> node2 = new ThreadBinaryNode<Integer>(3, null, null);ThreadBinaryNode<Integer> node3 = new ThreadBinaryNode<Integer>(6, null, null);ThreadBinaryNode<Integer> node4 = new ThreadBinaryNode<Integer>(8, null, null);ThreadBinaryNode<Integer> node5 = new ThreadBinaryNode<Integer>(10, null, null);ThreadBinaryNode<Integer> node6 = new ThreadBinaryNode<Integer>(14, null, null);node1.left = node2;node1.right = node3;node2.left = node4;node2.right = node5;node3.left = node6;ThreadedBinaryTreeDemo<Integer> binaryTreeDemo = new ThreadedBinaryTreeDemo<>(node1);binaryTreeDemo.threadNodes();// 测试叶子结点的左右指针指向System.out.println("left:" + node5.leftType + " " + node5.left.data);System.out.println("left:" + node5.leftType + " " + node5.right.data);}ThreadBinaryNode<T> root;// pre 当前结点对象的前驱结点ThreadBinaryNode<T> pre = null;public ThreadedBinaryTreeDemo(ThreadBinaryNode<T> root) {this.root = root;}public void threadNodes() {if (root == null) {return;}threadNodes(root);}/*** 编写对二叉树进行中序线索化的方法** @param cur 当前结点对象*/private void threadNodes(ThreadBinaryNode<T> cur) {// 当前结点为空if (cur == null) {return;}// 线索化左子树threadNodes(cur.left);// 线索化当前结点// 先处理当前结点的前驱结点if (cur.left == null) {// 指向前驱结点cur.left = pre;// 设置左子树表示为前驱结点cur.leftType = 1;}// 处理右指针// 是让后继结点处理前驱结点的空指针域（即若前驱结点的右指针域为null，则让其指向当前结点）if (pre != null && pre.right == null) {// 让前驱结点的右指针指向当前结点pre.right = cur;// 设置右子树表示为后继结点pre.rightType = 1;}// 每处理一个结点后，让当前结点是下一个结点的前驱结点pre = cur;// 线索化右子树threadNodes(cur.right);}}class ThreadBinaryNode<T> {T data;int leftType; // 为0表示指向的是左子树，如果1则表示前驱ThreadBinaryNode<T> left;int rightType; // 为0表示指向的是右子树，如果1则表示后继ThreadBinaryNode<T> right;public ThreadBinaryNode(T data, ThreadBinaryNode<T> left, ThreadBinaryNode<T> right) {this.data = data;this.left = left;this.right = right;}public ThreadBinaryNode(T data, int leftType, ThreadBinaryNode<T> left, int rightType, ThreadBinaryNode<T> right) {this.data = data;this.leftType = leftType;this.left = left;this.rightType = rightType;this.right = right;}
}

3.5.2 遍历线索化二叉树

public void threadedShow() {// 循环找到 leftType == 1的结点，第一个找到就是8结点// 结点随着遍历而变化，因为当leftType==1时，说明该节点是按照线索化// 处理后的有效结点ThreadBinaryNode<T> node = root;while (node != null) {while (node.leftType == 0) {node = node.left;}System.out.println(node.data);// 如果当前结点的右指针指向的是后继节点，就一直输出while (node.rightType == 1) {// 获取到当前结点的后继节点node = node.right;System.out.println(node.data);}// 替换这个遍历的结点node = node.right;}

3.6 二叉树的应用

3.6.1 堆排序（见 2022.4.5 三、排序算法.md）

3.6.2 赫夫曼树

package com.gyh.tree;import com.gyh.sort.QuickSort2;import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;/*** @author Gao YongHao* @version 1.0*/
public class HuffmanTree {public static void main(String[] args) {int arr[] = {13, 7, 8, 3, 29, 6, 1};Node node = new HuffmanTree().toTree(arr);System.out.println(new HuffmanTree().wpl(node, 0));// 先序遍历结果new HuffmanTree().preOrder(node);}public void preOrder(Node n) {if (n == null) {return;}System.out.println(n.value);preOrder(n.left);preOrder(n.right);}/*** 计算带权路径长度** @param node 根结点* @param path 当前结点的路径长度* @return*/public int wpl(Node node, int path) {if (node == null) {return 0;} if (node.left == null && node.right == null) {return node.value * path; // 叶子结点的带权路径}return wpl(node.left, path + 1) + wpl(node.right, path + 1);}public Node toTree(int[] nums) {if (nums == null || nums.length <= 0) {return null;}//        // 从小到大排序
//        new QuickSort2().sort(nums, true);// 从小到大排序并转换为结点List<Node> nodes = Arrays.stream(nums).mapToObj(Node::new).collect(Collectors.toList());// 作几轮while (nodes.size() > 1) {// 从小到大排序nodes.sort(Comparator.comparingInt(x -> x.value));Node node1 = nodes.get(0);Node node2 = nodes.get(1);Node node = new Node(node1.value + node2.value, node1, node2);// 将计算后的结点加入剩余的元素集合中nodes.remove(0);nodes.remove(0);nodes.add(node);}return nodes.get(0);}}class Node {int value;Node left;Node right;public Node(int value, Node left, Node right) {this.value = value;this.left = left;this.right = right;}public Node(int value) {this.value = value;}@Overridepublic String toString() {return "Node{" +"value=" + value +'}';}
}

3.6.3 赫夫曼编码

package com.gyh.tree;import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;/*** @author Gao YongHao* @version 1.0*/
public class HuffmanEncode {public static void main(String[] args) {String content = "i like like like java do you like a java";// 分别统计每个字符的频度String[] contentStr = content.split("");Map<String, Long> statistic = Stream.of(contentStr).collect(Collectors.groupingBy(m -> m, Collectors.counting()));HuffmanEncode huffmanEncode = new HuffmanEncode();CodeNode root = huffmanEncode.createHuffmanTree(statistic);huffmanEncode.getCode(root);}public void getCode(CodeNode node) {getCode(node, "");}// 获取每个字符的霍夫曼编码（叶子结点作显示）private void getCode(CodeNode node, String prefix) {if (node == null) {return;}if (node.left == null && node.right == null) {System.out.println(node.data + "---->" + prefix);return;}getCode(node.left, prefix + "0");getCode(node.right, prefix + "1");}public CodeNode createHuffmanTree(Map<String, Long> statistic) {// 创建结点listList<CodeNode> nodes = statistic.entrySet().stream().map(s -> new CodeNode(s.getKey(), s.getValue().intValue())).collect(Collectors.toList());while (nodes.size() > 1) {// 从小到大排序nodes.sort(Comparator.comparingInt(x -> x.weight));CodeNode left = nodes.get(0);CodeNode right = nodes.get(1);CodeNode codeNode = new CodeNode(null, left.weight + right.weight, left, right);// 将新结点加入到集合中nodes.remove(0);nodes.remove(0);nodes.add(codeNode);}return nodes.get(0);}
}class CodeNode {String data; // 存放数据本身int weight; // 权值，表示数据频度CodeNode left;CodeNode right;public CodeNode(String data, int weight, CodeNode left, CodeNode right) {this.data = data;this.weight = weight;this.left = left;this.right = right;}public CodeNode(String data, int weight) {this.data = data;this.weight = weight;}
}

3.6.4 二叉排序树（见：四、查找算法）