package wsj;
/**
* 当前类所有函数
* -------------
* [递归方式][前序]遍历二叉树:preOrderRecur()
* [递归方式][中序]遍历二叉树:inOrderRecur()
* [递归方式][后序]遍历二叉树:posOrderRecur()
* [非递归方式][前序]遍历二叉树:preOrderUnRecur()
* [非递归方式][中序]遍历二叉树:inOrderUnRecur()
* [非递归方式][后序]遍历二叉树:posOrderUnRecur()
* [按层]遍历二叉树:printByLevel()
* 由[前序遍历序列]和[中序遍历序列]重建二叉树:buildTreeByPreAndIn()
* 由[后序遍历序列]和[中序遍历序列]重建二叉树:buildTreeByPosAndIn()
*/
import java.util.LinkedList;
import java.util.Stack;
//定义二叉树节点
class TreeNode {
public int value;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
this.value = x;
}
}
public class MyTree {
// [递归方式][前序]遍历二叉树
public static void preOrderRecur(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.value + "-");
preOrderRecur(root.left);
preOrderRecur(root.right);
}
// [递归方式][中序]遍历二叉树
public static void inOrderRecur(TreeNode root) {
if (root == null) {
return;
}
inOrderRecur(root.left);
System.out.print(root.value + "-");
inOrderRecur(root.right);
}
// [递归方式][后序]遍历二叉树
public static void posOrderRecur(TreeNode root) {
if (root == null) {
return;
}
posOrderRecur(root.left);
posOrderRecur(root.right);
System.out.print(root.value + "-");
}
// [非递归方式][前序]遍历二叉树
public static void preOrderUnRecur(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
System.out.print(cur.value + "-");
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
}
// [非递归方式][中序]遍历二叉树
public static void inOrderUnRecur(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
System.out.print(node.value + "-");
cur = node.right;
}
}
// [非递归方式][后序]遍历二叉树
public static void posOrderUnRecur(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
TreeNode cur = root;
stack1.push(cur);
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
stack2.push(node);
if (node.left != null) {
stack1.push(node.left);
}
if (node.right != null) {
stack1.push(node.right);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().value + "-");
}
}
// [按层]遍历二叉树
public static void printByLevel(TreeNode root){
if (root==null) {
return;
}
LinkedList<TreeNode> queue=new LinkedList<>();
queue.addLast(root);
while (!queue.isEmpty()) {
TreeNode node=queue.pollFirst();
System.out.print(node.value+"-");
if (node.left!=null) {
queue.addLast(node.left);
}
if (node.right!=null) {
queue.addLast(node.right);
}
}
}
// 由[前序遍历序列]和[中序遍历序列]重建二叉树
public static TreeNode buildTreeByPreAndIn(int[] pre, int[] in) {
return buildProcess1(pre, 0, pre.length - 1, in, 0, in.length - 1);
}
private static TreeNode buildProcess1(int[] pre, int preStart, int preEnd,
int[] in, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(pre[preStart]);
int i = inStart;
while (in[i] != pre[preStart]) {
i++;
}
root.left = buildProcess1(pre, preStart + 1, preStart + i - inStart,
in, inStart, i - 1);
root.right = buildProcess1(pre, preStart + i - inStart + 1, preEnd, in,
i + 1, inEnd);
return root;
}
// 由[后序遍历序列]和[中序遍历序列]重建二叉树
public static TreeNode buildTreeByPosAndIn(int[] pos, int[] in) {
return buildProcess2(pos, 0, pos.length - 1, in, 0, in.length - 1);
}
private static TreeNode buildProcess2(int[] pos, int posStart, int posEnd,
int[] in, int inStart, int inEnd) {
if (posStart > posEnd || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(pos[posEnd]);
int i = inStart;
while (in[i] != pos[posEnd]) {
i++;
}
root.left = buildProcess2(pos, posStart, posStart + i - inStart - 1,
in, inStart, i - 1);
root.right = buildProcess2(pos, posStart + i - inStart, posEnd - 1, in,
i + 1, inEnd);
return root;
}
public static void main(String[] args) {
int[] pre = { 1, 2, 4, 7, 3, 5, 6, 8 };
int[] in = { 4, 7, 2, 1, 5, 3, 8, 6 };
int[] pos = { 7, 4, 2, 5, 8, 6, 3, 1, };
// TreeNode root = buildTreeByPreAndIn(pre, in);
TreeNode root = buildTreeByPosAndIn(pos, in);
preOrderRecur(root);
System.out.println();
preOrderUnRecur(root);
System.out.println();
inOrderRecur(root);
System.out.println();
inOrderUnRecur(root);
System.out.println();
posOrderRecur(root);
System.out.println();
posOrderUnRecur(root);
System.out.println();
printByLevel(root);
}
}
网友评论