数据结构与算法——二叉树遍历、查找、删除、顺序存储二叉树、线索化二叉树
一、树的存储方式
1.1 为什么需要树这种数据结构
1.1.1 数组存储方式分析：
优点：通过下标方式访问，速度快。对于有序数组，还可以使用二分查找提高检索效率
缺点：如果要检索某个集体之或者插入值会整体移动，效率低
ArrayList的底层也是一个数组，（transient Object[] elementData）此数组当空间不足的时候会自动进行扩容
既然到这里了，那我们可以先了解一下ArrayList底层源码分析
当创建对象时，使用的无参构造器，初始elementData容量为0（JDK7是10）
如果使用的是指定容量的capacity的构造器，则初始elementData的容量为capacity
建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)
添加元素的时候，先判断是否要扩容，若扩容则调用grow方法，否则直接添加元素到指定的位置
如果使用的是无参构造器，第一次添加需要扩容的话，则扩容elementData为10，如果需要再次扩容的话，则扩容elementData为1.5倍
如果使用的是capacity构造器，需要扩容的话，则直接扩容elementData为1.5倍
1.1.2 链式存储方式的分析：
优点：在一定程度上对数组存储方式优化，比如插入一个数值节点，只需要将插入节点连接到链表中，删除同样效率较高
缺点：在进行检索时，效率仍然较低，比如检索某个值，需要从头节点遍历
LinkedList的底层是一个双向链表
LinkedList：双向链表，内部没有声明数组，而是定义了Node类型的first和last，用于记录首末元素。同时，定义内部类Node，作为LinkedList中保存数据的基本结构
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next; //next变量记录下一个元素的位置
this.prev = prev; //prev变量记录前一个元素的位置
}
}
1.1.3二叉树存储方式的分析：
能提高数据存储，读取的效率，比如利用二叉排序树，即可保证数据的检索速度，同时也可以保证数据的插入、删除、修改的速度
怎么构建树？
下图中的数组的数据构建成树。我们可以将数字的第一个节点设置为树的最上面，然后剩余的元素和节点比较，比节点大的在右侧添加，小的在节点左侧添加
假如我们要查找12的话，怎么查找呢？
12会先和7比较，比7大，则向7右侧寻找；
12再和7右侧的10比较，则再向10右侧寻找；
12再和10右侧的12比较，发现相等，则返回。
1.2 树的概念和常用术语
1.3 二叉树
树有很多种，每个节点最多只能有两个子节点的形式成为二叉树；
二叉树的子节点分为左节点和右节点；
如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树；
也可以说满二叉树的节点总数= 2^n -1 , n 为层数
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树
二、二叉树的遍历
2.1 前序遍历、中序遍历、后序遍历
前序遍历: 先输出父节点，再遍历左子树和右子树
先输出当前节点（初始时为根节点，即root节点），
如果左子节点不为空，则递归继续前序遍历
如果右子节点不为空，则递归继续前序遍历
按照图的输出顺序为：1 2 3 4
中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
如果当前节点的左子节点不为空，则递归继续中序遍历
先输出当前节点（初始时为根节点，即root节点）
如果当前节点的右子节点不为空，则递归继续中序遍历
按照图的输出顺序为 2 1 3 4
后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
如果当前节点的左子节点不为空，则递归继续后序遍历
如果当前节点的右子节点不为空，则递归继续后序遍历
先输出当前节点（初始时为根节点，即root节点）
按照图的输出顺序为 2 4 3 1
小结: 看输出父节点的顺序，就确定是前序，中序还是后序
假设我们再增加一个5号节点关胜
前序遍历： 1 2 3 5 4
中序遍历： 2 1 5 3 4
后序遍历： 2 5 4 3 1
2.2 代码实现
使用代码实现下图的二叉树
package org.example.suanfa;
import lombok.Data;
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, "林冲");
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
binaryTree.setRoot(root);
System.out.println("前序遍历");
binaryTree.preOrder();
System.out.println("中序遍历");
binaryTree.midOrder();
System.out.println("后续遍历");
binaryTree.postOrder();
}
}
@Data
class BinaryTree {
private HeroNode 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("当前二叉树为空，无法便利");
}
}
}
@Data
class HeroNode {
private int no;
private String name;
private HeroNode left;
private HeroNode right;
/**
* 编写前序遍历的方法
*/
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);
}
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
}
三、二叉树的查找
要求：
请编写前序查找，中序查找，后续查找的方法
并分别使用三种查找方式，查找heroNo=5的节点
并分析各种查找方式比较了多少次
3.1 前序查找，中序查找，后续查找的分析
3.2 代码实现
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("前序查找");
System.out.println(binaryTree.preOrderSearch(5));
System.out.println("中序查找");
System.out.println(binaryTree.midOrderSearch(5));
System.out.println("后续查找");
System.out.println(binaryTree.postOrderSearch(5));
}
}@Data
class BinaryTree {
private HeroNode root;
// 前序查找
public HeroNode preOrderSearch(int no) {
if (root != null) {
return root.postOrderSearch(no);
} else {
return null;
}
}
// 中序查找
public HeroNode midOrderSearch(int no) {
if (root != null) {
return root.midOrderSearch(no);
} else {
return null;
}
}
// 后续查找
public HeroNode postOrderSearch(int no) {
if (root != null) {
return root.postOrderSearch(no);
} else {
return null;
}
}
}@Data
class HeroNode {
private int no;
private String name;
private HeroNode left;
private HeroNode right;
/**
* @param no 要查找的编号
* @return 对应的Node，没有找到返回null
*/
public HeroNode preOrderSearch(int no) {
if (this.no == no) {
return this;
}
HeroNode heroNode = null;
if (this.left != null) {
// 运行到这里肯定不是自己要找的，向左递归
heroNode = this.left.preOrderSearch(no);
}
if (heroNode != null) {
// 找到了
return heroNode;
}
// this.right != null,为了调用的时候没有空指针异常
if (this.right != null) {
// 运行到这里说明还没有找到
heroNode = this.right.preOrderSearch(no);
}
return heroNode;
}
// 中序遍历查找
public HeroNode midOrderSearch(int no) {
HeroNode heroNode = null;
// 向左
if (this.left != null) {
// 运行到这里肯定不是自己要找的，向左递归
heroNode = this.left.midOrderSearch(no);
}
if (heroNode != null) {
// 找到了
return heroNode;
}
// 中
if (this.no == no) {
return this;
}
// 向右
if (this.right != null) {
// 运行到这里说明还没有找到
heroNode = this.right.midOrderSearch(no);
}
return heroNode;
}
// 后续遍历查找
public HeroNode postOrderSearch(int no) {
HeroNode heroNode = null;
// 向左
if (this.left != null) {
// 运行到这里肯定不是自己要找的，向左递归
heroNode = this.left.postOrderSearch(no);
}
if (heroNode != null) {
// 找到了
return heroNode;
}
// 向右
if (this.right != null) {
// 运行到这里说明还没有找到
heroNode = this.right.postOrderSearch(no);
}
// 这个地方再写一个if判断heroNode是不是空也行
// 中
if (this.no == no) {
return this;
}
return heroNode;
}
}
四、二叉树的删除操作
4.1 图解
因为现在还没有学二叉排序树，那现在如果删除的不是子节点的话，我们就将整个子节点的树给删掉
4.2 代码实现
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);
binaryTree.delNode(5);
binaryTree.preOrder();
}
}@Data
class BinaryTree {
private HeroNode root;
// 前序遍历
public void preOrder() {
if (this.root != null) {
this.root.preOrder();
} else {
System.out.println("当前二叉树为空，无法便利");
}
}
public boolean delNode(int no){
if(root !=null){
// 如果只有一个root节点，这里立即判断root是不是要删除的节点
if(root.getNo() == no){
root =null;
return true;
}
}else {
System.out.println("空树，不能删除");
return false;
}
// 运行到这里肯定是没有删除的
// boolean nodeBoolean = root.deleteNode(no);
return root.deleteNode(no) ;
}
}@Data
class HeroNode {
private int no;
private String name;
private HeroNode left;
private HeroNode right;
/**
* 编写前序遍历的方法
*/
public void preOrder() {
// 先输出父节点
System.out.println(this);
// 向左子树递归前序遍历
if (this.left != null) {
this.left.preOrder();
}
// 向右子树递归前序遍历
if (this.right != null) {
this.right.preOrder();
}
}
/**
* 递归删除节点
* 如果删除的节点是叶子节点，则删除改节点
* 如果删除的节点是非叶子节点，则删除该子树
* @param no
*/
public boolean deleteNode(int no){
// 2.如果当前节点的左子节点不为空，并且左子节点就是要删除的节点，就将this.left=null,并且结束递归
if(this.left !=null && this.left.no == no){
this.left = null;
return true;
}
// 3.如果当前节点的右子节点不为空，并且右子节点就是要删除的节点，就将this.left=null,并且结束递归
if(this.right !=null && this.right.no ==no){
this.right =null;
return true;
}
// 4.如果第2，3步没有删除节点，那我们就需要向左子树递归删除
boolean deleteBoolean = false; //true表示删除了
if(this.left !=null){
deleteBoolean = this.left.deleteNode(no);
if (deleteBoolean){
return true;
}
}
// 5.再向右子树递归删除
if(this.right !=null){
deleteBoolean = this.right.deleteNode(no);
if (deleteBoolean){
return true;
}
}
return deleteBoolean;
}
}
五、顺序存储二叉树
八大排序算法中的堆排序，就会使用到顺序存储二叉树
5.1 顺序存储二叉树基本说明
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也能转换成数组。
要求：
下图的二叉树的结点，要求以数组的方式来存放 ，如，arr : [1, 2, 3, 4, 5, 6, 6]
要求在遍历数组 arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历
简单的说要就是，数据以数组的方式存储，但是读取的时候却是按照树的方式进行读取
5.2 顺序存储二叉树的特点
顺序二叉树通常只考虑完全二叉树
第n个元素的左子节点的下标为 2 * n + 1
假设n=1，此时对应的数据为2，左子节点对应的下标为2*1+1=3，数据刚好是4
第n个元素的右子节点的下标为 2 * n + 2
假设n=1,此时对应的数据为2，右子节点对应的下标为2*1+2=4，数据刚好是5
第n个元素的父节点的下标为 (n-1) / 2
假设n=1,此时对应的数据为2，父节点对应的下标为0，数据刚好是1
n : 表示二叉树中的第几个元素(按0开始编号如图所示，也可以理解为数组的下标)
5.3 代码实现
public class ArrBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
// 从0号节点开始遍历
arrBinaryTree.preOrder(0);
System.out.println("*********************");
arrBinaryTree.midOrder(0);
System.out.println("*********************");
arrBinaryTree.postOrder(0);
}
}
//编写一个ArrBinaryTree，实现顺序存储二叉树遍历
class ArrBinaryTree {
private int[] arr; //崔楚数据节点的数组
// 构造器
public ArrBinaryTree(int[] arr) {
this.arr = arr;
}
/**
* 编写一个方法，完成顺序存储二叉树的前序遍历
*
* @param index 数组的下标
*/
public void preOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("数组为空，不能按照二叉树的前序遍历");
return;
}
// 运行到这里说明数组中还有数据
// 输出当前的这个元素
System.out.println(arr[index]);
// 向左节点遍历,记得判断一下，可能存在数组下标越界的可能
if ((index * 2 + 1) < arr.length) {
preOrder(index * 2 + 1);
}
// 左递归完成后再向右节点遍历
if ((index * 2 + 2) < arr.length) {
preOrder(index * 2 + 2);
}
}
// 中序遍历
public void midOrder(int index){
if (arr == null || arr.length == 0) {
System.out.println("数组为空，不能按照二叉树的前序遍历");
return;
}
// 向左节点遍历,记得判断一下，可能存在数组下标越界的可能
if ((index * 2 + 1) < arr.length) {
midOrder(index * 2 + 1);
}
// 输出当前的这个元素
System.out.println(arr[index]);
// 再向右节点遍历
if ((index * 2 + 2) < arr.length) {
midOrder(index * 2 + 2);
}
}
// 后续遍历
public void postOrder(int index){
if (arr == null || arr.length == 0) {
System.out.println("数组为空，不能按照二叉树的前序遍历");
return;
}
// 向左节点遍历,记得判断一下，可能存在数组下标越界的可能
if ((index * 2 + 1) < arr.length) {
postOrder(index * 2 + 1);
}
// 再向右节点遍历
if ((index * 2 + 2) < arr.length) {
postOrder(index * 2 + 2);
}
// 输出当前的这个元素
System.out.println(arr[index]);
}
}
六、线索化二叉树
下图中有7个空指针域，空指针域的个数可以看6.1的计算方式
当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 }
但是 6, 8, 10, 14 这几个节点的 左右指针，并没有完全的利用上.
如果我们希望充分的利用 各个节点的左右指针， 让各个节点可以指向自己的前后节点,怎么办?
解决方案-线索二叉树
6.1 介绍
n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。
利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
公式来历：一共有n个结点，一个结点有2个指针，n个结点有2n个指针；n个结点的话会占用n-1个指针，则还剩下2n-(n-1)个空指针域
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。
根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
一个结点的前一个结点，称为前驱结点
一个结点的后一个结点，称为后继结点
6.2 图解
说明：线索二叉树最终形成的结果和遍历的顺序有直接的关系
说明: 当线索化二叉树后，Node节点的 属性 left 和 right ，有如下情况:
left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点.
right指向的是右子树，也可能是指向后继节点，比如 ① 节点right 指向的是右子树，而⑩ 节点的right 指向的是后继节点.
6.3 线索化二叉树代码实现
省略所有get、set、构造方法
public class ThreadedBinaryTreeDemo {
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);
// 测试线索化
ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
threadedBinaryTree.setRoot(root);
threadedBinaryTree.threadedNodes();
// 以10结点做测试
System.out.println("left--->"+node5.getLeft());
System.out.println("right--->"+node5.getRight());
}
}class ThreadedBinaryTree {
private HeroNode root;
// 为了实现线索化，需要创建当前结点的前驱结点指针,简单的来说，这个pre总是保留前一个结点地址
private HeroNode pre =null;
public void threadedNodes() {
this.threadedNodes(root);
}
/**
* 中序线索化的代码
* 对某个结点进行线索化
* @param node 当前需要线索化的结点
*/
public void threadedNodes(HeroNode node) {
// node ==null，不能线索化
if(node == null) {
return;
}
// 1. 先线索化左子树
threadedNodes(node.getLeft());
// 2. 当前结点线索化（有点难度）
// 处理前驱
if(node.getLeft() == null) {
// 如果当前结点的左指针是空，那就指向前驱指针
node.setLeft(pre);
// 修改当前结点的左指针的类型，指向前驱结点
node.setLeftType(1);
}
// 处理后继
// 这个处理后继很巧妙，此时不处理当前node节点的后继节点,只有当node到下一个节点的时候 才会去处理上一个节点的后继节点
if (pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
// ！！！！后移指针
// 每处理一个结点后，让当前结点是下一个结点的前驱结点
pre = node;
// 3. 再线索化右子树
threadedNodes(node.getRight());
}
}
class HeroNode {
private int no;
private String name;
private HeroNode left;
private HeroNode right;
// 说明：
// 如果leftType ==0 表示指向的是左子树，如果1则表示指向的前驱结点
// 如果rightType ==0 表示指向的是右子树，如果1表示指向后继结点
private int leftType;
private int rightType;
}