树的非递归代码（Java实现）
建树：
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
public class TreeBuilder {
/**
* 从文件读取数据按层次遍历的方式创建一个二叉树 (测试用)
* 文件输入只能是'#'或数字，'#'表示null
* 测试用例1： 1 2 3 4 5 # # 6 # 7 9
* 测试用例2： 1 2 3 4 5
*
* @return
*/
public TreeNode<Integer> createTree(Scanner in) {
String val = in.next();
if (val.equals("#")) {
return null;
}
TreeNode<Integer> node = new TreeNode<>(Integer.valueOf(val));
TreeNode<Integer> root = node;
Queue<TreeNode<Integer>> queue = new ArrayDeque<>();
queue.add(node);
while (!queue.isEmpty()) {
int len = queue.size();
for (int i = 0; i < len; i++) {
node = queue.remove();
if (!in.hasNext()) {
break;
}
val = in.next();
if (val.equals("#")) {
node.left = null;
} else {
node.left = new TreeNode<>(Integer.valueOf(val));
queue.add(node.left);
}
if (!in.hasNext()) {
break;
}
val = in.next();
if (val.equals("#")) {
node.right = null;
} else {
node.right = new TreeNode<>(Integer.valueOf(val));
queue.add(node.right);
}
}
}
return root;
}
}
树节点定义：
public class TreeNode<T> {
TreeNode(T val) {
this.val = val;
}
T val;
TreeNode<T> left;
TreeNode<T> right;
}
层次遍历、前中后遍历的代码：
import java.util.*;
public class TreeIter<T> {
/**
* 层次遍历，用队列实现
*
* @param root
* @return
*/
public List<T> levelOrder(TreeNode<T> root) {
List<T> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode<T>> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode<T> node = queue.remove();
res.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return res;
}
/**
* 前序遍历非递归
*
* @param root
* @return
*/
public List<T> preOrder(TreeNode<T> root) {
List<T> res = new ArrayList<>();
if (root == null) {
return res;
}
TreeNode<T> curNode = root;
Stack<TreeNode<T>> stack = new Stack<>();
while (curNode != null || !stack.isEmpty()) {
while (curNode != null) {
stack.add(curNode);
res.add(curNode.val);
curNode = curNode.left;
}
curNode = stack.pop();
curNode = curNode.right;
}
return res;
}
/**
* 中序遍历非递归
*
* @param root
* @return
*/
public List<T> midOrder(TreeNode<T> root) {
List<T> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode<T>> stack = new Stack<>();
TreeNode<T> curNode = root;
while (curNode != null || !stack.isEmpty()) {
while (curNode != null) {
stack.push(curNode);
curNode = curNode.left;
}
curNode = stack.pop();
res.add(curNode.val);
curNode = curNode.right;
}
return res;
}
/**
* 后序遍历非递归(双栈法，好理解)
*
* @param root
* @return
*/
public List<T> postOrder(TreeNode<T> root) {
List<T> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode<T>> stackRes = new Stack<>();
Stack<TreeNode<T>> stackTmp = new Stack<>();
stackTmp.push(root);
TreeNode<T> curNode;
while (!stackTmp.isEmpty()) {
curNode = stackTmp.pop();
stackRes.push(curNode);
if (curNode.left != null) {
stackTmp.add(curNode.left);
}
if (curNode.right != null) {
stackTmp.add(curNode.right);
}
}
while (!stackRes.isEmpty()) {
res.add(stackRes.pop().val);
}
return res;
}
/**
* 后序遍历非递归
* <p>
* 参考链接，注释非常详细
* http://www.cnblogs.com/ybwang/archive/2011/10/04/lastOrderTraverse.html
*
* @param root
* @return
*/
public List<T> postOrder2(TreeNode<T> root) {
List<T> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode<T>> stack = new Stack<>();
stack.push(root);
TreeNode<T> curNode = null;
TreeNode<T> preNode = null;
while (!stack.isEmpty()) {
curNode = stack.peek();
if (preNode == null || preNode.left == curNode || preNode.right == curNode) {
if (curNode.left != null) {
stack.push(curNode.left);
} else if (curNode.right != null) {
stack.push(curNode.right);
} else {
res.add(stack.pop().val);
}
} else if (curNode.left == preNode) {
if (curNode.right != null) {
stack.push(curNode.right);
} else {
res.add(stack.pop().val);
}
} else if (curNode.right == preNode) {
res.add(stack.pop().val);
}
preNode = curNode;
}
return res;
}
}
测试用例：
input.txt
1 2 3 4 5 # # 6 # 7 9
测试代码：
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws FileNotFoundException {
TreeIter<Integer> treeIter = new TreeIter<>();
Scanner in = new Scanner(new FileInputStream("input.txt"));
TreeNode<Integer> root = new TreeBuilder().createTree(in);
List<Integer> preOrder = treeIter.preOrder(root);
System.out.println(preOrder);
List<Integer> midOrder = treeIter.midOrder(root);
System.out.println(midOrder);
List<Integer> postOrder = treeIter.postOrder(root);
System.out.println(postOrder);
List<Integer> postOrder2 = treeIter.postOrder2(root);
System.out.println(postOrder2);
List<Integer> levelOrder = treeIter.levelOrder(root);
System.out.println(levelOrder);
}
}
网友评论