【Java数据结构与算法】树结构基础

数组 链表 树存储方式分析

为什么需要树这种数据结构

1. 数组存储方式分析

   优点：通过下标方式访问元素，速度快。对于有序数组，还可以使用二分查找提高检索速度；

   缺点：如果要检所具体某个值，或者插入值(按一定顺序)会整体移动，效率低；

   

   拓展：集合的底层其实也是维护了一个数组，它插入值同样使用数组扩容来实现；

2. 链式存储方式分析

   优点：在一定程度上对数组存储方式有优化(如：插入一个数值节点，只需要将插入节点，链接到链表即可，删除效率也很好)；

   缺点：检索效率仍然较低；

   

3. 树存储方式分析

   能提高数据存储，读取的效率，比如利用二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度；

   案例：[7,3,10,1,5,9,12];

   

   二叉排序树存储数据效率：

   1. 查找12，就拿12和7比较，结果12>7，就往7的右边查找；然后12和10比较，结果12>10，继续往10的右边查找；最后找到了12；
   2. 添加13，先通过上方的步骤找到12的位置，然后12和13比较，13>12，就将13连接到12的右侧；
   3. 删除和修改的速度也同样很快；

二叉树的概念和常用术语

树示意图

树常用术语

1. 节点
2. 根节点
3. 父节点
4. 子节点
5. 叶子节点（没有子节点的节点）
6. 节点的权（节点值）
7. 路径（从root节点到该节点的路线）
8. 层
9. 子树
10. 树的高度（最大层数）
11. 森林（多颗子树构成森林）

二叉树的概念

1. 树的类型很多，每个节点最多只能有两个子节点的一种形式称为二叉树；

2. 二叉树的子节点分为左节点和右节点；

   

3. 如果该二叉树的所有叶子节点都在最后一层，并且节点总数=2$^n$-1，n为层数，增我们称为满二叉树；

   

4. 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树；

   

前序中序后序遍历二叉树图解

使用前序，中序和后序对下面的二叉树进行遍历；

1. 前序遍历：

   先输出当前节点，如果当前节点左子节点不为空，就递归前序遍历；如果当前节点右子节点不为空，就递归前序遍历。

2. 中序遍历：

   如果当前节点的左子节点不为空，就递归中序遍历；然后输出当前节点；若当前节点右子节点不为空，就递归中序遍历。

3. 后序遍历：

   如果当前节点的左子节点不为空，就递归后序遍历；若当前节点右子节点不为空，就递归后序遍历；最后输出当前节点。

前序中序后序遍历二叉树代码实现

代码实现

代码

package com.jokerdig.tree;

/**
 * @author Joker大雄
 * @data 2022/10/28 - 9:24
 **/
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.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;  // 默认为null
    private HeroNode right; // 默认为null

    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;
    }

    @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 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);
    }
}

运行结果

前序遍历
HeroNode{no=1, name='宋江'}
HeroNode{no=2, name='吴用'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=4, name='武松'}
中序遍历
HeroNode{no=2, name='吴用'}
HeroNode{no=1, name='宋江'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=4, name='武松'}
后序遍历
HeroNode{no=2, name='吴用'}
HeroNode{no=4, name='武松'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=1, name='宋江'}

Process finished with exit code 0

拓展

1. 在上图的"卢俊义"节点处，增加一个左子节点"关胜"；
2. 使用前序，中序，后序遍历，并查看输出结果；

代码

package com.jokerdig.tree;

/**
 * @author Joker大雄
 * @data 2022/10/28 - 9:24
 **/
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左侧添加
        root.setRight(node3);// root右侧添加
        node3.setLeft(node5);
        node3.setRight(node4);
        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;  // 默认为null
    private HeroNode right; // 默认为null

    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;
    }

    @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 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);
    }
}

运行结果

前序遍历
HeroNode{no=1, name='宋江'}
HeroNode{no=2, name='吴用'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=5, name='关胜'}
HeroNode{no=4, name='武松'}
中序遍历
HeroNode{no=2, name='吴用'}
HeroNode{no=1, name='宋江'}
HeroNode{no=5, name='关胜'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=4, name='武松'}
后序遍历
HeroNode{no=2, name='吴用'}
HeroNode{no=5, name='关胜'}
HeroNode{no=4, name='武松'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=1, name='宋江'}

