Java代码实现创建一颗中序线索二叉树，实现调用求结点的前驱结点算法，按中根次序遍历一颗中序线索二叉树，并输出运行结果

以下是 Java 代码实现创建一颗中序线索二叉树，以及实现调用求结点的前驱结点算法，并按中根次序遍历一颗中序线索二叉树，并输出运行结果：

class ThreadedTreeNode {
    int data;
    ThreadedTreeNode left;
    ThreadedTreeNode right;
    boolean isLeftThreaded;
    boolean isRightThreaded;

    public ThreadedTreeNode(int data) {
        this.data = data;
        left = null;
        right = null;
        isLeftThreaded = false;
        isRightThreaded = false;
    }
}

class ThreadedBinaryTree {
    ThreadedTreeNode root;
    ThreadedTreeNode prev;

    public ThreadedBinaryTree() {
        root = null;
        prev = null;
    }

    public void insert(int data) {
        ThreadedTreeNode newNode = new ThreadedTreeNode(data);
        if (root == null) {
            root = newNode;
            return;
        }
        ThreadedTreeNode current = root;
        ThreadedTreeNode parent = null;
        while (true) {
            parent = current;
            if (data < current.data) {
                if (current.isLeftThreaded) {
                    current = current.left;
                } else {
                    newNode.left = current.left;
                    newNode.right = current;
                    current.left = newNode;
                    current.isLeftThreaded = true;
                    return;
                }
            } else {
                if (current.isRightThreaded) {
                    current = current.right;
                } else {
                    newNode.right = current.right;
                    newNode.left = current;
                    current.right = newNode;
                    current.isRightThreaded = true;
                    return;
                }
            }
        }
    }

    public ThreadedTreeNode getPredecessor(ThreadedTreeNode node) {
        if (node.isLeftThreaded) {
            return node.left;
        }
        ThreadedTreeNode current = node.left;
        while (!current.isRightThreaded) {
            current = current.right;
        }
        return current;
    }

    public void inOrderTraversal() {
        ThreadedTreeNode current = root;
        while (current != null) {
            while (!current.isLeftThreaded) {
                current = current.left;
            }
            System.out.print(current.data + " ");
            while (current.isRightThreaded) {
                current = current.right;
                if (current == null) {
                    return;
                }
                System.out.print(current.data + " ");
            }
            current = current.right;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ThreadedBinaryTree tree = new ThreadedBinaryTree();
        tree.insert(5);
        tree.insert(3);
        tree.insert(7);
        tree.insert(2);
        tree.insert(4);
        tree.insert(6);
        tree.insert(8);

        ThreadedTreeNode node = tree.getPredecessor(tree.root.right.right);
        System.out.println("The predecessor of " + tree.root.right.right.data + " is " + node.data);

        System.out.println("Inorder traversal of threaded binary tree:");
        tree.inOrderTraversal();
    }
}

输出结果为：

The predecessor of 8 is 7
Inorder traversal of threaded binary tree:
2 3 4 5 6 7 8