线索化二叉树

1. 问题分析

• 当对上面的二叉树进行中序遍历时，序列应为：[8,3,10,1,14,6]；
• 但存在一个问题也即，编号为6，8，10，14的几个节点的左右指针并没有完全利用上；
• 如果希望利用到各个节点的左右指针，让各个节点可以指向自己的前后节点，即使用线索化二叉树。

2. 线索化二叉树基本介绍

• n个节点的二叉链表中含有n + 1个空指针域；利用二叉链表中的空指针域，存放指向该节点在某种遍历次序（前序、中序或后序）下的前驱和后继节点的指针（这种附加的指针称为“线索”）
  • 公式推导：n个节点共有2n个指针域，除了根节点外的每个节点都有被指针指向（n-1），所以空指针域有2n - (n - 1) = n + 1
• 这种加上了“线索”的二叉链表称为线索链表，相应的二叉树称为线索二叉树（Threaded Binary Tree）。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树
• 前驱节点：即一个节点的前一个节点。以上图的中序线索二叉树为例，中序遍历结果为：[8,3,10,1,14,6]，10节点的前驱节点为3节点。但对8节点而言，其虽然左子节点为空但在序列中8节点没有前一个节点，因此8节点没有前驱节点
• 后继节点：即一个节点的后一个节点。同样以上图的中序线索二叉树为例，中序遍历结果为：[8,3,10,1,14,6]，10节点的后继节点为1节点。但对6节点而言，其虽然右子节点为空但在序列中6节点没有后一个节点，因此6节点没有后继节点

3. 中序线索化二叉树思路分析

• 当线索化二叉树后，node节点的left和right指针有如下情况：
  • left指向左子树，也可能指向node节点的前驱节点。eg.1节点的left指向左子树，而10节点的left指向前驱节点3；
  • right指向右子树，也可能指向node节点的后继节点。eg.1节点的right指向右子树，而10节点的right指向后继节点1.
• 此时就需要在节点类中定义两个变量leftType和rightType，分别表示left和right所指向的类型。默认为0表示指向对应的左/右子树；当对节点进行线索化时，就需要将相应的leftType/rightType置为1，表示指向前驱节点/后继节点；
• 同时，在实现线索化的过程中，还需要定义一个preNode表示指向当前节点的前驱节点，初始化为null；
  • 需要注意的是，处理前驱节点和后继节点并不是在同一轮递归中实现的；
  • 处理后继节点时，应以preNode为基准，执行preNode.setRight(node)操作，也即将前驱节点的右指针指向当前节点；
  • 每处理完一个节点，就置preNode = node，也即令当前节点作为下一个待处理节点的前驱节点。

4. 中序线索化二叉树遍历思路分析

• 线索化后，各个节点的指向有所变化，因此不能直接使用原来的中序遍历方式。进行遍历时应判断节点的leftType和rightType，另外需注意，遍历的次序应与线索化二叉树的类型保持一致，即中序线索化二叉树必须用中序线索化遍历。

5. 中序线索化二叉树实现 + 遍历代码实现

package com.datastructure;

/**
 * @author SnkrGao
 * @create 2023-05-09 19:29
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {

        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();

        ThreadedTreeNode root = new ThreadedTreeNode(1, "tom");
        ThreadedTreeNode node2 = new ThreadedTreeNode(3, "jerry");
        ThreadedTreeNode node3 = new ThreadedTreeNode(6, "mike");
        ThreadedTreeNode node4 = new ThreadedTreeNode(8, "marry");
        ThreadedTreeNode node5 = new ThreadedTreeNode(10, "smith");
        ThreadedTreeNode node6 = new ThreadedTreeNode(14, "lisa");

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        threadedBinaryTree.setRoot(root);

        // 中序线索化二叉树
        threadedBinaryTree.threadedNodes(root);

        System.out.println("节点10的前驱节点为：" + node5.getLeft());
        System.out.println("节点10的后继节点为：" + node5.getRight());

        System.out.println("中序线索化二叉树遍历结果：");
        threadedBinaryTree.inorderThreadedTraversal();


    }
}

class ThreadedBinaryTree {
    private ThreadedTreeNode root;

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

    // preNode指向当前节点的前驱节点
    private ThreadedTreeNode preNode = null;

    /**
     * 中序线索化二叉树
     * @param node 表示当前节点
     */
    public void threadedNodes(ThreadedTreeNode node) {
        // 判断当前节点是否为空
        if (node == null) {
            return;
        }

        // 线索化左子树
        threadedNodes(node.getLeft());

        // 线索化当前节点
        if (node.getLeft() == null) {
            // 当前节点的左指针指向前驱节点
            node.setLeft(preNode);
            node.setLeftType(1);
        }
        // 以preNode为基准，处理当前节点的后继节点
        if (preNode != null && preNode.getRight() == null) {
            preNode.setRight(node);
            preNode.setRightType(1);
        }
        // 每处理完一个节点，令当前节点作为下一个待处理节点的前置节点
        preNode = node;

        // 线索化右子树
        threadedNodes(node.getRight());
    }

    // 中序遍历线索化二叉树
    public void inorderThreadedTraversal() {
        // 表示当前遍历的节点，从root开始遍历
        ThreadedTreeNode node = root;

        while (node != null) {
            // 循环遍历找到第一个leftType == 1的节点，即左子节点为空的节点
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
            System.out.println(node);
            // 若当前节点的右指针指向的是后继节点，一直输出
            while (node.getRightType() == 1) {
                System.out.println(node.getRight());
                node = node.getRight();
            }
            // 后移，继续遍历
            node = node.getRight();
        }
    }
}

class ThreadedTreeNode {
    private int no;
    private String name;
    private ThreadedTreeNode left;
    private ThreadedTreeNode right;

    // 若leftType == 0表示指向左子树，若为1表示指向前驱节点
    private int leftType;
    // 若rightType == 0表示指向右子树，若为1表示指向后继节点
    private int rightType;

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

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

    public ThreadedTreeNode getRight() {
        return right;
    }

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