Process finished with exit code 0

前序中序后序查找思路图解

二叉树查找指定节点

要求：

1. 请编写前序，中序，后序查找的方法；
2. 并分别使用三种查找方式，查找heroNo=5的节点；
3. 并分析各种查找方式，分别比较了多少次；

查找步骤分析

前序查找

• 先判断当前节点的是否等于要查找的节点；

• 如果相等，就返回当前节点；

• 如果不相等，则判断当前节点的左子节点是否为空，若不为空，则左递归前序查找；找到节点就返回，否则继续判断当前节点的右子节点是否为空，若不为空，则继续右递归前序查找，最后返回节点(不管是否为空都返回)；

中序查找

• 先判断当前节点的左子节点是否为空，若不为空，则左递归中序查找，找到节点就返回；

• 如果没有找到，就判断当前节点是否等于要查找的节点，如果相等就返回当前节点；

• 如果不相等，则继续判断当前节点的右子节点是否为空，若不为空，则继续右递归中序查找，最后返回节点(不管是否为空都返回)；

后序查找

• 先判断当前节点的左子节点是否为空，若不为空，则左递归后序查找，找到节点就返回；

• 然后继续判断当前节点的右子节点是否为空，若不为空，则继续右递归后序查找，找到节点就返回；

• 否则，就判断当前节点是否等于要查找的节点，如果相等就返回当前节点，否则返回null；

前序中序后序查找代码实现

代码

package com.jokerdig.tree;

/**
 * @author Joker大雄
 * @data 2022/10/28 - 9:24
 **/
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左侧添加
        root.setRight(node3);// root右侧添加
        node3.setLeft(node5);
        node3.setRight(node4);
        binaryTree.setRoot(root);
        // 测试查找5号节点
        // 前序遍历查找4次
        System.out.println("=======前序遍历查找=======");
        HeroNode heroNode = binaryTree.preOrderSearch(5);
        if(heroNode!=null){
            System.out.printf("找到：no=%d name=%s\n",heroNode.getNo(),heroNode.getName());
        }else{
            System.out.printf("没有 no=%d 的节点\n",5);
        }
        // 中序遍历查找3次
        System.out.println("=======中序遍历查找=======");
        HeroNode heroNode2 = binaryTree.infixOrderSearch(5);
        if(heroNode2!=null){
            System.out.printf("找到：no=%d name=%s\n",heroNode2.getNo(),heroNode2.getName());
        }else{
            System.out.printf("没有 no=%d 的节点\n",5);
        }
        // 后序遍历查找2次
        System.out.println("=======后序遍历查找=======");
        HeroNode heroNode3 = binaryTree.postOrderSearch(5);
        if(heroNode3!=null){
            System.out.printf("找到：no=%d name=%s\n",heroNode3.getNo(),heroNode3.getName());
        }else{
            System.out.printf("没有 no=%d 的节点\n",5);
        }
    }
}
// 定义BinaryTree二叉树
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);
        }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;  // 默认为null
    private HeroNode right; // 默认为null

    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;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
    // 定义一个节点
    private HeroNode node = null;
    // 前序遍历查找
    /**
     *
     * @param no 编号
     * @return 返回查找到的节点，没找到返回null
     */
    public HeroNode preOrderSearch(int no){
        System.out.println("进入前序遍历查找");
        // 比较当前节点是否要找到
        if(this.no == no){
            return this;
        }
        // 判断当前节点的左子节点是否为空，若不为空，则左递归前序查找
        // 找到节点就返回
        if(this.left!=null){
            node = this.left.preOrderSearch(no);
        }
        if(node!=null){
            // 在左子节点找到了要查找的节点
            return node;
        }
        // 继续判断当前节点的右子节点是否为空，
        // 若不为空，则继续右递归前序查找
        if(this.right!=null){
            node = this.right.preOrderSearch(no);
        }
        return node;
    }
    // 中序遍历查找
    public HeroNode infixOrderSearch(int no){
        // 先判断当前节点的左子节点是否为空，
        // 若不为空，则左递归中序查找；找到节点就返回
        if(this.left!=null){
            node = this.left.infixOrderSearch(no);
        }
        if(node!=null){
            return node;
        }
        // 判断是否和当前节点相等
        System.out.println("进入中序遍历查找");
        if(this.no == no){
            return this;
        }
        // 判断右子节点是否为空，不为空就右递归中序查找，找到节点就返回
        if(this.right!=null){
            node = this.right.infixOrderSearch(no);
        }
        return node;
    }
    // 后序遍历查找
    public HeroNode postOrderSearch(int no){
        // 判断当前节点的左子节点是否为空，
        // 若不为空，则左递归后序查找，找到节点就返回
        if(this.left!=null){
            node = this.left.postOrderSearch(no);
        }
        if(node!=null){
            return node;
        }
        // 判断当前节点的右子节点是否为空，
        // 若不为空，则继续右递归后序查找，找到节点就返回
        if(this.right!=null){
            node = this.right.postOrderSearch(no);
        }
        if(node!=null){
            return node;
        }
        // 判断当前节点是否等于要查找的节点，如果相等就返回当前节点
        System.out.println("进入后序遍历查找");
        if(this.no == no){
            return this;
        }
        return null;
    }
}

