1、二叉树
为什么需要树
- 数组的查找效率高，但是插入效率低。
- 链表的插入效率高，查找效率低。
需要一种数据结构来平衡查找与插入效率，使得查找速度和插入速度都能得到提升，因此有了树这种数据结构。
树的基本概念
二叉树的基本概念
满二叉树
如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n为层数，则我们称为满二叉树。
2
完全二叉树
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树
二叉树的遍历
前序遍历
中序遍历
后序遍历
先遍历左子节点，再遍历右子节点，最后遍历父节点
可以看出，前中后的区别在于父节点遍历的时机
前序遍历结果：1、2、3、4
中序遍历结果：2、1、3、4
后序遍历结果：2、4、3、1
实际代码
此代码使用手动的方式创建二叉树，使用递归的方式遍历二叉树
package Tree;/*** @author Voyager1* @create 2021-10-07 20:42*/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.setLeft(node5);node3.setRight(node4);binaryTree.setRoot(root);//测试前序遍历System.out.println("前序遍历：" );//1,2,3,5,4binaryTree.preOrder();//测试中序遍历System.out.println("中序遍历：");//2,1,5,3,4binaryTree.infixOrder();//测试后序遍历System.out.println("后序遍历：");//2,5,4,3,1binaryTree.postOrder();}static 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 节点static 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;}@Overridepublic 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 Demo5 {public static void main(String[] args) {TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);node1.left = node2;node1.right = node3;List<Integer> integers = preTraverse(node1);System.out.println("前序遍历结果");for (Integer integer : integers) {System.out.print(integer);System.out.print(" ");}System.out.println();List<Integer> integers2 = midTraverse(node1);System.out.println("中遍历结果");for (Integer integer : integers2) {System.out.print(integer);System.out.print(" ");}System.out.println();List<Integer> integers3 = lastTraverse(node1);System.out.println("后遍历结果");for (Integer integer : integers3) {System.out.print(integer);System.out.print(" ");}System.out.println();}/*** 使用迭代法对二叉树进行前序遍历* @param root 二叉树根节点* @return 遍历后的集合*/public static List<Integer> preTraverse(TreeNode root) {// 用于存放结果的集合List<Integer> result = new ArrayList<>();if (root == null) {return result;}// 栈，用于存放遍历的节点Stack<TreeNode> stack = new Stack<>();stack.push(root);// 遍历二叉树while (!stack.isEmpty()) {// 栈顶元素出栈，并放入集合中root = stack.pop();result.add(root.val);// 先遍历右子树，将其压栈if (root.right != null) {stack.push(root.right);}// 遍历左子树,压栈if (root.left != null) {stack.push(root.left);}}return result;}/*** 使用迭代法对二叉树进行中序遍历* @param root 二叉树根节点* @return 中序遍历结果集合*/public static List<Integer> midTraverse(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> stack = new Stack<>();while (root != null || !stack.isEmpty()) {// 节点压栈，并遍历其左子树while (root != null) {stack.push(root);root = root.left;}// 栈顶元素出栈，放入结果集合root = stack.pop();result.add(root.val);// 遍历该节点的右子树root = root.right;}return result;}/*** 使用迭代法的后序遍历* @param root 二叉树根节点* @return 后序遍历集合*/public static List<Integer> lastTraverse(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> stack = new Stack<>();// 保存放入集合的右子树，避免重复放入TreeNode pre = null;while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;}// 获取栈顶元素root = stack.pop();// 如果该元素没有右子树，或者右子树已近被遍历过了，就放入集合if (root.right == null || root.right == pre) {result.add(root.val);pre = root;root = null;} else {// 否则就继续遍历该节点的右子树stack.push(root);root = root.right;}}return result;}}运行结果前序遍历结果1 2 3中遍历结果2 1 3后遍历结果2 3 1
二叉树的查找
前、中、后序查找的思路与遍历相似，当找到对应的元素时，直接返回即可。
实现代码
package Tree;/*** @author Voyager1* @create 2021-10-07 20:42*/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.setLeft(node5);node3.setRight(node4);binaryTree.setRoot(root);//测试前序遍历System.out.println("前序遍历：" );//1,2,3,5,4binaryTree.preOrder();//测试中序遍历System.out.println("中序遍历：");//2,1,5,3,4binaryTree.infixOrder();//测试后序遍历System.out.println("后序遍历：");//2,5,4,3,1binaryTree.postOrder();System.out.println("###################################");//测试前序查找binaryTree.preOrderSearch(5);//4次//中序查找binaryTree.infixOrderSearch(5);//3次//后序查找binaryTree.postOrderSearch(5);//2次}static 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 void preOrderSearch(int no){System.out.println("前序查找：");HeroNode resNode = null;if (root != null){resNode = root.preOrderSearch(no);}else {System.out.println("未找到该元素");return;}if(resNode != null){System.out.println(resNode);System.out.println();}else {System.out.println("未找到该元素");System.out.println();}}//中序查找public void infixOrderSearch(int no){System.out.println("中序查找：");HeroNode resNode = null;if (root != null){resNode = root.infixOrderSearch(no);}else {System.out.println("未找到该元素");return;}if(resNode != null){System.out.println(resNode);System.out.println();}else {System.out.println("未找到该元素");System.out.println();}}//后续查找public void postOrderSearch(int no){System.out.println("后序查找：");HeroNode resNode = null;if (root != null){resNode = root.postOrderSearch(no);}else {System.out.println("未找到该元素");return;}if(resNode != null){System.out.println(resNode);System.out.println();}else {System.out.println("未找到该元素");System.out.println();}}}//先创建HeroNode 节点static 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;}@Overridepublic 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){System.out.println("进入前序遍历");//比较当前结点是不是,如果找到了，就返回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;}System.out.println("进入中序遍历");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;}System.out.println("进入后序遍历");if (this.no == no){return this;}return resNode;}}}
二叉树的删除
删除要求
- 如果删除的是叶子节点，则直接删除即可
-
删除思路
因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点
- 如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将 this.left = null; 并且就返回 (结束递归删除)
- 如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将 this.right= null ;并且就返回 (结束递归删除)
- 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
- 如果 4步也没有删除结点，则应当向右子树进行递归删除
实现代码
public class Demo3 {public static void main(String[] args) {//创建根节点BinaryDeleteTree deleteTree = new BinaryDeleteTree();//手动创建节点StudentNode student1 = new StudentNode(1, "A");StudentNode student2 = new StudentNode(2, "B");StudentNode student3 = new StudentNode(3, "C");StudentNode student4 = new StudentNode(4, "D");StudentNode student5 = new StudentNode(5, "E");student1.setLeft(student2);student1.setRight(student3);student2.setLeft(student4);student3.setRight(student5);//指定根节点deleteTree.setRoot(student1);//删除节点deleteTree.deleteNode(3);}}class BinaryDeleteTree {StudentNode root;public void setRoot(StudentNode root) {this.root = root;}/*** 删除节点* @param id 删除节点的id*/public void deleteNode(int id) {System.out.println("删除节点");if(root.id == id) {root = null;System.out.println("根节点被删除");return;}//调用删除方法root.deleteNode(id);}}class StudentNode {int id;String name;StudentNode left;StudentNode right;public StudentNode(int id, String name) {this.id = id;this.name = name;}public int getId() {return id;}public void setId(int id) {this.id = id;}public String getName() {return name;}public void setName(String name) {this.name = name;}public StudentNode getLeft() {return left;}public void setLeft(StudentNode left) {this.left = left;}public StudentNode getRight() {return right;}public void setRight(StudentNode right) {this.right = right;}@Overridepublic String toString() {return "StudentNode{" +"id=" + id +", name='" + name + '\'' +'}';}/*** 删除节点* @param id 删除节点的id*/public void deleteNode(int id) {//如果左子树不为空且是要查找的节点，就删除if(left != null && left.id == id) {left = null;System.out.println("删除成功");return;}//如果右子树不为空且是要查找的节点，就删除if(right != null && right.id == id) {right = null;System.out.println("删除成功");return;}//左递归，继续查找if(left != null) {left.deleteNode(id);}//右递归，继续查找if(right != null) {right.deleteNode(id);}}}
顺序存储二叉树
基本说明
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组
特点
- 顺序二叉树通常只考虑完全二叉树
- 第 n个元素的左子节点为 2 × n + 1
- 第 n个元素的右子节点为 2 × n + 2
- 第 n个元素的父节点为 (n-1) ÷2
- 其中n 表示二叉树中的第几个元素(从0开始编号)
实现代码
package Tree;
/**
* @author Voyager1
* @create 2021-10-08 11:06
*/
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();
}
static class ArrBinaryTree{
private int[] arr;
public ArrBinaryTree(int[] arr) {
this.arr = arr;
}
public void preOrder(){
this.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(){
this.infixOrder(0);
}
/**
* 中序遍历
* @param index 数组下标
*/
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(){
this.postOrder(0);
}
/**
* 后序遍历
* @param index
*/
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
线索化二叉树
基本概念
因为一般的二叉树，叶子节点的左右指针都为空，这样就会造成空间的浪费。为了减少浪费，便有了线索化二叉树
- n个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针
- 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树
- 根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
- 如果一个节点已经有了左右孩子，那么该节点就不能被线索化了，所以线索化二叉树后，节点的left和right有如下两种情况
- left可能指向的是左孩子，也可能指向的是前驱节点
- right可能指向的是右孩子，也可能指向的是后继节点
图解
实现代码
线索化思路
- 每个节点需要用两个变量来表示左右指针的类型（保存左右子树，还是前驱后继）
- 需要用两个变量来表示当前节点和当前节点的前驱节点
- 通过将当前节点的左指针指向前驱节点，来实现前驱节点的绑定
- 通过将前驱节点的右指针指向当前节点，来实现后继节点的绑定
遍历方式
- 各个节点可以通过线性的方式遍历，无需使用递归的方式遍历
- 首先有一个外循环，代替递归操作，循环条件的暂存节点不为空
- 第一个内循环用于找到第一个元素，然后打印
- 第二个循环用于找到节点的后继元素
- 最后将暂存节点令为右孩子
public class Demo1 {
public static void main(String[] args) {
//初始化节点
Student student1 = new Student(1, "1");
Student student2 = new Student(2, "3");
Student student3 = new Student(3, "6");
Student student4 = new Student(4, "8");
Student student5 = new Student(5, "10");
Student student6 = new Student(6, "14");
//手动创建二叉树
ThreadedBinaryTree tree = new ThreadedBinaryTree();
student1.setLeft(student2);
student1.setRight(student3);
student2.setLeft(student4);
student2.setRight(student5);
student3.setLeft(student6);
tree.setRoot(student1);
tree.midThreaded();
//得到第五个节点的前驱节点和后继节点
System.out.println("第五个节点的前驱节点和后继节点");
System.out.println(student5.getLeft());
System.out.println(student5.getRight());
//遍历线索化二叉树
System.out.println("遍历线索化二叉树");
tree.midThreadedTraverse();
}
}
class ThreadedBinaryTree {
private Student root;
/**
* 指向当前节点的前一个节点
*/
private Student pre;
public void setRoot(Student root) {
this.root = root;
}
/**
* 中序线索化
* @param node 当前节点
*/
private void midThreaded(Student node) {
if(node == null) {
return;
}
//左线索化
midThreaded(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;
//右线索化
midThreaded(node.getRight());
}
public void midThreaded() {
midThreaded(root);
}
/**
* 遍历线索化后的二叉树
*/
public void midThreadedTraverse() {
//暂存遍历到的节点
Student tempNode = root;
//非递归的方法遍历，如果tempNode不为空就一直循环
while(tempNode != null) {
//一直访问二叉树的左子树，直到某个节点的左子树指向前驱节点
while(tempNode.getLeftType() != 1) {
tempNode = tempNode.getLeft();
}
//找到了第一个节点
System.out.println(tempNode);
//再访问该节点的右子树，看是否保存了后继节点
//如果是，则打印该节点的后继节点信息
while(tempNode.getRightType() == 1) {
tempNode = tempNode.getRight();
System.out.println(tempNode);
}
tempNode = tempNode.getRight();
}
}
}
class Student {
private int id;
private String name;
private Student left;
private Student right;
/**
* 左、右指针的类型，0-->指向的是左右孩子，1-->指向的是前驱、后续节点
*/
private int leftType = 0;
private int rightType = 0;
public Student(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Student getLeft() {
return left;
}
public void setLeft(Student left) {
this.left = left;
}
public Student getRight() {
return right;
}
public void setRight(Student right) {
this.right = right;
}
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;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
运行结果
第五个节点的前驱节点和后继节点
Student{id=2, name='3'}
Student{id=1, name='1'}
遍历线索化二叉树
Student{id=4, name='8'}
Student{id=2, name='3'}
Student{id=5, name='10'}
Student{id=1, name='1'}
Student{id=6, name='14'}
Student{id=3, name='6'}
2、树的应用
堆排序
package Tree;
import java.util.Arrays;
/**
* @author Voyager1
* @create 2021-10-11 16:39
*/
public class HeapSort {
public static void main(String[] args) {
int[] arr = {4, 6, 8, 5, 9};
heapSort(arr);
System.out.println("排序后=" + Arrays.toString(arr));
}
//堆排序方法
public static void heapSort(int arr[]){
int temp = 0;
System.out.println("堆排序");
//将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
for (int i = arr.length/2 -1;i >= 0;i--){
adjustHeap(arr,i, arr.length);
}
/*
* 2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，
* 反复执行调整+交换步骤，直到整个序列有序。
*/
for (int j = arr.length - 1; j > 0; j--){
//交换
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr,0,j);
}
}
/**
* 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆
* @param arr 待调整的数组
* @param i 表示非叶子结点在数组中索引
* @param length 表示对多少个元素继续调整， length 是在逐渐的减少
*/
public static void adjustHeap(int arr[],int i,int length){
int temp = arr[i];
//开始调整
//说明
//1. k = i * 2 + 1 k 是 i结点的左子结点
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
if (k + 1 <length && arr[k] < arr[k + 1]){//说明左子结点的值小于右子结点的值
k++;
}
if (arr[k] > temp){//如果子结点大于父结点
arr[i] = arr[k];//把较大的值赋给当前结点
i = k;//!!! i 指向 k,继续循环比较
}else {
break;
}
}
//当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)
arr[i] = temp;//将temp值放到调整后的位置
}
}
堆排序的时间复杂度为O(nlogn) 8w 随机数的排序 秒杀 80w依旧秒杀 800w 4秒
哈夫曼树
基本介绍
- 给定 n个权值作为 n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)
-
重要概念
路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为 L-1
- 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
- 结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积（W×L）
- 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和（W1×L1+W2×L2…），记为WPL(weighted pathlength) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
-
创建思路及图解
创建思路
从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
- 取出根节点权值最小的两颗二叉树
- 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
- 再将这颗新的二叉树，以根节点的权值大小 再次排序，不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
图解
以{3, 6, 7, 1, 8, 29, 13}为例
首先排序：{1, 3, 6, 7, 8, 13, 29}
实现代码
public class Demo1 {
public static void main(String[] args) {
int[] arr = {3, 6, 7, 1, 8, 29, 13};
HuffmanTree huffmanTree = new HuffmanTree();
Node root = huffmanTree.createHuffmanTree(arr);
root.preTraverse();
}
}
class HuffmanTree {
public Node createHuffmanTree(int[] arr) {
//创建数组用于存放Node
ArrayList<Node> nodes = new ArrayList<>(arr.length);
for(int value : arr) {
nodes.add(new Node(value));
}
//对集合中的元素进行排序
Collections.sort(nodes);
while(nodes.size() > 1) {
//左右子树在集合中对应的下标
int leftIndex = 0;
int rightIndex = 1;
//取出最小的两个节点
Node leftNode = nodes.get(leftIndex);
Node rightNode = nodes.get(rightIndex);
//创建父节点，并创建左右子树
Node parent = new Node(leftNode.value + rightNode.value);
parent.left = leftNode;
parent.right = rightNode;
//从集合中移除两个最小的节点，并将父节点放入集合中
nodes.add(parent);
nodes.remove(leftNode);
nodes.remove(rightNode);
//再次比较
Collections.sort(nodes);
}
//返回根节点
return nodes.get(0);
}
}
class Node implements Comparable<Node> {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
/**
* 重写比较函数，用于排序
*/
@Override
public int compareTo(Node o) {
return value - o.value;
}
public void preTraverse() {
System.out.print(this.value + " ");
if (this.left != null) {
this.left.preTraverse();
}
if (this.right != null) {
this.right.preTraverse();
}
}
}
运行结果
前序遍历哈夫曼树
67 29 38 15 7 8 23 10 4 1 3 6 13
哈夫曼编码
原理及图解
前缀编码：任何一个字符的编码，都不会是其它的字符的前缀
- 统计需编码的字符串中，各个字符出现的次数：如helloworld
- h:1 e:1 w:1 r:1 d:1 o:2 l:3
- 将字符出现的次数作为权值，构建哈弗曼树。如下图
- 根据哈弗曼树进行编码，向左的路径为0，向右的路径为1
- 字符编码结果为：h:000 e:001 w:100 d:1010 r:1011 l:11 o:01
- 字符串编码结果为：000001111101100011011111010
实现代码
此处代码只实现了哈弗曼树的创建与每个字符的编码 ```java public class Demo2 { public static void main(String[] args) { String str = “helloworld”; //哈夫曼编码 HuffmanCode huffmanCode = new HuffmanCode(); ArrayListlist = huffmanCode.getList(str); //构建哈弗曼树 Code root = huffmanCode.createHuffmanTree(list); System.out.println(“前序遍历哈弗曼树”); root.preTraverse(); //进行哈弗曼编码 Map
class HuffmanCode {
public ArrayList getList(String codes) {
//得到字符串对应的字节数组
byte[] byteCodes = codes.getBytes();
//创建哈希表，用于存放数据及其权值（出现次数）
Map<Byte, Integer> dataAndWight = new HashMap<>();
for(byte b : byteCodes) {
Integer wight = dataAndWight.get(b);
//如果还没有该数据，就创建并让其权值为1
if(dataAndWight.get(b) == null) {
dataAndWight.put(b, 1);
}else {
//如果已经有了该数据，就让其权值加一
dataAndWight.put(b, wight+1);
}
}
//创建List，用于返回
ArrayList<Code> list = new ArrayList<>();
//遍历哈希表，放入List集合中
for(Map.Entry<Byte, Integer> entry : dataAndWight.entrySet()) {
list.add(new Code(entry.getKey(), entry.getValue()));
}
return list;
}
public Code createHuffmanTree(ArrayList lists) {
int leftIndex = 0;
int rightIndex = 1;
//根据权值进行排序
Collections.sort(lists);
while (lists.size() > 1) {
Code leftCode = lists.get(leftIndex);
Code rightCode = lists.get(rightIndex);
Code parent = new Code(null,leftCode.weight + rightCode.weight);
parent.left = leftCode;
parent.right = rightCode;
lists.add(parent);
lists.remove(leftCode);
lists.remove(rightCode);
//再次排序
Collections.sort(lists);
}
return lists.get(0);
}
}
class Code implements Comparable {
Byte data;
int weight;
Code left;
Code right;
private Map codeMap = new HashMap<>();
public Code(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public String toString() {
return “Code{“ +
“data=” + data +
“, weight=” + weight +
‘}’;
}
public void preTraverse() {
System.out.println(this);
if(left != null) {
left.preTraverse();
}
if(right != null) {
right.preTraverse();
}
}
public Map getCodeMap() {
return getCode(this, “”, new StringBuilder());
}
/**
* 对哈弗曼树中的叶子节点进行编码
* @param node 根节点
* @param code 左子树为0，右子树为1
* @param stringBuilder 用于拼接的字符串
* @return
*/
private Map getCode(Code node, String code, StringBuilder stringBuilder) {
//新建拼接路径
StringBuilder appendCode = new StringBuilder(stringBuilder);
appendCode.append(code);
if(node != null) {
//如果是非叶子结点，就继续向下遍历
if(node.data == null) {
getCode(node.left, “0”, appendCode);
getCode(node.right, “1”, appendCode);
}else {
//如果是叶子节点，就将哈弗曼编码放入哈希表中
codeMap.put(node.data, appendCode.toString());
}
}
return codeMap;
}
@Override
public int compareTo(Code o) {
return weight - o.weight;
}
}
运行结果
前序遍历哈弗曼树
Code{data=null, weight=10}
Code{data=null, weight=4}
Code{data=null, weight=2}
Code{data=114, weight=1}
Code{data=100, weight=1}
Code{data=null, weight=2}
Code{data=101, weight=1}
Code{data=119, weight=1}
Code{data=null, weight=6}
Code{data=108, weight=3}
Code{data=null, weight=3}
Code{data=104, weight=1}
Code{data=111, weight=2}
每个字符对应的哈弗曼编码
{114=000, 100=001, 101=010, 119=011, 104=110, 108=10, 111=111}
<a name="h0pk3"></a>
### 二叉排序树
<a name="n1mif"></a>
#### 基本介绍
**二叉排序树**：BST: (Binary Sort(Search) Tree), 对于二叉排序树的**任何一个非叶子节点**，要求**左子节点的值比当前节点的值小，右子节点的值比当前节点的值大**
- **特别说明**：如果有相同的值，可以将该节点放在左子节点或右子节点
比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：<br />[](https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200729161543.png)
<a name="C9Rlk"></a>
#### 操作思路
**添加**
- 根据插入节点的值来寻找其应该插入的位置
- 新插入的节点都是**叶子节点**
**删除**<br />删除**叶子节点**（如删除值为2节点）
- 找到待删除的节点
- 找到待删除节点的父节点
- 判断待删除节点是其**父节点**的左孩子还是右孩子，然后让其令为空
删除**只有一颗子树的节点**（如删除值为1的节点）
- 找到待删除的节点
- 找到待删除的节点的父节点
- 判断待删除节点是其**父节点**的左孩子还是右孩子
- 判断待删除节点的**子树**是其左孩子还是右孩子
- 让父节点指向待删除节点的子树指向待删除节点的子树
删除有**两颗子树的节点**（如删除值为3的节点）
- 找到待删除的节点
- 找到待删除的节点的父节点
- 判断待删除节点是其**父节点**的左孩子还是右孩子
- 顺着待删除节点的**右子树**，找到一个值最小的节点（该值的大小最接近待删除节点的值）
- 让父节点指向待删除节点的子树指向上一步找到的最小的节点
删除**根节点**（如删除值为7的节点）
- 删除根结点的方法和删除有两个子树的方法相似
- 找到一个接近根节点值的节点
- 删除该节点，将该节点的值赋值给根节点即可
<a name="ZZWbf"></a>
#### 二叉排序树的创建和遍历
代码实现
```java
package Tree;
/**
* @author Voyager1
* @create 2021-10-12 15:45
*/
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]));
}
//中序遍历二叉排序树
System.out.println("中序遍历二叉排序树:");
binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12
}
}
//创建二叉排序树
class BinarySortTree{
private Node root;
public Node getRoot() {
return root;
}
//添加结点
public void add(Node node){
if (root == null){
root = node;
}else {
root.add(node);
}
}
//中序遍历
public void infixOrder(){
if (root == null){
System.out.println("二叉排序树为空，不能遍历");
}else {
root.infixOrder();
}
}
}
//创建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){
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();
}
}
}
二叉排序树的删除
package Tree;
/**
* @author Voyager1
* @create 2021-10-12 15:45
*/
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]));
}
//中序遍历二叉排序树
System.out.println("中序遍历二叉排序树:");
binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12
//测试删除节点
binarySortTree.delNode(2);
binarySortTree.delNode(5);
binarySortTree.delNode(3);
binarySortTree.delNode(10);
binarySortTree.delNode(1);
binarySortTree.delNode(7);
binarySortTree.delNode(9);
System.out.println("删除节点后中序遍历：");
binarySortTree.infixOrder();
}
}
//创建二叉排序树
class BinarySortTree{
private Node root;
public Node getRoot() {
return root;
}
//添加结点
public void add(Node node){
if (root == null){
root = node;
}else {
root.add(node);
}
}
//中序遍历
public void infixOrder(){
if (root == null){
System.out.println("二叉排序树为空，不能遍历");
}else {
root.infixOrder();
}
}
//查找要删除的节点
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);
}
}
//编写方法:
//1. 返回的 以node 为根结点的二叉排序树的最小结点的值
//2. 删除node 为根结点的二叉排序树的最小结点
public int delRightTreeMin(Node node){
Node target = node;
while (target.left != null){
target = target.left;
}
//这时 target就指向了最小结点
//删除最小结点
delNode(target.value);
return target.value;
}
//删除节点
public void delNode(int value){
if (root == null){
return;
}else {
//1.需求先去找到要删除的结点 targetNode
Node targetNode = search(value);
//如果没有找到要删除的结点
if (targetNode == null){
return;
}
//如果我们发现当前这颗二叉排序树只有一个结点
if (root.left == null && root.right == null){
return;
}
//找到targetNode的父结点
Node parent = searchParent(value);
//如果要删除的结点是叶子结点
if (targetNode.left == null && targetNode.right == null){
//判断targetNode 是父结点的左子结点，还是右子结点
if(parent != 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 (targetNode.left != null && targetNode.right != null){//删除有两颗子树的节点
int minVal = delRightTreeMin(targetNode);
targetNode.value = minVal;
}else {// 删除只有一颗子树的结点
//如果要删除的结点有左子结点
if (targetNode.left != null){
if (parent != null){
//如果 targetNode 是 parent 的左子结点
if (parent.left.value == value){
parent.left = targetNode.left;
}else {//targetNode 是 parent 的右子结点
parent.right = targetNode.left;
}
}else {
root = targetNode.left;
}
}else {//如果要删除的结点有右子结点
if (parent != null){
//如果 targetNode 是 parent 的左子结点
if (parent.left.value == value){
parent.left = targetNode.right;
}else {//targetNode 是 parent 的右子结点
parent.right = targetNode.right;
}
}else {
root = targetNode.right;
}
}
}
}
}
}
//创建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){
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();
}
}
/**
*查找要删除的节点
* @param value 希望删除的结点的值
* @return 如果找到返回该结点，否则返回null
*/
public Node search(int value){
if (this.value == value){
return this;
} else if (value < this.value){
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;
}
}
}
}
二叉排序树的注意事
如果删除的数10这个根节点 走到这一步时 会报空指针异常 所以需要加一个判断
修改方案如果
parent 判空
public void delNode(int value) {
if (root == null){
return;
}else {
// 1 先去找到要删除的节点 targetNode
Node targetNode = search(value);
if (targetNode == null){ //没有找到
return;
}
// 如果这颗二叉树只有一个 targetNode 节点
if (root.left == null && root.right == null){
root = null;
return;
}
// 去找到targetNode的父节点
Node parent = searchParent(value);
// 如果要删除的节点是叶子节点 左节点? 右节点
if (targetNode.left == null && targetNode.right == null){
if (parent.value > value){
parent.left = null;
}else {
parent.right = null;
}
}else if(targetNode.right != null && targetNode.left != null){ // 要删除的节点左右都有子节点
int min = delRightTreeMin(targetNode);
targetNode.value = min;
}else { // 删除只有一颗子树的接单
// 如果要删除的这个节点有左子节点
if (targetNode.left != null){
if (parent != null) {
if (parent.left.value == targetNode.value) {// 如果targetNode是parent的左子节点
parent.left = targetNode.left;
} else {//如果targetNode是parent的右子节点
parent.right = targetNode.left;
}
}else {
root = targetNode.left;
}
}else {
if (parent != null) {
if (parent.left.value == targetNode.value) {// 如果targetNode是parent的左子节点
parent.left = targetNode.right;
} else { //如果targetNode是parent的右子节点
parent.right = targetNode.right;
}
}else {
root = targetNode.right;
}
}
}
}
}
平衡二叉树
基本介绍
为什么需要平衡二叉树
- 如果由数组{1, 2, 3, 4}来构建一颗二叉排序树，得到的二叉树不仅没有体现其特点，反而还退化成了链表
简介
- 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树，可以保证查询效率较高
- 具有以下特点：
- 它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树
- 平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等
- 下图所示的二叉树就是平衡二叉树
应用案例——左旋转
将由数列 {4,3,6,5,7,8}构建的二叉排序树，修改为一颗平衡二叉树
此处右子树的高度高于左子树，且差值大于1，所以需要进行左旋转，来降低右子树的高度
步骤
- 创建一个新节点，值为当前节点的值（4）
- 让新节点的左子树指向当前节点的左子树
- 让新节点的右子树指向当前节点的右子树的左子树
- 将当前节点的值改为其右子树的值
- 将当前节点的右子树变为其右子树的右子树
- 让当前节点的左子树指向新节点
应用案例——右旋转
当一颗二叉排序树的左子树高度大于右子树高度，且差值大于1时，需要进行右旋转，来降低左子树的高度
步骤
- 创建一个新节点，其值为当前节点的值
- 将新节点的右子树指向当前节点的右子树
- 将新节点的左子树指向当前节点的左子树的右子树
- 将当前节点的值改为其左子树的值
- 将当前节点的左子树指向其左子树的左子树
-
应用案例——双旋转
某些时候，只进行左旋转或者右旋转，并不能将二叉排序树变为平衡二叉树。这时就需要进行双旋转，即同时进行左旋转和右旋转
进行左旋转时，如果当前节点右子树的左子树高于其右子树，需要先进行左旋转
- 进行右旋转时，如果当前节点左子树的右子树高于其左子树，需要先进性右旋转
实现代码
package Tree;
/**
* @author Voyager1
* @create 2021-10-14 15:15
*/
public class AVLTreeDemo {
public static void main(String[] args) {
//int[] arr = {4,3,6,5,7,8};
//int[] arr = { 10, 12, 8, 9, 7, 6 };
int[] arr = { 10, 11, 7, 6, 8, 9 };
//创建一个 AVLTree对象
AVLTree avlTree = new AVLTree();
//添加结点
for(int i=0; i < arr.length; i++) {
avlTree.add(new AVLNode(arr[i]));
}
//遍历
System.out.println("中序遍历");
avlTree.infixOrder();
System.out.println("在平衡处理~");
System.out.println("树的高度=" + avlTree.getRoot().height());//4-->3
System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight());//1-->2
System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight());//3-->2
System.out.println("根节点=" + avlTree.getRoot().right.right);
}
}
class AVLTree{
private AVLNode root;
public AVLNode getRoot() {
return root;
}
//添加结点
public void add(AVLNode node){
if (root == null){
root = node;
}else {
root.add(node);
}
}
//中序遍历
public void infixOrder(){
if (root == null){
System.out.println("二叉排序树为空，不能遍历");
}else {
root.infixOrder();
}
}
//查找要删除的节点
public AVLNode search(int value){
if (root == null){
return null;
}else{
return root.search(value);
}
}
//查找要删除节点的父节点
public AVLNode searchParent(int value){
if (root == null){
return null;
}else {
return root.searchParent(value);
}
}
//编写方法:
//1. 返回的 以node 为根结点的二叉排序树的最小结点的值
//2. 删除node 为根结点的二叉排序树的最小结点
public int delRightTreeMin(AVLNode node){
AVLNode target = node;
while (target.left != null){
target = target.left;
}
//这时 target就指向了最小结点
//删除最小结点
delNode(target.value);
return target.value;
}
//删除节点
public void delNode(int value){
if (root == null){
return;
}else {
//1.需求先去找到要删除的结点 targetNode
AVLNode targetNode = search(value);
//如果没有找到要删除的结点
if (targetNode == null){
return;
}
//如果我们发现当前这颗二叉排序树只有一个结点
if (root.left == null && root.right == null){
return;
}
//找到targetNode的父结点
AVLNode parent = searchParent(value);
//如果要删除的结点是叶子结点
if (targetNode.left == null && targetNode.right == null){
//判断targetNode 是父结点的左子结点，还是右子结点
if(parent != 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 (targetNode.left != null && targetNode.right != null){//删除有两颗子树的节点
int minVal = delRightTreeMin(targetNode);
targetNode.value = minVal;
}else {// 删除只有一颗子树的结点
//如果要删除的结点有左子结点
if (targetNode.left != null){
if (parent != null){
//如果 targetNode 是 parent 的左子结点
if (parent.left.value == value){
parent.left = targetNode.left;
}else {//targetNode 是 parent 的右子结点
parent.right = targetNode.left;
}
}else {
root = targetNode.left;
}
}else {//如果要删除的结点有右子结点
if (parent != null){
//如果 targetNode 是 parent 的左子结点
if (parent.left.value == value){
parent.left = targetNode.right;
}else {//targetNode 是 parent 的右子结点
parent.right = targetNode.right;
}
}else {
root = targetNode.right;
}
}
}
}
}
}
class AVLNode {
int value;
AVLNode left;
AVLNode right;
public AVLNode(int value) {
this.value = value;
}
@Override
public String toString() {
return "AVLNode{" +
"value=" + value +
'}';
}
//添加结点的方法
// 递归的形式添加结点，注意需要满足二叉排序树的要求
public void add(AVLNode node){
if (node == null){
return;
}
if (node.value < this.value){
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);
}
}
//当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转
if ((rightHeight() - leftHeight()) > 1){
//如果它的右子树的左子树的高度大于它的右子树的右子树的高度
if (right != null && right.leftHeight() > right.rightHeight()){
//先对右子结点进行右旋转
right.rightRotate();
//然后在对当前结点进行左旋转
leftRotate();
}else {
//直接进行左旋转即可
leftRotate();
}
}
//当添加完一个结点后，如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
if ((leftHeight() - rightHeight()) > 1){
//如果它的左子树的右子树高度大于它的左子树的高度
if (left != null && left.rightHeight() > left.leftHeight()){
//先对当前结点的左结点(左子树)->左旋转
left.leftRotate();
//再对当前结点进行右旋转
rightRotate();
}else {
//直接进行右旋转即可
rightRotate();
}
}
}
//中序遍历
public void infixOrder(){
if (this.left != null){
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null){
this.right.infixOrder();
}
}
/**
*查找要删除的节点
* @param value 希望删除的结点的值
* @return 如果找到返回该结点，否则返回null
*/
public AVLNode search(int value){
if (this.value == value){
return this;
} else if (value < this.value){
if (this.left == null){
return null;
}
return this.left.search(value);
}else {//如果查找的值不小于当前结点，向右子树递归查找
if (this.right == null){
return null;
}
return this.right.search(value);
}
}
/**
* 查找父节点
* @param value
* @return
*/
public AVLNode 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;
}
}
}
// 返回左子树的高度
public int leftHeight(){
if (left == null){
return 0;
}
return left.height();
}
// 返回右子树的高度
public int rightHeight(){
if(right == null){
return 0;
}
return right.height();
}
// 返回 以该结点为根结点的树的高度
public int height(){
return Math.max(left == null ? 0:left.height(),right == null ? 0:right.height()) + 1;
}
//左旋转方法
public void leftRotate(){
//创建新的结点，以当前根结点的值
AVLNode newNode = new AVLNode(value);
//把新的结点的左子树设置成当前结点的左子树
newNode.left = left;
//把新的结点的右子树设置成带你过去结点的右子树的左子树
newNode.right = right.left;
//把当前结点的值替换成右子结点的值
value = right.value;
//把当前结点的右子树设置成当前结点右子树的右子树
right = right.right;
//把当前结点的左子树(左子结点)设置成新的结点
left = newNode;
}
//右旋转方法
public void rightRotate(){
AVLNode newNode = new AVLNode(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
}
3、多叉树
基本介绍
在二叉树中，每个节点最多有一个数据项和两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树（multiway tree）
多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化
2-3树
2-3树是最简单的B树结构，具有以下特点
- 2-3树的所有叶子节点都在同一层(只要是 B树都满足这个条件)
- 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点
- 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
- 2-3树是由二节点和三节点构成的树（2和3）
2-3树插入规则
- 2-3树的所有叶子节点都在同一层.(只要是 B树都满足这个条件)
- 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点
- 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
- 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面 3个条件
对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则
B树的阶：节点的最多子节点个数。比如 2-3树的阶是3，2-3-4树的阶是4
- B树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点
- 关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据
- 搜索有可能在非叶子结点结束
-
B+树
B+树是B树的变体，也是一种多路搜索树
- B+树的搜索与 B树也基本相同，区别是 B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找
- 所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据)恰好是有序的
- 不可能在非叶子结点命中
- 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
- 更适合文件索引系统
B树和 B+树各有自己的应用场景，不能说 B+树完全比 B树好，反之亦然
B*树
B*树是 B+树的变体，在 B+树的非根和非叶子结点再增加指向兄弟的指针
- B*树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为 2/3，而B+树的块的最低使用率为的1/2
- 从第 1个特点我们可以看出，B*树分配新结点的概率比B+树要低，空间使用率更高
若有收获，就点个赞吧
0 人点赞
