Java代码实现在一颗中序线索二叉树中按后根次序遍历中序线索二叉树

以下 Java 代码实现：

class Node {
    int val;
    Node left, right;
    boolean lTag, rTag;

    public Node(int val) {
        this.val = val;
    }
}

public class ThreadedBinaryTree {
    Node root, pre;

    public ThreadedBinaryTree(Node root) {
        this.root = root;
        pre = null;
        if (root != null) {
            inOrderThreading(root);
            if (pre.right == null) {
                pre.rTag = true;
            }
        }
    }

    private void inOrderThreading(Node p) {
        if (p != null) {
            inOrderThreading(p.left);
            if (p.left == null) {
                p.lTag = true;
                p.left = pre;
            }
            if (pre != null && pre.right == null) {
                pre.rTag = true;
                pre.right = p;
            }
            pre = p;
            inOrderThreading(p.right);
        }
    }

    public void postOrderTraverse() {
        if (root != null) {
            Node p = root;
            while (p.lTag == false || p.rTag == false) {
                while (p.lTag == false) {
                    p = p.left;
                }
                while (p.rTag == true || p.right == null) {
                    System.out.print(p.val + " ");
                    if (p == root) {
                        return;
                    }
                    p = p.right;
                }
                p = p.right;
            }
            System.out.print(p.val + " ");
        }
    }
}

在中序线索二叉树中按后根次序遍历二叉树时，我们需要先找到最后一个访问的结点，即右子树为空的结点。然后，沿着指向该结点的右线索，依次访问其祖先结点的右儿子，直到回到根结点为止。这个过程可以用一个 while 循环实现。在访问结点时，我们需要注意到该结点可能是前一个结点的右子树，因此需要判断是否回到了根结点。