运行结果

=======前序遍历查找=======
进入前序遍历查找
进入前序遍历查找
进入前序遍历查找
进入前序遍历查找
找到：no=5 name=关胜
=======中序遍历查找=======
进入中序遍历查找
进入中序遍历查找
进入中序遍历查找
找到：no=5 name=关胜
=======后序遍历查找=======
进入后序遍历查找
进入后序遍历查找
找到：no=5 name=关胜

Process finished with exit code 0

二叉树删除节点思路图解

二叉树删除节点

要求：

1. 如果删除的节点是叶子节点，则删除该节点；
2. 如果删除的节点是非叶子节点，则删除该子树；
3. 测试删除5号叶子节点和3号树；

步骤：

1. 如果只有一个root节点，则等价于将二叉树为空；

2. 因为我们的二叉树是单向的，所以通常判断当前节点的子节点是否为待删除节点，而不是去判断当前节点是否待删除；

3. 如果当前节点的左子节点不为空，并且左子节点就是待删除的节点，就将this.left=null，并返回(结束递归删除);

4. 如果当前节点的右子节点不为空，并且右子节点就是待删除的节点，就将this.right=null，并返回(结束递归删除);

5. 如果第2，3步骤没有删除节点，那么我们就需要向左子树进行递归删除；

6. 如果第4步骤也没有删除节点，那么我们就需要向右子树进行递归删除；

二叉树删除节点代码实现

代码

package com.jokerdig.tree;

/**
 * @author Joker大雄
 * @data 2022/10/28 - 9:24
 **/
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左侧添加
        root.setRight(node3);// root右侧添加
        node3.setLeft(node5);
        node3.setRight(node4);
        binaryTree.setRoot(root);
        // 测试删除5号叶子节点和3号树
        System.out.println("==========删除5号叶子节点==========");
        System.out.println("删除前，前序遍历");
        binaryTree.preOrder();
        // 删除
        binaryTree.delNode(5);
        System.out.println("删除后，前序遍历");
        binaryTree.preOrder();

        System.out.println("==========删除3号树==========");
        System.out.println("删除前，前序遍历");
        binaryTree.preOrder();
        // 删除
        binaryTree.delNode(3);
        System.out.println("删除后，前序遍历");
        binaryTree.preOrder();
    }
}
// 定义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 delNode(int no){
        if(root!=null){
           // 这里需要判断root是否为空
            if(root.getNo()==no){
                root = null;
            }else{
                // 递归删除
                root.delNode(no);
            }
        }else{
            System.out.println("二叉树为空");
        }
    }
}
// 先创建节点 HeroNode
class HeroNode{
    private int no;
    private String name;
    private HeroNode left;  // 默认为null
    private HeroNode right; // 默认为null

    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;
    }

    @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 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);
        }
    }
}

运行结果

