2.应用案例 - 代码实现 - 《数据结构与算法（浅学）》

package com.atguigu.tree;
/**
 * 中序线索化二叉树
 * @author Dxkstart
 * @create 2021-10-18-15:22
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        //测试中序线索化二叉树的功能
        HeroNodes root = new HeroNodes(1, "t");
        HeroNodes nodes2 = new HeroNodes(3, "y");
        HeroNodes nodes3 = new HeroNodes(6, "u");
        HeroNodes nodes4 = new HeroNodes(8, "o");
        HeroNodes nodes5 = new HeroNodes(10, "p");
        HeroNodes nodes6 = new HeroNodes(14, "q");
        //二叉树，后面我们要递归创建，现在简单处理使用手动创建
        root.setLeft(nodes2);
        root.setRight(nodes3);
        nodes2.setLeft(nodes4);
        nodes2.setRight(nodes5);
        nodes3.setLeft(nodes6);
        //测试线索化
        BinaryTrees binaryTrees = new BinaryTrees();
        binaryTrees.setRoot(root);
        binaryTrees.threadedNodes();
        //测试：以10号节点测试
        HeroNodes leftNode = nodes5.getLeft();
        HeroNodes rightNode = nodes5.getRight();
        System.out.println("10号节点的前驱节点是：" + leftNode);//3
        System.out.println("10号节点的后继节点是：" + rightNode);//1
    }
}
//定义ThreadedBinaryTree 实现了线索化功能的二叉树
class BinaryTrees {
    private HeroNodes root;
    //为了实现线索化，需要创建要给指向当前节点的前驱节点的指针
    //在递归进行线索化时，pre总是保留前一个节点
    private HeroNodes pre = null;
    public void setRoot(HeroNodes root) {
        this.root = root;
    }
    //重载threadedNodes方法
    public void threadedNodes(){
        this.threadedNodes(root);
    }
    //编写对二叉树进行中序线索化的方法
    /**
     *
     * @param nodes 就是当前需要线索化的节点
     */
    public void threadedNodes(HeroNodes nodes){
        //如果nodes == null，不能线索化
        if (nodes == null){
            return;
        }
        //1.先线索化左子树
        threadedNodes(nodes.getLeft());
        //2.线索化当前节点[有难度]
        //处理当前节点的前驱节点
        //以8号节点来理解
        //8节点的.left = null，8节点的.leftType = 1
        if (nodes.getLeft() == null){
            //让当前节点的左指针指向前驱结点
            nodes.setLeft(pre);
            //修改当前节点的左指针的类型，指向前驱节点
            nodes.setLeftType(1);
        }
        //处理后继节点
        if (pre != null && pre.getRight() == null){
            //让前驱节点的有指针指向当前节点
            pre.setRight(nodes);
            //修改前驱结点的右指针类型
            pre.setRightType(1);
        }
        //!!! 每处理一个节点后，让当前节点是下一个节点的前驱节点
        pre = nodes;
        //3.再线索化右子树
        threadedNodes(nodes.getRight());
    }
//*******遍历**************************
    //前序遍历
    public void preOrder1() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //中序遍历
    public void infixOrder1() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //后序遍历
    public void postOrder1() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }
//*******查找**************************
    //前序遍历查找
    public HeroNodes preOrderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序遍历查找
    public HeroNodes infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //后序遍历查找
    public HeroNodes postOrderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        } else {
            return null;
        }
    }
//*******删除**************************
    public void delete(int no){
        if (root != null){
            //如果只有一个root节点，则这里需要立即判断root是否为待删除节点
            if (root.getNo() == no){
                root = null;
            }else {
                root.delete(no);
            }
        }else {
            System.out.println("空树！");
        }
    }
}
//先创建HeroNode节点
class HeroNodes {
    private int no;
    private String name;
    private HeroNodes left;//默认null
    private HeroNodes right;//默认null
    //说明：
    //1.如果leftType == 0 表示指向的是左子树，如果 1则表示指向前驱节点
    //2.如果rightType == 0 便是指向的是右子树，如果 1则表示指向后继节点
    private int leftType;
    private int rightType;
    public HeroNodes(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 HeroNodes getLeft() {
        return left;
    }
    public void setLeft(HeroNodes left) {
        this.left = left;
    }
    public HeroNodes getRight() {
        return right;
    }
    public void setRight(HeroNodes 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 "HeroNodes{" +
                "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);
    }
//*******查找**************************
    //前序遍历查找
    /**
     * @param no 查找no
     * @return 如果找到就返回该Node，如果没有找到，就返回null
     */
    public HeroNodes preOrderSearch(int no) {
        //比较当前节点是不是
        if (this.no == no) {
            return this;
        }
        //1.则判断当前节点的左子节点是否为空，如果不为空，则递归前序查找
        //2.如果左递归前序查找，找到节点，则返回
        HeroNodes resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {//说明我们左子树找到
            return resNode;
        }
        //1.左递归前序查找，找到节点，则返回，否则继续判断
        //2.当前的节点的右子节点是否为空，如果不为空，则继续向右递归前序查找
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }
    //中序遍历查找
    public HeroNodes infixOrderSearch(int no) {
        HeroNodes resNode = null;
        //判断当前节点的左子节点是否为空，如果不为空，则递归中序查找
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //如果没找到，就和当前节点比较，如果是则返回当前节点
        if (this.no == no) {
            return this;
        }
        //否则继续进行右递归的中序查找
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }
    //后序遍历查找
    public HeroNodes postOrderSearch(int no) {
        HeroNodes resNode = null;
        //判断当前节点的左子节点是否为空，如果不为空，则递归后序查找
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //如果左子树没有找到，则向柚子树递归进行后序遍历查找
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //如果左右字数都没有找到，就比较当前节点是不是
        if (this.no == no) {
            resNode = this;
        }
        return resNode;
    }
//*******删除**************************
    //递归删除节点
    //1.如果删除的节点是叶子节点，则删除该节点
    //2.如果删除的节点是非叶子节点，则删除该子树
    /**
     * 思路：
     * 1.因为我们的二叉树是单向的，所以我们是判断当前节点的子节点是否为待删除节点，而不能去判断当前节点是否为待删除节点
     * 2.如果当前节点的左子节点不为空，并且左子节点就是待删除节点，就将this.left = null;并且返回（结束递归删除）
     * 3.如果当前节点的右子节点不为空，并且右子节点就是待删除节点，就将this.right = null;并且返回（结束递归删除）
     * 4.如果2,3步没有删除节点，name我们就需要向左子树进行递归删除
     * 5.如果第4步也没有删除节点，则应当向右子树进行递归删除
     * @param no
     */
    public void delete(int no){
        //2.
        if(this.left != null && this.left.no == no){
            this.left = null;
            return;
        }
        //3.
        if(this.right != null && this.right.no == no){
            this.right = null;
            return;
        }
        //4.
        if (this.left != null){
            this.left.delete(no);
        }
        //5.
        if (this.right != null){
            this.right.delete(no);
        }
    }
}