如何使用Java实现线索化二叉树数据结构？

1.线索化二叉树的介绍

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

问题分析:

1.当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 }

2.但是 6, 8, 10, 14 这几个节点的 左右指针，并没有完全的利用上.

3.如果我们希望充分的利用 各个节点的左右指针， 让各个节点可以指向自己的前后节点,怎么办?

4.解决方案-线索二叉树

概念：当用二叉链表作为二叉树的存储结构时，可以很方便的找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点。所以使用线索化，利用二叉树结构链表的空指针域进行线索化。

2.线索化二叉树的基本特点

n 个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）

这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种

3.线索化二叉树的应用案例

中序线索化二叉树并遍历

应用案例说明：将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}

思路分析

中序遍历的结果：{8, 3, 10, 1, 14, 6}

那么线索化之后的二叉树的左右指针如上图↑

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

• left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的 就是前驱节点.

• right 指向的是右子树，也可能是指向后继节点，比如 ① 节点 right 指向的是右子树，而⑩ 节点的 right 指向的是后继节点.

因此要改变原来的二叉树的结点结构

package com.studySelf.tree.threadedBinaryTree;

/**
 * @author wang
 * @version 1.0
 * @packageName com.studySelf.tree.tree01
 * @className Node
 * @date 2022/4/19 20:15
 * @Description Node结点
 */
public class Node {
    //唯一编号
    private int num;
    //结点的值
    private String name;
    //左结点
    private Node left;
    //右节点
    private Node right;

    //这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点
    private int leftType;
    //这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点
    private int rightType;


    //构造方法

    public Node(int num, String name) {
        this.num = num;
        this.name = name;
    }

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

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeft() {
        return left;
    }

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

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

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

    /**
     * 前序遍历
     */
    public void preSelect() {
        //首先输出根结点
        System.out.println(this);
        //其次判断是否有左结点
        if (this.left != null) {
            //没有左结点，就递归调用本方法输出该结点。
            this.left.preSelect();
        }
        if (this.right != null) {
            this.right.preSelect();
        }
    }

    /**
     * 中序遍历
     */
    public void infixSelect() {
        //首先判断左结点
        if (this.left != null) {
            //如果左结点不为空，递归向左子树调用
            this.left.infixSelect();
        }
        //当左结点为空，再输出根结点。当他本身就是最后一个左结点的时候，会直接输出，且没有右节点
        System.out.println(this);
        if (this.right != null) {
            //右节点同样如此，递归调用。直到没有结点为止。
            this.right.infixSelect();
        }
    }

    /**
     * 设二叉树有三个结点，根结点，左结点，右节点。
     * 后序遍历,解释，当一个二叉树的左结点不为空，那么他会进入下一个递归调用自己的后序遍历方法
     * 此时，根结点就是左结点，这时判断左结点，右节点均为空，就会输出左结点
     * 回退到根结点为this的时候，左结点已经判断完毕，接下来是右节点，右节点不为空，进入后续遍历递归，
     * 此时的this就是右节点，进入递归后，判断，不存在左右结点，输出this，也就是整个二叉树的右节点
     * 回退到this为根结点时，右节点也已经输出，走到最后一步，输出自己也就是this。
     * 整个后序遍历就结束，那么该二叉树的遍历结果就是左，右，根
     */

    public void afterSelect() {
        if (this.left != null) {
            this.left.afterSelect();
        }

        if (this.right != null) {
            this.right.afterSelect();
        }
        System.out.println(this);
    }

    /**
     * @param num
     * @Date 2022/4/21 17:51
     * @Param
     * @Return Node
     * @MetodName preSearchByNum
     * @Author wang
     * @Description 根据结点的编号来查询结点, 前序遍历查询，根，左，右
     */
    public Node preSearchByNum(int num) {
        //首先判断传进来的num与该结点的num是否相等
        //如果相等，那该结点就是我们要找的结点。
        if (this.num == num) {
            return this;
        }

        //如果不相等，该结点就不是我们要找的结点
        //那么我们就遍历该结点的左子节点，和右子结点
        //定义一个结点用于接收最后的返回结果
        Node resultNode = null;
        //如果该结点的左子结点不为空，就递归调用前序遍历，继续查找，如果找到了，那么resultNode就是我们想要的值
        if (this.left != null) {
            resultNode = this.left.preSearchByNum(num);
        }

        //如果遍历完左子结点，已经找到了我们想要的结果，直接返回结果即可，
        if (resultNode != null) {
            return resultNode;
        }

        //如果左子结点为空，且没有找到我们想要的结点的情况下。那就判断右子结点
        if (this.right != null) {
            resultNode = this.right.preSearchByNum(num);
        }
        //最后，如果找到了，那么resultNode一定会被赋值，如果没找到，就会返回null
        return resultNode;
    }