==========删除5号叶子节点==========
删除前，前序遍历
HeroNode{no=1, name='宋江'}
HeroNode{no=2, name='吴用'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=5, name='关胜'}
HeroNode{no=4, name='武松'}
删除后，前序遍历
HeroNode{no=1, name='宋江'}
HeroNode{no=2, name='吴用'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=4, name='武松'}
==========删除3号树==========
删除前，前序遍历
HeroNode{no=1, name='宋江'}
HeroNode{no=2, name='吴用'}
HeroNode{no=3, name='卢俊义'}
HeroNode{no=4, name='武松'}
删除后，前序遍历
HeroNode{no=1, name='宋江'}
HeroNode{no=2, name='吴用'}

Process finished with exit code 0

顺序存储二叉树思路图解

顺序存储二叉树基本介绍

从数据存储来看，数据存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组；

要求：

1. 上图的二叉树的节点，要求以数组的方式来存放；
2. 遍历数组的时候，要求仍然以前序，中序和后序的遍历方式来遍历数据；

顺序存储二叉树的特点

1. 顺序存储二叉树通常只考虑完全二叉树；
2. 第n个元素的左子节点为2*n+1；
3. 第n个元素的右子节点为2*n+2；
4. 第n个元素的父节点为(n-1)/2；
5. n：表示二叉树中第几个元素(从0开始编号)

顺序存储二叉树代码实现

题目要求

给你一个数组{1,2,3,4,5,6,7}，要求以二叉树前序，中序和后序遍历的方式进行遍历；

代码实现

代码

package com.jokerdig.tree;

/**
 * @author Joker大雄
 * @data 2022/11/1 - 9:53
 **/
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7};
        // 创建ArrBinaryTree
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        System.out.println("前序遍历：");
        arrBinaryTree.preOrder(); // 1 2 4 5 3 6 7
        System.out.println("\n中序遍历：");
        arrBinaryTree.infixOrder(); // 4 2 5 1 6 3 7
        System.out.println("\n后序遍历：");
        arrBinaryTree.postOrder(); // 4 5 2 6 7 3 1
    }
}
// 编写一个ArrBinaryTree，实现顺序存储二叉数遍历
class ArrBinaryTree{
    private int [] arr;// 存储数据节点
    // 构造器
    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

     // 重载preOrder方法
    public void preOrder(){
        this.preOrder(0);
    }
    // 重载infixOrder方法
    public void infixOrder(){
        this.infixOrder(0);
    }
    // 重载postOrder方法
    public void postOrder(){
        this.postOrder(0);
    }

    // 编写一个方法，完成顺序存储二叉树的遍历
    // 前序遍历
    /**
     *
     * @param index 数组的下标，也就是题目里的n
     */
    public void preOrder(int index){
        // 数组为空
        if(arr == null || arr.length==0){
            System.out.println("数组为空");
            return;
        }
        // 输出当前元素
        System.out.print(arr[index]+" ");
        //  向左递归遍历
        if((index*2+1)<arr.length){
            preOrder(index*2+1);
        }
        // 向右递归遍历
        if((index*2+2)<arr.length){
            preOrder(index*2+2);
        }
    }

