Java代码实现在一颗中序线索二叉树中按后根次序遍历中序线索二叉树，并输出运行结果

以下是 Java 代码实现，在中序线索二叉树中按后根次序遍历，并输出运行结果：

public class Main {
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);

        ThreadedBinaryTree tree = new ThreadedBinaryTree(root);
        System.out.print("后根次序遍历中序线索二叉树：");
        tree.postOrderTraverse();
    }
}

输出结果为：

后根次序遍历中序线索二叉树：4 5 2 6 7 3 1

相关问题

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 循环实现。在访问结点时，我们需要注意到该结点可能是前一个结点的右子树，因此需要判断是否回到了根结点。

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

以下是Java代码实现中序线索二叉树和求前驱结点算法：

class ThreadedBinaryTreeNode {
    int value;
    ThreadedBinaryTreeNode left;
    ThreadedBinaryTreeNode right;
    boolean isLeftThreaded;
    boolean isRightThreaded;

    public ThreadedBinaryTreeNode(int value) {
        this.value = value;
        this.isLeftThreaded = false;
        this.isRightThreaded = false;
    }
}

class ThreadedBinaryTree {
    private ThreadedBinaryTreeNode root;

    public ThreadedBinaryTree(ThreadedBinaryTreeNode root) {
        this.root = root;
        if (root != null) {
            inOrderThread(root, null);
        }
    }

    // 将以node为根节点的子树线索化
    private ThreadedBinaryTreeNode inOrderThread(ThreadedBinaryTreeNode node, ThreadedBinaryTreeNode prev) {
        if (node == null) {
            return null;
        }
        ThreadedBinaryTreeNode left = node.left;
        ThreadedBinaryTreeNode right = node.right;

        if (left == null) {
            node.left = prev;
            node.isLeftThreaded = true;
        } else {
            node.left = inOrderThread(left, prev);
        }

        if (right == null) {
            node.right = null;
            node.isRightThreaded = true;
        } else {
            node.right = inOrderThread(right, node);
        }

        return node;
    }

    // 求节点的前驱节点
    public ThreadedBinaryTreeNode getPredecessor(ThreadedBinaryTreeNode node) {
        if (node == null) {
            return null;
        }
        if (node.isLeftThreaded) {
            return node.left;
        }
        ThreadedBinaryTreeNode prev = node.left;
        while (prev != null && !prev.isRightThreaded) {
            prev = prev.right;
        }
        return prev;
    }

    // 按中根次序遍历
    public void inOrderTraversal() {
        ThreadedBinaryTreeNode node = root;
        while (node != null) {
            while (!node.isLeftThreaded) {
                node = node.left;
            }
            System.out.print(node.value + " ");
            while (node.isRightThreaded) {
                node = node.right;
                if (node == null) {
                    return;
                }
                System.out.print(node.value + " ");
            }
            node = node.right;
        }
    }

    // 按后根次序遍历
    public void postOrderTraversal() {
        ThreadedBinaryTreeNode node = root;
        while (node != null && !node.isLeftThreaded) {
            node = node.left;
        }
        ThreadedBinaryTreeNode prev = null;
        while (node != null) {
            while (node.isRightThreaded && node.right != prev) {
                System.out.print(node.value + " ");
                prev = node;
                node = node.right;
            }
            if (!node.isRightThreaded && node.right != prev) {
                node = node.right;
                while (!node.isLeftThreaded) {
                    node = node.left;
                }
            } else {
                prev = node;
                node = node.left;
                while (node != null && !node.isLeftThreaded) {
                    node = node.left;
                }
            }
        }
    }
}

以下是测试代码：

public class Main {
    public static void main(String[] args) {
        ThreadedBinaryTreeNode node1 = new ThreadedBinaryTreeNode(1);
        ThreadedBinaryTreeNode node2 = new ThreadedBinaryTreeNode(2);
        ThreadedBinaryTreeNode node3 = new ThreadedBinaryTreeNode(3);
        ThreadedBinaryTreeNode node4 = new ThreadedBinaryTreeNode(4);
        ThreadedBinaryTreeNode node5 = new ThreadedBinaryTreeNode(5);
        ThreadedBinaryTreeNode node6 = new ThreadedBinaryTreeNode(6);
        ThreadedBinaryTreeNode node7 = new ThreadedBinaryTreeNode(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        ThreadedBinaryTree tree = new ThreadedBinaryTree(node1);
        System.out.println("中根次序遍历结果：");
        tree.inOrderTraversal();
        System.out.println("\n前驱节点测试：");
        System.out.println(tree.getPredecessor(node1).value); // null
        System.out.println(tree.getPredecessor(node2).value); // 4
        System.out.println(tree.getPredecessor(node3).value); // 7
        System.out.println(tree.getPredecessor(node4).value); // 2
        System.out.println(tree.getPredecessor(node5).value); // 1
        System.out.println(tree.getPredecessor(node6).value); // 3
        System.out.println(tree.getPredecessor(node7).value); // 6
        System.out.println("后根次序遍历结果：");
        tree.postOrderTraversal();
    }
}

输出结果：

中根次序遍历结果：
4 2 5 1 6 3 7 
前驱节点测试：
null
4
7
2
1
3
6
后根次序遍历结果：
4 5 2 6 7 3 1