java数据结构和算法——线索化二叉树

一、二叉树问题分析

1、将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树，如下图： 2、问题分析:

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

二、线索二叉树的基本介绍

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

三、中序线索化二叉树思路分析

四、中序线索化二叉树代码示例

1、代码

package com.rf.springboot01.dataStructure.tree;

/**
 * @description: 中序线索二叉树示例
 * @author: xiaozhi
 * @create: 2020-09-03 22:38
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        //创建节点
        Nodes root = new Nodes(1);
        Nodes node2 = new Nodes(3);
        Nodes node3 = new Nodes(6);
        Nodes node4 = new Nodes(8);
        Nodes node5 = new Nodes(10);
        Nodes node6 = new Nodes(14);

        //手动创建二叉树
        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号节点测试
        Nodes leftNode = node5.getLeft();
        Nodes rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是 ="  + leftNode); //3
        System.out.println("10号结点的后继结点是="  + rightNode); //1
    }

}

/**
* @Description:  创建ThreadedBinaryTree， 实现了线索化功能的二叉树
* @Param:
* @Author: xz
* @return:
* @Date: 2020/9/3 22:44
*/
class ThreadedBinaryTree{

    private Nodes root;
    public void setRoot(Nodes root) {
        this.root = root;
    }
    //重载一把threadedNodes方法
    public void threadedNodes() {
        this.threadedNodes(root);
    }
    //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
    //在递归进行线索化时，pre 总是保留前一个结点
    private Nodes pre = null;
    //编写对二叉树进行中序线索化的方法
    public void threadedNodes(Nodes nodes){
        //如果nodes==null, 不能线索化
        if(nodes == null){
            return;
        }
        //一、先线索化左子树
        threadedNodes(nodes.getLeft());
        //二、处理当前结点的前驱结点
        //以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;
        //四、先线索化右子树
        threadedNodes(nodes.getRight());
    }

}

/**
* @Description:  创建 Nodes 结点
* @Param:
* @Author: xz
* @return:
* @Date: 2020/9/3 22:41
*/
class Nodes{
    private int no;
    private Nodes left;//二叉树的左节点，默认null
    private Nodes right;//二叉树的右节点，默认null
    private int leftType;//0 表示指向的是左子树;1 表示指向前驱结点
    private int rightType;//0 表示指向是右子树;1表示指向后继结点

    //构造方法
    public Nodes(int no) {
        this.no = no;
    }

    //setter、getter方法
    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Nodes getLeft() {
        return left;
    }

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

    public Nodes getRight() {
        return right;
    }

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

2、运行main函数，输出结果如下：

五、遍历线索化二叉树代码示例

1、在ThreadedBinaryTree类中添加遍历线索化二叉树的方法

//遍历线索化二叉树的方法
    public void threadedList() {
        //定义一个变量，存储当前遍历的结点，从root开始
        Nodes node = root;
        while(node != null) {
            //循环的找到leftType == 1的结点，第一个找到就是8结点
            //后面随着遍历而变化,因为当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();

        }
    }

2、在ThreadedBinaryTreeDemo类中添加如下调用方法

 System.out.println("使用线索化的方式遍历线索化二叉树=====");
 threadedBinaryTree.threadedList(); //输出： 8, 3, 10, 1, 14, 6

3、输出结果如下