目录
树的概述
一、为什么需要树这种数据结构
1、数组存储方式分析
优点：通过下标访问，速度快，对有序数组，还可以使用二分查找提高效率
缺点：如果检索某个值，或插入值（按一定顺序）要整体移动，效率低
2、链式存储方式分析
优点：在一定程度上对数组优化（插入删除这些效率高）
缺点：检索时，效率仍然较低，比如找某个值，需要从头到尾遍历
3、树存储方式的分析
能提高数据存储，读取存储的效率，比如利用二叉排序树，既保证数据检索速度，同时也能保证增删改查的速度
二、树的常用术语
二叉树
一、二叉树的概念
1、数有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树
2、二叉树的子节点分为左节点和右节点
3、如果二叉树的所有节点都在最后一层，并且节点总数=2n次方-1，n为层数，则为满二叉树
4、如果二叉树所有节点都在最后一层或者倒数第二层，而且最后一层的叶子节点左连续，倒数第二层叶子节点右连续，称完全二叉树
二、二叉树的遍历
思路分析
前序遍历：先输出父节点，再遍历左子树和右子树
中序遍历：先遍历左子树，在输出父节点，再遍历右子树
后序遍历：先遍历左子树，再遍历右子树，最后输出父节点
小结：父节点的顺序，就能确定是哪种遍历
代码实现
public class BinaryTreeDemo {
public static void main(String[] args) {
//先创建一个二叉树
BinaryTree binaryTree = new BinaryTree();
HeroNode root = new HeroNode(1,"关羽");
HeroNode node2 = new HeroNode(2,"赵云");
HeroNode node3 = new HeroNode(3,"曹操");
HeroNode node4 = new HeroNode(4,"张飞");
HeroNode node5 = new HeroNode(5,"刘备");
//我们先手动创建二叉树，后面我们学递归的方式创建
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
node3.setLeft(node5);
binaryTree.setRoot(root);
System.out.println("前序遍历: ");
binaryTree.preOrder();
System.out.println("中序遍历: ");
binaryTree.infixOrder();
System.out.println("后序遍历: ");
binaryTree.postOrder();
}
}
//定义BinaryTree 二叉树
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 infixOrder(){
if (this.root!=null){
this.root.infixOrder();
}else{
System.out.println("二叉树为空 无法遍历");
}
}
//后序遍历
public void postOrder(){
if (this.root!=null){
this.root.postOrder();
}else{
System.out.println("二叉树为空 无法遍历");
}
}
}
//先创建HeroNode节点
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;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public HeroNode getLeft() {
return left;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public HeroNode getRight() {
return right;
}
public void setRight(HeroNode right) {
this.right = right;
}
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 infixOrder(){
//递归向左子树前序遍历
if (this.left != null){
this.left.infixOrder();
}
//输出父节点
System.out.println(this);
//递归向右子树前序遍历
if (this.right !=null){
this.right.infixOrder();
}
}
//后序遍历的方法
public void postOrder(){
//递归向左子树前序遍历
if (this.left != null){
this.left.postOrder();
}
//递归向右子树前序遍历
if (this.right !=null){
this.right.postOrder();
}
//输出父节点
System.out.println(this);
}
}三、前中后序查找
思路分析
?代码实现
public class BinaryTreeDemo {
public static void main(String[] args) {
//先创建一个二叉树
BinaryTree binaryTree = new BinaryTree();
HeroNode root = new HeroNode(1,"关羽");
HeroNode node2 = new HeroNode(2,"赵云");
HeroNode node3 = new HeroNode(3,"曹操");
HeroNode node4 = new HeroNode(4,"张飞");
HeroNode node5 = new HeroNode(5,"刘备");
//我们先手动创建二叉树，后面我们学递归的方式创建
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
node3.setLeft(node5);
binaryTree.setRoot(root);
System.out.println("前序遍历: ");
binaryTree.preOrder();
System.out.println("中序遍历: ");
binaryTree.infixOrder();
System.out.println("后序遍历: ");
binaryTree.postOrder();
//前序遍历
HeroNode resNode = binaryTree.preOrderSearch(5);
if (resNode != null){
System.out.printf("找到了，信息为"+resNode.getNo()+" "+resNode.getName());
}else {
System.out.println("没有找到该英雄");
}
}
}
//定义BinaryTree 二叉树
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 infixOrder(){
if (this.root!=null){
this.root.infixOrder();
}else{
System.out.println("二叉树为空 无法遍历");
}
}
//后序遍历
public void postOrder(){
if (this.root!=null){
this.root.postOrder();
}else{
System.out.println("二叉树为空 无法遍历");
}
}
//前序遍历查找
public HeroNode preOrderSearch(int no){
if (root!=null){
return root.preOrderSearch(no);
}else {
return null;
}
}
//中序遍历查找
public HeroNode infixOrderSearch(int no){
if (root!=null){
return root.infixOrderSearch(no);
}else {
return null;
}
}
//后序遍历查找
public HeroNode postOrderSearch(int no){
if (root!=null){
return root.postOrderSearch(no);
}else {
return null;
}
}
}
//先创建HeroNode节点
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;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public HeroNode getLeft() {
return left;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public HeroNode getRight() {
return right;
}
public void setRight(HeroNode right) {
this.right = right;
}
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 infixOrder(){
//递归向左子树前序遍历
if (this.left != null){
this.left.infixOrder();
}
//输出父节点
System.out.println(this);
//递归向右子树前序遍历
if (this.right !=null){
this.right.infixOrder();
}
}
//后序遍历的方法
public void postOrder(){
//递归向左子树前序遍历
if (this.left != null){
this.left.postOrder();
}
//递归向右子树前序遍历
if (this.right !=null){
this.right.postOrder();
}
//输出父节点
System.out.println(this);
}
//前序遍历查找
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 infixOrderSearch(int no){
//判断左节点是否为空 如果不为空 则递归前序查找
//如果左递归找到则返回
HeroNode resNode = null;
if (this.left!=null){
resNode = this.left.infixOrderSearch(no);
}
if (resNode!=null){//说明左子树找到了
return resNode;
}
//比较当前是不是
if (this.no==no){
return this;
}
//判断右节点是否为空 如果不为空 则递归前序查找
if (this.right!=null){
resNode = this.right.infixOrderSearch(no);
}
return resNode;
}
//后序查找
public HeroNode postOrderSearch(int no){
//判断左节点是否为空 如果不为空 则递归前序查找
//如果左递归找到则返回
HeroNode resNode = null;
if (this.left!=null){
resNode = this.left.postOrderSearch(no);
}
if (resNode!=null){//说明左子树找到了
return resNode;
}
//判断右节点是否为空 如果不为空 则递归前序查找
if (this.right!=null){
resNode = this.right.postOrderSearch(no);
}
if (resNode!=null){//说明右子树找到了
return resNode;
}
//比较当前是不是
if (this.no==no){
return this;
}
return resNode;
}
}四、删除节点
要求
- 如果删除的节点是叶子节点，则直接删除该节点
- 如果删除节点是非叶子节点，则删除该子树
- 测试，删除掉5号叶子节点和3号子树
思路分析
- 因为我们的二叉树是单向的，所有我们是判断当前结点的子节点是否需要删除节点，而不能去判断当前结点是不是需要删除的节点
- 如果当前节点的左子树不为空，并且左子节点就是要删除的节点，就将this.left = null
- 如果当前结点的右子节点不为空，并且右子节点就是要删除的节点，就将this.right = null
- 如果2和3都没有删除节点，那么就要向左子树进行递归删除
- 如果4也没有删除，则向右子树递归删除
- 考虑如果数是空树3root，如果只有一个root节点，则等价于将二叉树置空
代码实现
在heroNode类中新增方法delNode（递归删除节点）
//递归删除节点
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);
}
}在BinaryTree类中添加方法delNode（int no）
public void delNode(int no){
if (root!=null){
//先判断本节点是不是 因为方法只能判断根节点下面的节点
if (root.getNo() == no){
root = null;
}else {
root.delNode(no);
}
}else {
System.out.println("这是一个空树，无法删除");
}
}main方法中测试
System.out.println("删除前");
binaryTree.preOrder();
binaryTree.delNode(5);
System.out.println("删除后");
binaryTree.preOrder();顺序存储二叉树
顺序存储二叉树的概念
?顺序存储二叉树的特点
- 顺序二叉树通常只考虑完全二叉树
- 第n个元素的左子节点为2*n+1
- 第n个元素的右子节点为2*n+2
- 第n个元素的父节点为(n-1)/2
n表示二叉树中的第几个元素（按零开始，编号如图所示）
代码实现
只有前序遍历的，中序遍历和后续遍历就是位置换一下 其他是一样的
public class ArrBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7};
//创建一个ArrBinaryTree
ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
arrBinaryTree.preOrder(0); //前序遍历
}
}
//编写ArrayBinaryTree 实现顺序存储二叉树遍历
class ArrBinaryTree{
private int[] arr; //存储数据节点的数组
public ArrBinaryTree(int[] arr) {
this.arr = arr;
}
//重载preOrder
public void preOrder(){
this.preOrder(0);
}
//编写一个方法，完全顺序存储二叉树的前序遍历
public void preOrder(int index){
//如果数组为空，或者arr.length = 0
if (arr ==null || arr.length == 0){
System.out.println("数组为空,不能前序遍历");
}
//输出当前这个元素
System.out.println(arr[index]);
//向左递归遍历
if ((index*2+1)<arr.length){
preOrder(2*index+1);
}
//向右递归遍历
if ((index*2+2)< arr.length){
preOrder(2*index+2);
}
}
}?线索化二叉树
n个节点的二叉链表中含有n+1个空指针域（没有指向节点的指针，每个节点都有两个指针，叶子节点两个空指针域），利用二叉链表中空指针域，存放该节点在某种遍历次序下的前驱和后继节点的指针，称线索。
线索二叉树构建和遍历
说明：对前面的中序线索化的二叉树进行遍历
因为线索化后，各个节点的指向有所改变，所以原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线性方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致
代码实现
public class ThreadedBinaryTree {
public static void main(String[] args) {
//测试中序线索二叉树的功能
HeroNode root = new HeroNode(1, "Tom");
HeroNode node2 = new HeroNode(3, "jack");
HeroNode node3 = new HeroNode(6, "smith");
HeroNode node4 = new HeroNode(8, "mary");
HeroNode node5 = new HeroNode(10, "king");
HeroNode node6 = new HeroNode(14, "dim");
root.setLeft(node2);
root.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
//测试线索化
BinaryTree binaryTree = new BinaryTree();
binaryTree.setRoot(root);
binaryTree.threadedNodes();
//以10号节点为例
HeroNode leftNode = node5.getLeft();
HeroNode rightNode = node5.getRight();
System.out.println("10号节点的前驱节点是=" + leftNode);
System.out.println("10号节点的后继节点是=" + rightNode);
//线索化的方式遍历线索化二叉树
System.out.println("线索化的方式遍历线索化二叉树");
binaryTree.threadedList();//8->3->10->1->14->6
}
}
//定义ThreadedBinaryTree实现了线索化功能的二叉树
class BinaryTree {
private HeroNode root;
//再递归进行线索化时，这个pre总是保留前一个节点
private HeroNode pre = null;
public void setRoot(HeroNode root) {
this.root = root;
}
//重载
public void threadedNodes() {
this.threadedNodes(root);
}
//遍历线索化二叉树的方法
public void threadedList() {
//定义临时存储变量node
HeroNode node = root;
while (node != null) {
//循环的找到leftType==1的节点，第一个找到的应该是8
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();
}
}
//建立中序线索化二叉树方法
/**
* @param node 当前需要线索化的节点
*/
public void threadedNodes(HeroNode node) {
//如果当前节点为空
if (node == null) {
return;
}
//(1)先线索化左子树
threadedNodes(node.getLeft());
//(2)线索化当前节点[有难度]
/*先处理当前节点的前驱节点*/
/*以8节点为例:8.left = null;8.letfType = 1*/
if (node.getLeft() == null) {
//让当前节点的左指针指向前驱节点
node.setLeft(pre);
//并且修改当前节点的左指针的类型,指向前驱节点
node.setLeftType(1);
}
/*再处理后继节点*/
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
//每处理一个节点后，让当前节点是下一个节点的前驱节点
pre = node;
//(3)再线索化右子树
threadedNodes(node.getRight());
}
}
?二叉排序树
一、二叉排序树介绍
我们先看需求
要求给一个数组（7,3,10,12,5,1,9）要求能高效的完成对数据的查询和添加
解决方案分析
数组没有排序，优点：直接数组尾添加，速度快。缺点：查询速度慢
数组有序，优点：可以使用二分查找，查找速度快。缺点：为了保证数组有序，在添加新数据，找到插入位置后，后面的数据整体移动，速度慢
使用链式存储-链表，不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动
这时候我们就可以使用?二叉排序树?
二叉排序树：对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点小，右子节点的值比当前节点的值大。
特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点
比如说我们在下面二叉树插入2，对应二叉排序树为：
二、二叉排序树创建和遍历
什么都不用说，我们直接上代码
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();
}
}
//创建二叉排序树
class BinarySortTree{
private Node root;
//添加节点的方法
public void add(Node node){
if (root == null){
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;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
//添加节点
//递归的形式添加节点，注意需要满足二叉排序树要求
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);
}
}
}
//中序遍历
public void infixOrder(){
if (this.left!=null){
this.left.infixOrder();
}
System.out.println(this);
if (this.right!=null){
this.right.infixOrder();
}
}
}最后看输出结果我们发现，只要是二叉排序树，中序遍历出来就是顺序的
?三、二叉排序树的删除
二叉排序树的删除情况比较复杂，下面有三种情况要考虑
- 删除叶子节点 2、5、9、12
- 删除只有一颗子树的节点1
- 删除有两颗子树的节点7、3、10
?
比如我们删10，就必须右子树找最小的11，然后把11的位置换到10?
代码实现
第一种情况（删除的节点是个叶子节点）
在node类新增方法
//查找要删除的节点
public Node search(int value){
if (value == this.value){
return this;
} else if (value<this.value) {
//如果左子节点为null就不用找且返回null
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;
}
}
}在tree类新增方法
//查找要删除的节点
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);
}
}
//删除节点
public void deNode(int value){
if (root == null){
return;
}else {
Node search = search(value);
if (search==null){
return;
}
//如果我们发现当前这颗二叉排序树只有一个节点
if (root.left==null && root.right==null){
root = null;
return;
}
//查找他的父节点
Node parent = searchParent(value);
if (search.left==null&&search.right==null){
if (parent.left!=null && parent.left.value == value){
parent.left = null;
} else if (parent.right!=null && parent.right.value == value) {
parent.right = null;
}
}
}
}main方法中测试?
binarySortTree.infixOrder();
//测试删除节点
binarySortTree.deNode(2);
binarySortTree.infixOrder();第二种情况（删除的节点有一个节点）
在node类的delNode中添加条件
//查找他的父节点
Node parent = searchParent(value);
if (search.left==null&&search.right==null){
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 (search.left!=null && search.right!=null) {
//剩下的就是只有一个节点的
}else {
//如果要删除的节点有左子节点
if (search.left!= null){
if (parent.left.value==value){
parent.left = search.left;
}else { //说明是右子节点
parent.right = search.left;
}
}else { //要删除的节点有右子及节点
if (parent.left.value==value){
parent.left = search.right;
}else { //说明是右子节点
parent.right = search.right;
}
}
}?我们还需要考虑一种情况 要删除的节点没有父节点时
//如果要删除的节点有左子节点
if (search.left!= null){
if(parent!=null){
if (parent.left.value==value){
parent.left = search.left;
}else { //说明是右子节点
parent.right = search.left;
}
}else {
root=search.left;
}
}else { //要删除的节点有右子及节点
if (parent!= null) {
if (parent.left.value==value){
parent.left = search.right;
}else { //说明是右子节点
parent.right = search.right;
}
}else {
root=search.right;
}
}第三种情况（删除的节点有两个子节点）
我们可以把要删除的右子数里找最小的节点替换删除的
也可以在左子树找最大的替换删除的节点
//查找父节点
public Node searchParent(int value){
if (root == null){
return null;
}else {
return root.searchParent(value);
}
}
// node当做二叉排序树的根节点，返回以node为根节点的二叉排序树的最小结点的值
public int delRightTreeMin(Node node){
Node target = node;
while (target.left!= null){
target = target.left;
}
//这时target就指向最小节点
//删除最小结点
deNode(target.value);
return target.value;
}
//删除节点
public void deNode(int value){
if (root == null){
return;
}else {
Node search = search(value);
if (search==null){
return;
}
//如果我们发现当前这颗二叉排序树只有一个节点
if (root.left==null && root.right==null){
root = null;
return;
}
//查找他的父节点
Node parent = searchParent(value);
if (search.left==null&&search.right==null){
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 (search.left!=null && search.right!=null) {
int minVal = delRightTreeMin(search.right);
search.value = minVal;
//剩下的就是只有一个节点的
}else {
//如果要删除的节点有左子节点
if (search.left!= null){
if (parent.left.value==value){
parent.left = search.left;
}else { //说明是右子节点
parent.right = search.left;
}
}else { //要删除的节点有右子及节点
if (parent.left.value==value){
parent.left = search.right;
}else { //说明是右子节点
parent.right = search.right;
}
}
}
}
}赫夫曼树
给定n个权值作为n个叶子节点，构造一颗二叉树，若带权路径长度达到最小WPL，称二叉树为最优二叉树，也叫赫夫曼树
赫夫曼树是带权路径长度最短的树，权值较大的节点离根较近
重要概念
?
思路分析
- 从小到大进行排序，将每个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树
- 取出根节点权值最小的两颗二叉树
- 组成一颗新的二叉树，该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
- 再将这颗新二叉树，以根节点权值大小排序，不断重复1234，直到所有数据处理
代码实现
public class huffmanTree {
public static void main(String[] args) {
int arr[]={13,7,8,3,29,6,1};
Node root = createHuffmanTree(arr);
preOrder(root);
}
//编写一个前序遍历方法
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);
System.out.println(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;
//从ArrayList中删除已经处理过的二叉树
nodes.remove(left);
nodes.remove(right);
//将新的二叉树加入集合
nodes.add(parent);
//排序
Collections.sort(nodes);
}
return nodes.get(0);
}
}
class Node implements Comparable<Node>{
int value; //权值
Node left;
Node right;
//前序遍历
public void preOrder(){
System.out.println(this);
if (this.left!=null){
this.left.preOrder();
}
if (this.right!=null){
this.right.preOrder();
}
}
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
@Override
public int compareTo(Node o) {
//从小到大排序
return this.value - o.value;
}
}赫夫曼编码
赫夫曼编码是一种编码方式，属于程序算法，广泛用于数据文件压缩，压缩率在20%~90%
?
?注意：赫夫曼树根据排序方法的不同，也可能不太一样，比如大的方左边，这样对赫夫曼编码也不一样，但是wpl是一样的，都是最小的。最后生成的赫夫曼编码长度也是一样的。
平衡二叉树（AVL树）
?平衡二叉树也叫平衡二叉搜索树，AVL树。可以保证查询效率较高
他是一颗空树或他的左右两个子树的高度差绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。实现方法有：红黑树、AVL 、替罪羊树、Treap、伸展树等
一、左旋转
代码实现
首先写出计算树高度的方法
// 返回 以该结点为根结点的树的高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
// 返回左子树的高度
public int leftHeight() {
if (left == null) {
return 0;
}
return left.height();
}
// 返回右子树的高度
public int rightHeight() {
if (right == null) {
return 0;
}
return 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;
}
?二、右旋转
代码实现?
右旋转的方法?
当左子树的高度 - 右子树的高度 > 1的时候
//右旋转
private void rightRotate() {
//创建新的结点，以当前根结点的值
Node newNode = new Node(value);
// 新节点的右子树设置为当前节点的右子树
newNode.right = right;
// 新节点的左子树设置为当前节点的左子树的右子树
newNode.left = left.right;
// 当前的值设置为左子树的值
value = left.value;
// 当前节点的左子树设置为左子树的左子树
left = left.left;
// 当节点的右子树设置为新节点
right = newNode;
}三、双旋转
在某种情况下，有可能单次旋转并不能满足转换为平衡二叉树，比如这种：
?所以在这种情况下，我们可能就需要旋转两次了
思路分析
- 当符合右旋转的条件时
- 如果它的左子树的右子树的高度大于它的左子树的高度
- 那就先对当前的节点进行左旋转
- 再对当前结点进行右旋转即可
代码实现
//当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 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();
}
}多叉树
一、多叉树原理图解
1、二叉树的问题分析
二叉树需要加载到内存的，如果二叉树节点很多会出现：
- 在构建二叉树时候，需要多次进行io操作（海量数据存在数据库或文件中），节点海量，构建二叉树时，速度有影响
- 节点海量，造成二叉树高度很大，会降低操作速度
2、多叉树
3、b树
?二、2-3树
2-3树是最简单的B树结构，他通过重新组织节点可以降低树的高度，提高查找效率
- 2-3树的所有叶子节点都在同一层（只要是B树都满足这个条件）
- 有两个子节点的节点叫二节点。二节点要么没有节点，要么有两个节点，不能只有一个
- 有三个节点的节点叫三节点，三节点要么没有节点，要么有三个节点
- 2-3树是由二节点和三节点构成的树
- 三节点的三个子节点123,2要满足在两个父节点的值之间，如上面图2-3树10必须是8和12之间，7小于8和12,14大于8和12。
思路
?
?
三、B树
?B树介绍
?B-tree，平衡的意思Balanced。很多习惯把B-tree写成B-树，就是B树的意思。
数据存在整颗树里，不一定在叶子节点上
?B+树介绍
所有真实的数据都只存在叶子节点中
?B*树介绍
B*树是B+树的变体，在B+数的非根和非叶子节点增加指向兄弟的指针，一定程度上提高了我们的使用率。
