二叉树的三种遍历（java实现）
前言
nowcoder题目：https://www.nowcoder.com/practice/566f7f9d68c24691aa5abd8abefa798c?tpId=101&rp=1&ru=%2Fta%2Fprogrammer-code-interview-guide&qru=%2Fta%2Fprogrammer-code-interview-guide%2Fquestion-ranking
常规递归和非递归方法
import java.io.*;import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
br.readLine();
TreeNode root = buildTree(br);
// 前序遍历
//preOrderTraversalRecur(root);
preOrderTraversal(root);
System.out.println("");
// 中序遍历
//inOrderTraversalRecur(root);
inOrderTraversal(root);
System.out.println("");
// 后序遍历
//postOrderTraversalRecur(root);
postOrderTraversal2(root);
System.out.println("");
br.close();
}
// 递归解法
private static void preOrderTraversalRecur(TreeNode root) {
if (null == root) {
return;
}
System.out.print(root.val + " ");
preOrderTraversalRecur(root.left);
preOrderTraversalRecur(root.right);
}
// 非递归前序遍历解法， 根左右
private static void preOrderTraversal(TreeNode root) {
if (null == root) {
return ;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root, last = root; // 记录上次遍历的 节点
stack.push(cur);
while (!stack.isEmpty()) {
cur = stack.pop();
System.out.print(cur.val + " ");
if (null != cur.right) {
stack.push(cur.right);
}
if (null != cur.left) {
stack.push(cur.left);
}
}
return;
}
private static void inOrderTraversalRecur(TreeNode root) {
if (null == root) {
return;
}
preOrderTraversalRecur(root.left);
System.out.print(root.val + " ");
preOrderTraversalRecur(root.right);
}
// 非递归中序遍历解法, 用栈实现， 左根右
private static void inOrderTraversal(TreeNode root) {
if (null == root) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (!stack.isEmpty() || null != cur) {
while (null != cur) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
System.out.print(cur.val + " ");
cur = cur.right;
}
return ;
}
private static void postOrderTraversalRecur(TreeNode root) {
if (null == root) {
return;
}
preOrderTraversalRecur(root.left);
preOrderTraversalRecur(root.right);
System.out.print(root.val + " ");
}
// 非递归后序遍历解法，左右根，参考左的书籍
// 用一个栈实现的版本
private static void postOrderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root, last = root; // last记录上次遍历并弹出的节点
stack.push(cur);
while (!stack.isEmpty()) {
cur = stack.peek();
// 左子树为空，且不等于访问过的节点
if (null != cur.left && last != cur.left && last != cur.right) {
stack.push(cur.left);
} else if (null != cur.right && last != cur.right) {
stack.push(cur.right);
} else {
System.out.print(stack.pop().val + " ");
last = cur;
}
}
return;
}
private static void postOrderTraversal2(TreeNode root) {
if (null == root) {
return;
}
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
TreeNode cur = root;
s1.push(cur);
while (!s1.isEmpty()) {
cur = s1.pop();
s2.push(cur);
if (null != cur.left) {
s1.push(cur.left);
}
if (null != cur.right) {
s1.push(cur.right);
}
}
while (!s2.isEmpty()) {
System.out.print(s2.pop().val + " ");
}
return;
}
// 递归构建二叉树
private static TreeNode buildTree(BufferedReader br) throws IOException {
String[] rawInput = br.readLine().trim().split(" ");
TreeNode root = new TreeNode(Integer.parseInt(rawInput[0]));
int iLeft = Integer.parseInt(rawInput[1]);
int iRight = Integer.parseInt(rawInput[2]);
if (0 != iLeft) {
root.left = buildTree(br);
}
if (0 != iRight) {
root.right = buildTree(br);
}
return root;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int value) {
this.val = value;
}
public TreeNode(int value, TreeNode left, TreeNode right) {
this.val = value;
this.left = left;
this.right = right;
}
}
Morris遍历
import java.io.*;import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
br.readLine();
TreeNode root = createTreeNode(br);
preOrderMorris(root);
inOrderMorris(root);
postOrderMorris(root);
br.close();
}
/**
* Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 xx）：
* 如果 xx 无左孩子，则访问 xx 的右孩子，即 x = x.right。
* 如果 xx 有左孩子，则找到 xx 左子树上最右的节点（即左子树中序遍历的最后一个节点，xx 在中序遍历中的前驱节点），我们记为predecessor。根据predecessor 的右孩子是否为空，进行如下操作。
* 如果 predecessor 的右孩子为空，则将其右孩子指向 xx，然后访问 xx 的左孩子，即 x = x.left。
* 如果 predecessor 的右孩子不为空，则此时其右孩子指向 xx，说明我们已经遍历完 xx 的左子树，我们将predecessor 的右孩子置空，
然后访问 xx 的右孩子，即 x = x.right。
* 作者：LeetCode-Solution
* 链接：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/
* 来源：力扣（LeetCode）
* 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
**/
// 先序遍历 Morris遍历 莫里斯遍历
private static void preOrderMorris(TreeNode root) {
if (null == root) {
return;
}
TreeNode cur = root, predecessor = null;
while (null != cur) {
predecessor = cur.left;
if (null != predecessor) {
while (null != predecessor.right && cur != predecessor.right) {
predecessor = predecessor.right;
}
if (null == predecessor.right) {
predecessor.right = cur;
System.out.print(cur.val + " ");
cur = cur.left;
continue;
} else {
predecessor.right = null;
}
} else {
System.out.print(cur.val + " ");
}
cur = cur.right;
}
System.out.println();
}
// 中序遍历 morris遍历, 复用空指针指向上层某个节点
// 这里为左子树最右结点指向根结点
private static void inOrderMorris(TreeNode root) {
if (null == root) {
return;
}
TreeNode cur = root, predecessor = null;
while (null != cur) {
predecessor = cur.left;
if (null != predecessor) {
// 获取左子树上的最右结点
while (null != predecessor.right && cur != predecessor.right) {
predecessor = predecessor.right;
}
if (null == predecessor.right) {
// 左子树上的最右结点 指向当前结点
predecessor.right = cur;
cur = cur.left;
continue; // 注意这里的continue;
} else {
// 复原空指针
predecessor.right = null;
}
}
System.out.print(cur.val + " ");
cur = cur.right;
}
System.out.println();
return;
}
// 后序遍历 morris遍历
private static void postOrderMorris(TreeNode root) {
if (null == root) {
return;
}
TreeNode cur = root, prodecessor = null;
while (null != cur) {
prodecessor = cur.left;
if (null != prodecessor) {
while (null != prodecessor.right && cur != prodecessor.right) {
prodecessor = prodecessor.right;
}
if (null == prodecessor.right) {
prodecessor.right = cur;
cur = cur.left;
continue; // 这里的continue;
} else {
prodecessor.right = null;
printEdge(cur.left);
}
}
cur = cur.right;
}
printEdge(root);
System.out.println();
}
private static void printEdge(TreeNode root) {
// 逆序右边界
TreeNode tail = reverseEdge(root);
TreeNode cur = tail;
while (null != cur) {
System.out.print(cur.val + " ");
cur = cur.right;
}
reverseEdge(tail);
}
private static TreeNode reverseEdge(TreeNode from) {
TreeNode next = null, pre = null;
while (null != from) {
next = from.right;
from.right = pre;
pre = from;
from = next;
}
return pre;
}
private static TreeNode createTreeNode(BufferedReader br) throws IOException {
String[] rawInput = br.readLine().trim().split(" ");
int rootVal = Integer.parseInt(rawInput[0]);
int leftVal = Integer.parseInt(rawInput[1]);
int rightVal = Integer.parseInt(rawInput[2]);
TreeNode root = new TreeNode(rootVal);
if (0 != leftVal) {
root.left = createTreeNode(br);
}
if (0 != rightVal) {
root.right = createTreeNode(br);
}
return root;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
以上是 二叉树的三种遍历（java实现） 的全部内容， 来源链接： utcz.com/z/393844.html
