线索二叉树操作

树节点

public class ThreadedTreeNode<T> {
    private T data;
    private ThreadedTreeNode<T> left;
    private ThreadedTreeNode<T> right;
    /**
     * 当左右指针指向左右子树时，值为0；否则，值为1
     */
    private int leftPointerType;
    private int rightPointerType;

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public ThreadedTreeNode<T> getLeft() {
        return left;
    }

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

    public ThreadedTreeNode<T> getRight() {
        return right;
    }

    public void setRight(ThreadedTreeNode<T> right) {
        this.right = right;
    }

    public int getLeftPointerType() {
        return leftPointerType;
    }

    public void setLeftPointerType(int leftPointerType) {
        this.leftPointerType = leftPointerType;
    }

    public int getRightPointerType() {
        return rightPointerType;
    }

    public void setRightPointerType(int rightPointerType) {
        this.rightPointerType = rightPointerType;
    }
}

创建中序线索二叉树

/**
 * 前驱节点
 */
private static ThreadedTreeNode<Integer> prevNode = null;

public static void createInOrderThreadedBinaryTree(ThreadedTreeNode<Integer> node) {
    if (node != null) {
        createInOrderThreadedBinaryTree(node.getLeft());
        /**
         * 若当前节点的左指针指向null，将当前节点的左指针指向前驱节点
         */
        if (node.getLeft() == null) {
            node.setLeft(prevNode);
            node.setLeftPointerType(1);
        }
        /**
         * 若前驱节点的右指针指向null，将前驱节点的右指针指向当前节点
         */
        if (prevNode != null && prevNode.getRight() == null) {
            prevNode.setRight(node);
            prevNode.setRightPointerType(1);
        }
        /**
         * 将当前节点作为前驱节点后，再处理右子树
         */
        prevNode = node;

        createInOrderThreadedBinaryTree(node.getRight());
    }
}

遍历中序线索二叉树

public static List<Integer> iterateInOrderThreadedBinaryTree(ThreadedTreeNode<Integer> node) {
    if (node != null) {
        List<Integer> list = new ArrayList<>();

        while (node != null) {
            /**
             * 找到中序遍历二叉树时的第一个节点
             */
            while (node.getLeftPointerType() == 0) {
                node = node.getLeft();
            }
            list.add(node.getData());
            while (node.getRightPointerType() == 1) {
                node = node.getRight();
                list.add(node.getData());
            }
            node = node.getRight();
        }
        return list;
    }
    return null;
}

创建前序线索二叉树

/**
 * 前驱节点
 */
private static ThreadedTreeNode<Integer> prevNode = null;

public static void createPreOrderThreadedBinaryTreeTest(ThreadedTreeNode<Integer> node) {
    if (node != null) {
        /**
         * 若当前节点的左指针指向null，将当前节点的左指针指向前驱节点
         */
        if (node.getLeft() == null) {
            node.setLeft(prevNode);
            node.setLeftPointerType(1);
        }
        /**
         * 若前驱节点的右指针指向null，将前驱节点的右指针指向当前节点
         */
        if (prevNode != null && prevNode.getRight() == null) {
            prevNode.setRight(node);
            prevNode.setRightPointerType(1);
        }
        /**
         * 将当前节点作为前驱节点后，再处理左、右子树
         */
        prevNode = node;

        if (node.getLeftPointerType() == 0) {
            /**
             * 当所有左子节点都递归处理完后，prevNode指向最后一个左子节点，
             * prevNode的下一个节点是最后一个右子节点
             */
            createPreOrderThreadedBinaryTreeTest(node.getLeft());
        }

        if (node.getRightPointerType() == 0) {
            /**
             * 当一个右子节点处理完后，prevNode指向当前右子节点，
             * prevNode的下一个节点是上一层的右子节点
             */
            createPreOrderThreadedBinaryTreeTest(node.getRight());
        }
    }
}

遍历前序线索二叉树

public static List<Integer> iteratePreOrderThreadedBinaryTree(ThreadedTreeNode<Integer> node) {
  List<Integer> list = new ArrayList<>();
    while (node != null) {

        while (node.getLeftPointerType() == 0) {
            list.add(node.getData());
            node = node.getLeft();
        }
        /**
         * 上面循环结束后，当前节点已没有左子节点，左指针指向后继结点，
         * 将当前节点的值记录下来后，处理其右指针指向的节点
         */
        list.add(node.getData());
        node = node.getRight();
    }
    return list;
}

参考：https://blog.csdn.net/uncleming5371/article/details/54176252