    // 中序遍历
    public void infixOrder(int index){
        // 数组为空
        if(arr == null || arr.length == 0){
            System.out.println("数组为空");
            return;
        }
        // 左递归遍历
        if((index*2+1)<arr.length){
            infixOrder(index*2+1);
        }
        // 数组当前元素
        System.out.print(arr[index]+" ");
        // 右递归遍历
        if((index*2+2)<arr.length){
            infixOrder(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.print(arr[index]+" ");
    }
}

运行结果

前序遍历：
1 2 4 5 3 6 7 
中序遍历：
4 2 5 1 6 3 7 
后序遍历：
4 5 2 6 7 3 1 
Process finished with exit code 0

八大排序算法中的堆排序，就会使用到顺序存储二叉树；

线索化二叉树的介绍

案例

将数列{1,3,6,8,10,14}构建成一颗二叉树；

问题分析：

1. 当我们对上面的二叉树进行中序遍历时，数列为{8,3,10,1,14,6}；
2. 但是8，10，14这几个节点的左右指针和6的右指针都并没有完全利用上；
3. 如果我们希望充分利用各个节点的左右指针，让各个节点可以指向自己的前后节点；
4. 使用线索二叉树解决；

线索二叉树基本介绍

1. n个节点的二叉链表中含有n+1【公式推导：2n-(n-1)=n+1】个空指针域，利用二叉链表中的空指针域，存放指向该节点在某种遍历次序下的前驱节点和后继节点指针；(这种附加的指针称为线索)
2. 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树（Threaded BinaryTree）。根据线索性质的不同，线索二叉树可以分为前序线索二叉树，中序线索二叉树和后序线索二叉树；
3. 一个节点的前一个节点，称为前驱节点；
4. 一个节点的后一个节点，称为后继节点；

线索化二叉树的思路图解

应用案例

将下面的二叉树，变为中序线索二叉树；

思路分析

结果应该为:{8,3,10,1,14,6}

说明：

当线索化二叉树后，Node节点的属性left和right，有如下情况；

1. left指向的是左子树，也可能指向的是前驱节点，比如1节点left指向的左子树，而10节点的left指向的就是前驱节点；
2. right指向的是右子树，也可能是指向后继节点，比如1节点right指向的是右子树，而10节点的right指向的是后继节点；

线索化二叉树的代码实现

代码

package com.jokerdig.tree;

/**
 * @author Joker大雄
 * @data 2022/11/2 - 19:06
 **/
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        // 测试中序线索二叉树的功能
        HeroNode2 root = new HeroNode2(1, "tom");
        HeroNode2 node2 = new HeroNode2(3, "jack");
        HeroNode2 node3 = new HeroNode2(6, "join");
        HeroNode2 node4 = new HeroNode2(8, "black");
        HeroNode2 node5 = new HeroNode2(10, "tom1");
        HeroNode2 node6 = new HeroNode2(14, "tom2");

        // 二叉树创建，手动
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        // 测试线索化
        BinaryTree2 binaryTree2 = new BinaryTree2();
        binaryTree2.setRoot(root);
        binaryTree2.threadedNodes();
        // 测试10这个节点进行
        HeroNode2 leftNode = node5.getLeft();
        HeroNode2 rightNode = node5.getRight();
        System.out.println("10号节点的前驱节点为："+leftNode);
        System.out.println("10号节点的后继节点为："+rightNode);
    }

}
// 线索化二叉树
class BinaryTree2{
    private HeroNode2 root; // 根节点
    // 前驱节点的辅助指针
    private HeroNode2 pre = null;

    public void setRoot(HeroNode2 root) {
        this.root = root;
    }

    // 方法重载
    public void threadedNodes(){
        this.threadedNodes(root);
    }

    // 编写中序线索化二叉树方法
    /**
     *
     * @param node  需要线索化的节点
     */
    public void threadedNodes(HeroNode2 node){
        // 判断是否为空
        if(node==null){
            return;
        }
        // 1. 先线索化左子树
        threadedNodes(node.getLeft());
        // 2. 线索化当前节点[有一定难度]
        // 先处理当前节点的前驱节点,这里是node
        if(node.getLeft()==null){
            // 当前节点的左指针指向前驱节点
            node.setLeft(pre);
            // 修改当前节点做指针的类型
            node.setLeftType(1);
        }
        // 处理后继节点，而这里是pre
        if(pre!=null && pre.getRight()==null){
            // 让当前节点的右指针指向当前节点
            pre.setRight(node);
            // 修改谦虚节点右指针类型
            pre.setRightType(1);
        }
        // 每处理一个节点后，让当前节点是下一个节点的前驱节点
        pre = node;
        // 3. 线索化右子树
        threadedNodes(node.getRight());
    }
}

// 创建HeroNode2
class HeroNode2 {
    private int no;
    private String name;
    private HeroNode2 left;  // 默认为null
    private HeroNode2 right; // 默认为null
    // 左属性 leftType=0表示指向左子树，如果是1表示指向前驱节点
    private int leftType;
    // 右属性 rightType=0表示指向右子树，如果是1表示指向后继节点
    private int rightType;

