二叉树
为什么需要树这种数据结构
数组存储方式分析
- 优点：通过下标方式访问元素，速度快。对于有序数组，还可以使用二分查找提高检索速度。
- 缺点：如果要插入值（按一定顺序）会整体移动，效率低。
链式存储方式分析
- 优点：在一定程度上对数组存储方式有优化（比如，插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好）。
- 缺点：在进行检索时，效率仍然较低（比如，检索某个值，需要从头节点开始遍历）。
树存储方式分析
能提高数据存储、读取的效率。比如利用 二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改的速度。
二叉树的概念
- 树有很多种，每个节点最多只能有两个子节点的树称为二叉树。
- 二叉树的子节点分为左子节点和右子节点。
- 如果二叉树的所有叶子节点都在最后一层，并且节点总数时2n-1，n为层数，则我们称为满二叉树。
- 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二次的叶子节点在右边连续，我们称之为完全二叉树。
二叉树遍历
- 前序遍历（前根遍历）：先遍历根，再遍历左子树，再遍历右子树。
- 中序遍历（中根遍历）：先遍历左子树，再遍历根，最后遍历右子树。
- 后续遍历（后根遍历）：先遍历左子树，再遍历右子树，最后遍历根。
代码实现：
public class BinaryTreeDemo {
public static void main(String[] args) {
HeroNode root = new HeroNode(1, "宋江");
HeroNode node2 = new HeroNode(2, "吴用");
HeroNode node3 = new HeroNode(3, "卢俊义");
HeroNode node4 = new HeroNode(4, "林冲");
BinaryTree binaryTree = new BinaryTree();
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
binaryTree.setRoot(root);
binaryTree.preOrder();
}
}
class BinaryTree {
private HeroNode root;
public void setRoot(HeroNode root) {
this.root = root;
}
public void preOrder() {
if (this.root != null) {
this.root.preOrder();
} else {
System.out.println("二叉树为空，无法遍历");
}
}
public void midOrder() {
if (this.root != null) {
this.root.midOrder();
} else {
System.out.println("二叉树为空，无法遍历");
}
}
public void postOrder() {
if (this.root != null) {
this.root.postOrder();
} else {
System.out.println("二叉树为空，无法遍历");
}
}
}
class HeroNode {
private int no;
private String name;
private HeroNode left;
private HeroNode right;
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
// 省略 setter 和 getter方法
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
public void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
public void midOrder() {
if (this.left != null) {
this.left.midOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.midOrder();;
}
}
public void postOrder() {
if (this.left != null) {
this.left.postOrder();
}
if (this.right != null) {
this.right.postOrder();
}
System.out.println(this);
}
}
二叉树的查找
- 前序查找
- 中序查找
- 后序查找
代码实现：
package com.feng.tree;
public class BinaryTreeDemo {
public static void main(String[] args) {
HeroNode root = new HeroNode(1, "宋江");
HeroNode node2 = new HeroNode(2, "吴用");
HeroNode node3 = new HeroNode(3, "卢俊义");
HeroNode node4 = new HeroNode(4, "林冲");
BinaryTree binaryTree = new BinaryTree();
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
binaryTree.setRoot(root);
HeroNode heroNode = binaryTree.preOrderSearch(3);
System.out.println("前序查找:" + heroNode);
}
}
class BinaryTree {
private HeroNode root;
public void setRoot(HeroNode root) {
this.root = root;
}
// 前序查找
public HeroNode preOrderSearch(int no) {
if (root != null) {
return root.preOrderSearch(no);
}
return null;
}
// 中序查找
public HeroNode midOrderSearch(int no) {
if (root != null) {
return root.midOrderSearch(no);
}
return null;
}
// 后序查找
public HeroNode postOrderSearch(int no) {
if (root != null) {
return root.postOrderSearch(no);
}
return null;
}
}
class HeroNode {
private int no;
private String name;
private HeroNode left;
private HeroNode right;
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
// 省略setter 和 getter方法
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
public HeroNode preOrderSearch(int no) {
if (this.no == no) {
return this;
}
HeroNode resNode = null;
if (this.left != null) {
resNode = this.left.preOrderSearch(no);
}
if(resNode!=null) {
return resNode;
}
if (this.right != null) {
resNode = this.right.preOrderSearch(no);
}
return resNode;
}
public HeroNode midOrderSearch(int no) {
HeroNode resNode = null;
if (this.left != null) {
resNode = this.left.midOrderSearch(no);
}
if (resNode != null) {
return resNode;
}
if (this.no == no) {
return this;
}
if (this.right != null) {
resNode = this.right.midOrderSearch(no);
}
return resNode ;
}
public HeroNode postOrderSearch(int no) {
HeroNode resNode = null;
if (this.left != null) {
resNode = this.left.midOrderSearch(no);
}
if (resNode != null) {
return resNode;
}
if (this.right != null) {
resNode = this.right.midOrderSearch(no);
}
if (resNode != null) {
return resNode;
}
if (this.no == no) {
return this;
}
return resNode;
}
}
二叉树节点删除
- 约定
- 如果删除的是叶子节点，则删除该节点。
- 如果删除的是非叶子节点，则删除该子树。
代码实现：
public class BinaryTreeDemo {
public static void main(String[] args) {
HeroNode root = new HeroNode(1, "宋江");
HeroNode node2 = new HeroNode(2, "吴用");
HeroNode node3 = new HeroNode(3, "卢俊义");
HeroNode node4 = new HeroNode(4, "林冲");
BinaryTree binaryTree = new BinaryTree();
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
binaryTree.setRoot(root);
binaryTree.delNode(3);
System.out.println("删除后节点3之后的树");
binaryTree.preOrder();
}
}
class BinaryTree {
private HeroNode root;
public void setRoot(HeroNode root) {
this.root = root;
}
public void delNode(int no) {
if (root != null) {
if (root.getNo() == no) {
this.root = null; // 如果根节点即为要删除的节点，直接删除
} else {
this.root.delNode(no);
}
} else {
System.out.println("当前树为空");
}
}
public void preOrder() {
if (this.root != null) {
this.root.preOrder();
} else {
System.out.println("二叉树为空，无法遍历");
}
}
}
class HeroNode {
private int no;
private String name;
private HeroNode left;
private HeroNode right;
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
// 省略 getter setter 方法
// 省略 toString 方法
public void delNode(int no) {
if (this.left != null && this.left.no == no) { // 如果当前节点的左子节点 恰好为要删除的节点
this.left = null;
return;
}
if (this.right != null && this.right.no == no) {// 如果当前节点的右子节点 恰好为要删除的节点
this.right = null;
return;
}
if (this.left != null) { // 如果左子节点不为空，递归查找
this.left.delNode(no);
}
if (this.right != null) { // 如果右子节点不为空，递归查找
this.right.delNode(no);
}
}
}
顺序存储二叉树（堆排序中会使用）
- 概念：从数据存储来看，数据存储方式和树的存储方式可以相互转换，即 数组可以转换成树，树也可以转换成数组。如图：
- 特点
- 顺序二叉树通常只考虑完全二叉树。
- 第n个元素的左子节点为 2*n+1
- 第n个元素的右子节点为 2*n+2
- 第n个元素的父节点为 (n-1)/2
- 代码实现
/** * 二叉树以数组方式存放 * 以二叉树的前序遍历数组 */ public class ArrBinaryTreeDemo { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5, 6, 7}; ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr); arrBinaryTree.preOrder(0); System.out.println(); } } class ArrBinaryTree { private int[] arr; public ArrBinaryTree(int[] arr) { this.arr = arr; } // 数组的下标 public void preOrder(int index) { if (arr == null || arr.length == 0) { System.out.println("数组为空，不能遍历"); return; } System.out.printf("%d ", arr[index]); if (index * 2 + 1 < arr.length) { preOrder(index * 2 + 1); } if (index * 2 + 2 < arr.length) { preOrder(index * 2 + 2); } } }
线索化二叉树
- 基本介绍
- n个节点的二叉链表中含有n+1个空指针域【4的左右、5的左右、6的左右、7的右】。利用二叉链表中的空指针域，存放指向该节点在某种遍历次序下的前驱和后继节点的指针（这种附加的指针称为“线索”）
- 这种加了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。根据线索性质的不同，线索二叉树又可分为前序线索二叉树、中序线索二叉树和后序线索二叉树。
- 一个节点的前一个结点，称为前驱结点。
- 一个结点的后一个结点，称为后继结点。
- 二叉树中序遍历，线索化后
当线索二叉树后，Node结点的属性left和right的情况：
- left指向的是左子树，可也能是指向前驱结点。
- right指向的是右子树，也可能是指向后继结点。
- 代码实现：
public class ThreadedBinaryTreeDemo { public static void main(String[] args) { HeroNode root = new HeroNode(1, "jack"); HeroNode node2 = new HeroNode(3, "tom"); HeroNode node3 = new HeroNode(6, "lusi"); HeroNode node4 = new HeroNode(8, "tom"); HeroNode node5 = new HeroNode(10, "kity"); HeroNode node6 = new HeroNode(14, "mask"); root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree(); threadedBinaryTree.setRoot(root); threadedBinaryTree.threadedNodes(); // 以node5做测试，查看其左右节点的值 HeroNode leftNode = node5.getLeft(); HeroNode rightNode = node5.getRight(); System.out.println(leftNode); System.out.println(rightNode); System.out.println("遍历线索化后的二叉树"); threadedBinaryTree.threadedList(); } } class ThreadedBinaryTree { private HeroNode root; private HeroNode pre; public void setRoot(HeroNode root) { this.root = root; } public void threadedNodes() { this.threadedNodes(root); } // 遍历线索化二叉树 public void threadedList() { HeroNode node = root; while (node != null) { // 一直找，直到找到type为1的节点 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(); } } public void threadedNodes(HeroNode node) { if (node == null) { return; } threadedNodes(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; threadedNodes(node.getRight()); } } class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; // 如果leftType == 0, 表示指向的是左子树，如果是１表示指向的是前驱节点 // 如果rightType == 0, 表示指向的是右子树，如果是１表示指向的是后继节点 private int leftType; private int rightType; public HeroNode(int no, String name) { this.no = no; this.name = name; } // 省略getter和setter方法 @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", leftType=" + leftType + ", rightType=" + rightType + '}'; } }
赫夫曼树
- 简要说明
- 给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树或霍夫曼树。
- 赫夫曼树是带权路径长度最短的树，权值较大的结点离根很近。
- 重要概念
- 路径：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。
- 路径长度：通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
- 结点的权：若将书中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
- 结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。
- 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(Weighted Path Length)，权值越大的结点离根结点越近的二叉树才是最优二叉树。
- WPL最小的就是赫夫曼树。
- 赫夫曼树创建思路
给定一个数列{13，7，8，3，29，6，1}，要求转成一颗赫夫曼树。
- 从小到大进行排序，将每一个数据（每一个数据都是一个结点）看成是一颗最简单的二叉树。
- 取处根结点权值最小的两颗二叉树。
- 组成一颗新的二叉树，该新的二叉树的根结点的权值是前面两颗二叉树根结点权值的和。
- 再将这颗新的二叉树，以根结点的权值大小再次排序，不断重复 1~4的步骤。直到数列中，所有的数据都被处理，就得到一颗赫夫曼树。
- 代码实现：
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class HuffmanTreeDemo { public static void main(String[] args) { int[] arr = {13, 7, 8, 3, 29, 6, 1}; Node node = createHuffmanTree(arr); preOrder(node); } public static void preOrder(Node root) { if (root != null) { root.preOrder(); } else { System.out.println("赫夫曼树为空"); } } // 创建赫夫曼树的方法 public static Node createHuffmanTree(int[] arr) { List<Node> nodes = new ArrayList<>(); for (int value : arr) { nodes.add(new Node(value)); } while (nodes.size() > 1) { Collections.sort(nodes); Node leftNode = nodes.get(0); Node rightNode = nodes.get(1); Node parentNode = new Node(leftNode.value + rightNode.value); parentNode.left = leftNode; parentNode.right = rightNode; nodes.remove(leftNode); nodes.remove(rightNode); nodes.add(parentNode); } return nodes.get(0); } } // 为了让Node对象实现排序，需要实现Comparable接口 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 int compareTo(Node o) { return this.value - o.value; } @Override public String toString() { return "Node{" + "value=" + value + '}'; } }