    /**
     * @param num
     * @Date 2022/4/21 17:58
     * @Param
     * @Return Node
     * @MetodName infixSearchByNum
     * @Author wang
     * @Description 中序遍历查找，左，根，右进行查询即可。
     */
    public Node infixSearchByNum(int num) {
        //首先判断左子结点,如果存在左子结点，递归继续查询遍历即可即可。
        Node resultNode = null;
        if (this.left != null) {
            resultNode = this.left.infixSearchByNum(num);
        }

        //如果左子结点已经找到了我们想要的结点，直接返回当前结点即可
        if (resultNode != null) {
            return resultNode;
        }

        //判断根结点
        if (this.num == num) {
            return this;
        }

        //判断右子结点，
        if (this.right != null) {
            resultNode = this.right.infixSearchByNum(num);
        }
        //最后返回我们的结果即可。
        return resultNode;
    }


    /**
     * @param num
     * @Date 2022/4/21 19:15
     * @Param
     * @Return Node
     * @MetodName afterSearchNum
     * @Author wang
     * @Description 后续遍历结点进行查找结点。左，右，根
     */
    public Node afterSearchNum(int num) {
        Node resultNode = null;
        //首先遍历左结点
        if (this.left != null) {
            resultNode = this.left.afterSearchNum(num);
        }

        //判断左结点是否找到哦啊
        if (resultNode != null) {
            return resultNode;
        }

        //判断右节点是否为空
        if (this.right != null) {
            resultNode = this.right.afterSearchNum(num);
        }

        //判断右节点是否找到
        if (resultNode != null) {
            return resultNode;
        }

        //判断根结点是否为我们找的结点
        if (this.num == num) {
            return this;
        }
        //最后返回
        return resultNode;
    }

    /**
     * @param num
     * @Date 2022/4/25 19:30
     * @Param
     * @Return void
     * @MetodName delNodeByNum
     * @Author wang
     * @Description 根据结点的编号删除结点
     */
    public void delNodeByNum(int num) {
        //首先，判断当前结点的左结点是否为空，并且左结点的num是否与num相等
        if (this.left != null && this.left.num == num) {
            //如果相等，那就说明该结点就是我们要删除的结点,将其左结点置空即可
            this.left = null;
            return;
        }

        //如果左结点没有执行，说明左结点没有我们想要的结果，也就是要删除的结点不在左结点
        //那么就对右节点进行判断
        if (this.right != null && this.right.num == num) {
            this.right = null;
            return;
        }

        //如果左右结点均没有找到目标结点
        //那么就对左子树进行递归删除操作
        if (this.left != null) {
            this.left.delNodeByNum(num);
        }

        //同理，如果左子树没有目标结点，向右子树进行递归删除操作
        if (this.right != null) {
            this.right.delNodeByNum(num);
        }

    }
}

可以看到我们多出来了这么两个属性：

    //这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点
    private int leftType;
    //这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点
    private int rightType;

中序线索化二叉树

  /**中序线索化二叉树*/
    /**
     * @param node 该结点为根结点，从根节点开始线索化二叉树，中序
     */
    public void infixThreadNodes(Node node) {
        /**首先判断二叉树的根节点上会否为空，如果根结点为空，不可以线索化，因为没有二叉树*/
        if (node == null) {
            return;
        }

        /**接着对左子树进行线索化*/
        infixThreadNodes(node.getLeft());

        /**对当前结点进行线索化*/
        /**首先判断当前结点的左子结点是否为空*/
        if (node.getLeft() == null) {
            //如果左子结点为空，说明就找到了我们需要线索化的结点
            //就可以将pre也就是一直在当前结点的前趋结点设置给当前结点的左子结点，
            //如果这是第一个结点，那么pre为空，正好第一个结点的前趋结点也为空
            node.setLeft(pre);
            //并且将它的左子结点的类型设置为前趋结点。1代表前趋结点
            node.setLeftType(1);
        }

        /**接着判断前趋结点的右子结点是否为空，前提是前趋结点不能为空，如果他为空，说明这是第一个结点还没走完*/
        if (pre != null && pre.getRight() == null) {
            //如果条件满足，说明前趋结点现在已经走到了值，并且还没有线索到后继结点，
            // 也就是当前结点的上一个结点（这个上一个结点就是当前的前趋结点）还没有后继，
            //那么上一个结点的后继结点就是当前结点，因此赋值前趋结点（也就是上一个结点）的后继结点为当前结点。
            //这样这条线索就连接上了,并且只有满足叶子结点的结点才可以进行线索化
            pre.setRight(node);
            pre.setRightType(1);
        }

        //当前两步走完之后，就可以将pre结点赋值为当前结点，
        // 因为下一个结点一走，当前结点就是前趋结点了。直到走到全部线索化结束
        //这步十分重要，这一步不写，整个线索化就连接不上
        pre = node;

        /**对右子树进行线索化*/
        infixThreadNodes(node.getRight());
    }

中序线索化二叉树思路

1. 因为中序遍历的二叉树顺序是左根右，因此，首先对左子树进行线索化，递归线索化即可；

2. 当递归到左子树的最左结点的时候，他的左结点肯定为空，那么就对他的左结点赋值为pre（pre结点是在线索化的最后一步赋值为当前结点，这样递归才能进行下去）,注意左结点的类型一定要改为1，代表他是前趋结点。前趋结点就线索掉了。

3. 后继结点的处理则是判断前趋结点，当前趋结点不为空，并且前趋结点的右节点为空，那么设置前趋结点的右节点为当前结点，也就是上一个结点未设置的右节点，类型同样要设置为后继

