数据结构与算法分析----中序线索化二叉树+中序遍历

数据结构与算法分析----中序线索化二叉树+中序遍历

目录

• • 概述
  • 线索化二叉树的实现
  • • 中序遍历构建
    • 中序线索化二叉树的遍历
    • 代码

概述

百度百科：
在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。

原二叉树的某些结点的左指针或右指针或左右指针是空的，浪费资源，我们可以让这些指针指向其他的一些结点，方便遍历和查找
我们用某一种方式(前中后序)遍历二叉树，在某个结点前面打印的称为此结点的前驱结点，在这个结点后面打印的称为后继结点。
我们线索化二叉树要做的就是让结点的空指针指向他们的前驱或者后继结点，左指针指向前驱结点，右指针指向后继结点。
经此处理过的二叉树就是线索化二叉树

线索化二叉树的实现

首先构建结点：
对于原节点的构建，在原二叉树的节点上我们需要再加入两个属性，一个用来标记左子结点是否被线索化，一个用来标记右子结点是否被线索化
这里用两个int类型的遍历记录，当为正常的子结点则默认为0，若为线索化的结点，则设置为1
除了属性外，其他的都是一些很常规的方法

构建这样的一个二叉树

要知道的小知识：
前中后三种构建的线索化二叉树对应遍历方式也不同

然后，很重要一点，我们要对二叉树进行线索化，则一定会需要遍历过程中当前结点的前驱结点，所以我们要设置一个变量来时刻记录当前所遍历的结点的上一个结点，三种构建方法需要如此
下面我们设置一个变量pre来表示

中序遍历构建

中序遍历构建就是对原二叉树进行中序遍历，在遍历的过程中对原二叉树进行线索化
思路：
遍历构建，递归进行，这里递归的结束条件是当前节点为空，即表示遍历构建完成，然后进行正常的遍历，在该打印结点的地方，判断当前结点的左子结点是否为空，为空则让左子结点指向pre，这个步骤即表示为当前结点连接上前驱结点，然后修改标记左子结点的变量，设置为1。然后判断pre结点是否为空，为空则让pre所指向的结点的右子节点指向当前结点，这个步骤即表示为让点前结点的前驱结点连接上当前结点，当前结点即作为上一个结点的后继结点。然后更改pre的值，让pre指向当前结点
对上面思路的分析：
首先我们需要直到递归遍历二叉树的原理：
每次的递归最多只能打印一个结点，也就是说，如有两个满足打印条件的递归，且他们之间没有满足打印条件的递归，则这两次所打印的两个结点，前面的便是后面的前驱结点，后面的便是前面的后继结点。
在一次的递归中，首先是当前结点的左子结点连接前驱结点(pre)，然后是前驱结点(pre)的右子结点连接后继结点(当前结点)，然后更换pre的值，pre指向当前结点，此时，若进入下一次的递归，pre便成为了下一次递归中该打印的结点的前驱结点，然后就按照前面所说的步骤，就没有一点问题，当第一次满足打印条件，则此时pre实际是null，但这正好，正好此时的当前节点没有前驱结点
pre是我们用来记录当前所遍历的结点的前驱结点的
遍历完成，即线索化完成

中序线索化二叉树的遍历

这里，我们用循环来遍历，线索化后的二叉树，便利起来要简单一点，而且效率更高
首先，我们一直从根结点一直向左取子结，得到第一个需要输出的结点，在此处，找到的标志是当前结点的左子结点被标记为线索化后的结点，即LeftType!=0。虽然此时这个结点的前驱结点是null，但是在我们构建的过程中，我们依然把第一个结点的LeftType标记为1。所以此处不用担心找不到还有空指针域的问题。
然后打印当前结点，然后就简单了，直接按照我们的线索进行输出打印，直接用while循环，若右结点被标记为1，则持续node=node.getRight();然后打印，若遇到不为1，则表示我们遇到了一个右子结点不是线索化的结点(类似于我们上图二叉树中的1结点)，此时，按照中序遍历的规矩，到这里，说明此结点的左子结点已经输出，此时轮到自身输出了，所以此时我们打印一下自己，然后把当前结点换成当前结点的右子结点即可，即node=node.getRight()。这里需要注意一点，我们这个while循环体中是先更换当前结点，再输出，再判断的，所以这里出了while后不用再打印一次


确实没有问题

代码

public class ThreadedBinaryTree {
    public static void main(String[] args) {
        Node02 root=new Node02(0,"Hi");
        Node02 node1=new Node02(1,"你");
        Node02 node2=new Node02(2,"好");
        Node02 node3=new Node02(3,"牛");
        Node02 node4=new Node02(4,"蛙");
        Node02 node5=new Node02(5,"！");

        root.setLeft(node1);
        root.setRight(node2);
        node1.setLeft(node3);
        node1.setRight(node4);
        node2.setLeft(node5);

        ThreadedBinaryTreeDemo threadedBTree=new ThreadedBinaryTreeDemo(root);
        threadedBTree.ThreadedBTree();

        threadedBTree.List();
    }
}
//将
class ThreadedBinaryTreeDemo{
    private Node02 root;

    public ThreadedBinaryTreeDemo(Node02 root) {
        this.root = root;
    }

    private Node02 pre;

    public void ThreadedBTree(){
        pre=null;
        if (root==null){
            System.out.println("树空");
            return;
        }
        ThreadedBTree(root);
    }

//    中序遍历线索化二叉树
    public void List(){
        Node02 node=root;

        while (node!=null){
            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();
        }
    }

    private void ThreadedBTree(Node02 node){
        if (node==null){
            return;
        }
        ThreadedBTree(node.getLeft());
        if (node.getLeft()==null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre!=null&&pre.getRight()==null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre=node;
        ThreadedBTree(node.getRight());
    }
}
class Node02{
    private int id;
    private String name;
    private Node02 left;
    private Node02 right;
    private int LeftType;   //记录左子结点是否线索化
    private int RightType;   //记录右子节点是否线索化

    public int getLeftType() {
        return LeftType;
    }
    public void setLeftType(int leftType) {
        LeftType = leftType;
    }
    public int getRightType() {
        return RightType;
    }
    public void setRightType(int rightType) {
        RightType = rightType;
    }
    public Node02(int id, String name) {
        this.id = id;
        this.name = name;
    }
    public void setId(int id) {
        this.id = id;
    }
    public void setName(String name) {
        this.name = name;
    }
    public void setLeft(Node02 left) {
        this.left = left;
    }
    public void setRight(Node02 right) {
        this.right = right;
    }
    public int getId() {
        return id;
    }
    public String getName() {
        return name;
    }
    public Node02 getLeft() {
        return left;
    }
    public Node02 getRight() {
        return right;
    }

    @Override
    public String toString() {
        return "Node02{" +
                "id=" + id +
                ", name='" + name + ''' +
                '}';
    }
}