遍历二叉树和线索二叉树的方法

遍历二叉树的方法有三种：先序遍历、中序遍历和后序遍历。其中，先序遍历是指先遍历根节点，再遍历左子树和右子树；中序遍历是指先遍历左子树，再遍历根节点和右子树；后序遍历是指先遍历左子树和右子树，再遍历根节点。

线索二叉树是在二叉树的基础上，通过添加线索（即前驱和后继指针）来实现遍历的优化。线索二叉树的遍历方法有两种：中序遍历和后序遍历。其中，中序遍历是指按照节点的中序遍历顺序遍历线索二叉树；后序遍历是指按照节点的后序遍历顺序遍历线索二叉树。

举例说明：

//先序遍历二叉树
public void preOrder(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

//中序遍历二叉树
public void inOrder(TreeNode root) {
    if (root != null) {
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}

//后序遍历二叉树
public void postOrder(TreeNode root) {
    if (root != null) {
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
}

//中序遍历线索二叉树
public void inOrderThreaded(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        while (cur.left != null && !cur.left.isThreaded) {
            cur = cur.left;
        }
        System.out.print(cur.val + " ");
        if (cur.right != null && cur.isThreaded) {
            cur = cur.right;
        } else {
            cur = cur.right;
            while (cur != null && !cur.isThreaded) {
                cur = cur.left;
            }
        }
    }
}

//后序遍历线索二叉树
public void postOrderThreaded(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        while (cur.left != null && !cur.left.isThreaded) {
            cur = cur.left;
        }
        while (cur.right != null && cur.isThreaded) {
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
        System.out.print(cur.val + " ");
        cur = cur.right;
    }
}