    public HeroNode2(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 HeroNode2 getLeft() {
        return left;
    }

    public void setLeft(HeroNode2 left) {
        this.left = left;
    }

    public HeroNode2 getRight() {
        return right;
    }

    public void setRight(HeroNode2 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 "HeroNode2{" +
                "no=" + no +
                ", name='" + name + 
                '}';
    }
}

运行结果

10号节点的前驱节点为：HeroNode2{no=3, name='jack}
10号节点的后继节点为：HeroNode2{no=1, name='tom}

Process finished with exit code 0

遍历线索化二叉树实现

需求分析

说明：对前面的中序线索化二叉树进行遍历；

分析：因为线索化后，各个节点可以通过线索方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致；

代码实现

代码

package com.jokerdig.tree;

/**
 * @author Joker大雄
 * @data 2022/11/2 - 19:06
 **/
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        // 测试中序线索二叉树的功能
        HeroNode2 root = new HeroNode2(1, "tom");
        HeroNode2 node2 = new HeroNode2(3, "jack");
        HeroNode2 node3 = new HeroNode2(6, "join");
        HeroNode2 node4 = new HeroNode2(8, "black");
        HeroNode2 node5 = new HeroNode2(10, "tom1");
        HeroNode2 node6 = new HeroNode2(14, "tom2");
        // 二叉树创建，手动
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        // 线索化
        BinaryTree2 binaryTree2 = new BinaryTree2();
        binaryTree2.setRoot(root);
        binaryTree2.threadedNodes();
        // 当线索化二叉树后，不能使用原来的遍历方式
        System.out.println("使用线索化的方式遍历线索化二叉树");
        binaryTree2.threadedList(); // 8,3,10,1,14,6
    }
}
// 线索化二叉树
class BinaryTree2{
    private HeroNode2 root; // 根节点
    // 前驱节点的辅助指针
    private HeroNode2 pre = null;

    public void setRoot(HeroNode2 root) {
        this.root = root;
    }

    // 方法重载
    public void threadedNodes(){
        this.threadedNodes(root);
    }

    // 遍历线索化二叉树的方法
    public void threadedList(){
        // 定义变量，存储当前遍历的节点
        HeroNode2 node = root;
        while(node!=null){
            // 循环的找到leftType=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();
        }
    }

    // 编写中序线索化二叉树方法
    /**
     *
     * @param node  需要线索化的节点
     */
    public void threadedNodes(HeroNode2 node){
        // 判断是否为空
        if(node==null){
            return;
        }
        // 1. 先线索化左子树
        threadedNodes(node.getLeft());
        // 2. 线索化当前节点[有一定难度]
        // 先处理当前节点的前驱节点,这里是node
        if(node.getLeft()==null){
            // 当前节点的左指针指向前驱节点
            node.setLeft(pre);
            // 修改当前节点做指针的类型
            node.setLeftType(1);
        }
        // 处理后继节点，而这里是pre
        if(pre!=null && pre.getRight()==null){
            // 让当前节点的右指针指向当前节点
            pre.setRight(node);
            // 修改谦虚节点右指针类型
            pre.setRightType(1);
        }
        // 每处理一个节点后，让当前节点是下一个节点的前驱节点
        pre = node;
        // 3. 线索化右子树
        threadedNodes(node.getRight());
    }
}

// 创建HeroNode2
class HeroNode2 {
    private int no;
    private String name;
    private HeroNode2 left;  // 默认为null
    private HeroNode2 right; // 默认为null
    // 左属性 leftType=0表示指向左子树，如果是1表示指向前驱节点
    private int leftType;
    // 右属性 rightType=0表示指向右子树，如果是1表示指向后继节点
    private int rightType;

    public HeroNode2(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 HeroNode2 getLeft() {
        return left;
    }

    public void setLeft(HeroNode2 left) {
        this.left = left;
    }

    public HeroNode2 getRight() {
        return right;
    }

    public void setRight(HeroNode2 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 "HeroNode2{" +
                "no=" + no +
                ", name='" + name + 
                '}';
    }
}

运行结果

使用线索化的方式遍历线索化二叉树
HeroNode2{no=8, name='black}
HeroNode2{no=3, name='jack}
HeroNode2{no=10, name='tom1}
HeroNode2{no=1, name='tom}
HeroNode2{no=14, name='tom2}
HeroNode2{no=6, name='join}

Process finished with exit code 0