一、树的存储方式

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 item;Node next;Node prev;Node(Node prev, E element, Node 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;}@Overridepublic 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;
}