4. 最后就是对pre这个结点赋值，为当前结点，因为下一次递归，当前结点就成了上一个结点，也就是这里的pre

5. 最后就是对二叉树的右子结点进行线索化。

中序线索化二叉树的遍历

1. 遍历中序线索化二叉树首先应该明确的是他的遍历顺序要和遍历原来的中序二叉树遍历的结果是一样的，才是遍历成功

2. 那么第一步应该就是判断根结点不为空，也就是循环结束条件

3. 接着就循环查找当前结点的左子结点类型为0的也就是没有被线索化的结点，只要他为0，那么结点就一直往左子结点赋值。直到找到第一个被线索化的结点，输出他，他就是我们第一个线索化并且也是中序遍历的第一个左子结点。

4. 输出之后，判断他的右子结点是否被线索化，如果被线索化，那么当前结点node就被赋值为它自己的右子结点，并且输出，如果他之后的结点的右子结点的类型又为1，那么继续往后走并赋值，说明他有后继

5. 直到右子结点的类型为0，退出循环之后，也应该向右再赋值，继续向后遍历

代码演示

    /**遍历中序线索化二叉树*/
    public void infixThreadNodesSelect() {
        /**第一个结点为根结点*/
        Node node = root;
        while(node != null) {
            /**当结点不为空，就一直遍历*/
            /**当该结点的左子结点的类型为1的时候，也就是说该结点是被线索化的结点,
             * 因为是中序遍历，所以应该遍历到最左边的最左子结点，那么就是第一个
             * 左子结点类型为1的结点。*/
            while(node.getLeftType() == 0) {
                node = node.getLeft();
            }
            /**当左子结点的类型为1,输出左子结点*/
            System.out.println(node);

            /**当右子结点类型为1，当前结点输出完毕后
             * 中序遍历就应该输出右子结点，那么就是当前结点的右子结点类型只要为1，就往后移动
             * 并且输出，当他为0，说明没有线索化，那么没有后继结点，但是他有右子结点，
             * 因此要在循环结束以后向后移动。*/
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }
            /**当右子结点循环退出，说明这里到了类型为0也就是后继结点*/
            node = node.getRight();
        }

4.前序线索化二叉树、遍历

线索化二叉树

 /**
     * 前序线索化二叉树
     */
    public void preThreadNodes(Node node) {
        /**首先判断当前节点是否为空*/
        if (node == null) {
            return;
        }

        /**如果是前序遍历，那么先对当前结点进行判断，当前结点的前趋结点的操作*/
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }

        /**处理后继结点,定义的前趋结点不为空，说明他有值，就是已经存在了上一个结点的值，他的右子结点没有值的话，就可以
         * 给他赋予后继结点为当前结点，这里赋予的也就是上一个结点*/
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }

        /**这里是关键的一步*/
        pre = node;

        /**对左子结点进行线索化,注意，这里需要排除已经被线索化掉的结点,因为这里要考虑一个情况，
         * 比如这里已将到了最下面一个左子结点，由于是前序遍历，遍历到左子结点，他的前趋结点在上面就设置了
         * 如果这里不判断左子结点的类型，那么就会进入递归，但是这个递归如果进去了，就是错误的递归，因为他传过去的结点
         * 是我们刚刚给他赋值的前趋结点，也就是根结点。会发生错误。因此得判断类型*/
        if (node.getLeftType() != 1) {
            preThreadNodes(node.getLeft());
        }


        /**对右子结点进行递归线索化*/
        if (node.getRightType() != 1) {
            preThreadNodes(node.getRight());
        }
    }

 遍历线索化二叉树

/**
     * 前序遍历线索二叉树*/
    public void preThreadNodeSelect() {
        Node node = root;
        while(node !=null) {
            while(node.getLeftType() == 0) {
                /**前序遍历为根左右，先输出根结点,因为他每次进来循环肯定是先到根结点，所以一进该循环
                 * 就要输出根结点，当他的lefttype=1循环结束，说明遇到了被线索化的地方了。*/
                System.out.println(node);
                /**再最左子结点进行遍历*/
                node = node.getLeft();
            }
            /**上面的循环结束之后就应该输出当前结点，也就是那个序列化的结点
             * 之后结点向右移动继续遍历*/
            System.out.println(node);
            node = node.getRight();
        }
  }

图解

5.后序线索化二叉树

后续线索化二叉树

/**
 * 后序线索化二叉树的方法
 */
public void postThreadedBinaryTree(Node node) {
    /**首先判断结店不能为空*/
    if (node == null) {
        return;
    }

    /**先后续线索化左子结点*/
    postThreadedBinaryTree(node.getLeft());
    /**在后续线索化右子结点*/
    postThreadedBinaryTree(node.getRight());

    /**处理当前结点的前趋结点*/
    if (node.getLeft() == null) {
        node.setLeft(pre);
        node.setLeftType(1);
    }

    /**处理后继结点*/
    if (pre != null && pre.getRight() == null) {
        pre.setRight(node);
        pre.setRightType(1);
    }
    pre = node;
}