二叉树的先序遍历、中序遍历、后序遍历、层次遍历
介绍二叉树的4中遍历方式
java用递归和非递归方式实现前序中序后序遍历
二叉树的遍历方式，
1. 先序遍历 Pre-order
前序遍历：
若二叉树为空，则空操作返回，
否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
特点：1. 根----->左----->右 2. 根据前序遍历的结果可知第一个访问的必定是root结点。
2. 中序遍历 Inorder Traversal(LDR)
中序遍历：
若二叉树为空，则空操作返回，
否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。
特点：1. 左----->根------->右 2. 根据中序遍历的结果，再结合前序遍历的root结点去划分root结点的左右子树。
3. 后序遍历 Postorder Traversal(LRD)
后序遍历：
若二叉树为空，则空操作返回，
否则从左到右先叶子结点后结点的方式遍历访问左右子树，最后访问根结点。
特点：1. 左------>右------>根 2. 根据后序遍历的结果可知最后访问的必定是root结点。
4. 层序遍历
层序遍历：
若二叉树为空，则空返回，
否则从树的第一层，即根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
特点：1. 从左到右，从上到下 2. 可知第一个访问的必定是root结点
java递归非递归 实现前序中序后序遍历二叉树
package cn.altman.common.test;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* Created by xuzhihua on 1/5/2018.
*/
class TreeNode<T> {
private T value;
private TreeNode<T> left;
private TreeNode<T> right;
public T getValue() {return value;}
public void setValue(T value) {this.value = value;}
public TreeNode<T> getLeft() {return left;}
public void setLeft(TreeNode<T> left) {this.left = left;}
public TreeNode<T> getRight() {return right;}
public void setRight(TreeNode<T> right) {this.right = right;}
}
// 前序遍历 Preorder Traversal (DLR)
class PreOrder<T> {
// 递归
public List<T> travelWithRecursion(TreeNode<T> tree) {
List<T> result = new ArrayList<T>();
doTravelRecursion(tree, result);
return result;
}
private void doTravelRecursion(TreeNode<T> tree, List<T> result) {
if (tree == null)
return;
result.add(tree.getValue());
if (tree.getLeft() != null)
doTravelRecursion(tree.getLeft(), result);
if (tree.getRight() != null)
doTravelRecursion(tree.getRight(), result);
}
// 非递归
public List<T> travelWithoutRecursion(TreeNode<T> tree) {
List<T> result = new ArrayList<T>();
Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
stack.push(tree);
while (!stack.empty()) {
TreeNode<T> node = stack.pop();
result.add(node.getValue());
if (node.getRight() != null) {
stack.push(node.getRight());
}
if (node.getLeft() != null) {
stack.push(node.getLeft());
}
}
return result;
}
}
// 中序遍历 Inorder Traversal (LDR)
class InOrder<T> {
// 递归
public List<T> travelWithRecursion(TreeNode<T> tree) {
List<T> result = new ArrayList<T>();
doTravelRecursion(tree, result);
return result;
}
private void doTravelRecursion(TreeNode<T> tree, List<T> result) {
if (tree == null)
return;
if (tree.getLeft() != null)
doTravelRecursion(tree.getLeft(), result);
result.add(tree.getValue());
if (tree.getRight() != null)
doTravelRecursion(tree.getRight(), result);
}
// 非递归
public List<T> travelWithoutRecursion(TreeNode<T> tree) {
List<T> result = new ArrayList<T>();
Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
TreeNode<T> node = tree;
while (!stack.empty() || node != null) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (!stack.empty()) {
node = stack.pop();
result.add(node.getValue());
node = node.getRight();
}
}
return result;
}
}
// 后序遍历 Postorder Traversal (LRD)
class PostOrder<T> {
// 递归
public List<T> travelWithRecursion(TreeNode<T> tree) {
List<T> result = new ArrayList<T>();
doTravelRecursion(tree, result);
return result;
}
private void doTravelRecursion(TreeNode<T> tree, List<T> result) {
if (tree == null)
return;
if (tree.getLeft() != null)
doTravelRecursion(tree.getLeft(), result);
if (tree.getRight() != null)
doTravelRecursion(tree.getRight(), result);
result.add(tree.getValue());
}
// 非递归
public List<T> travelWithoutRecursion(TreeNode<T> tree) {
List<T> result = new ArrayList<T>();
Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
TreeNode<T> currentNode = tree;
TreeNode<T> lastNode = null;
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.getLeft();
}
while (!stack.empty()) {
currentNode = stack.pop();
//只有“当前节点”没有右孩子或者右孩子已经被访问过了，才可以访问“当前节点”
if (currentNode.getRight() == null || currentNode.getRight() == lastNode) {
result.add(currentNode.getValue());
lastNode = currentNode;
}
else {
stack.push(currentNode);
currentNode = currentNode.getRight();
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.getLeft();
}
}
}
return result;
}
}
public class TraversalOfBinaryTreeDemo {
public static void main(String[] args) {
// 初始化 二叉树 数据
TreeNode<String> root = prepareData();
PreOrder<String> preOrder = new PreOrder<String>();
InOrder<String> inOrder = new InOrder<String>();
PostOrder<String> postOrder = new PostOrder<String>();
System.out.println("先序遍历 非递归\t\t" + String.join(", ", preOrder.travelWithoutRecursion(root)));
System.out.println("先序遍历 递归\t\t" + String.join(", ", preOrder.travelWithRecursion(root)));
System.out.println();
System.out.println("中序遍历 非递归\t\t" + String.join(", ", inOrder.travelWithoutRecursion(root)));
System.out.println("中序遍历 递归\t\t" + String.join(", ", inOrder.travelWithRecursion(root)));
System.out.println();
System.out.println("后序遍历 非递归\t\t" + String.join(", ", postOrder.travelWithoutRecursion(root)));
System.out.println("后序遍历 递归\t\t" + String.join(", ", postOrder.travelWithRecursion(root)));
System.out.println();
}
/**
* 1
* 2 3
* 4 5 6 7
* 8 9
* 初始化节点数据
*/
private static TreeNode<String> prepareData() {
TreeNode<String> root = new TreeNode<String>();
root.setValue("1");
TreeNode<String> node1 = new TreeNode<String>();
node1.setValue("2");
root.setLeft(node1);
TreeNode<String> node1_1 = new TreeNode<String>();
node1_1.setValue("4");
node1.setLeft(node1_1);
TreeNode<String> node1_2 = new TreeNode<String>();
node1_2.setValue("5");
node1.setRight(node1_2);
TreeNode<String> node8 = new TreeNode<String>();
node8.setValue("8");
node1_1.setLeft(node8);
TreeNode<String> node9 = new TreeNode<String>();
node9.setValue("9");
node1_1.setRight(node9);
TreeNode<String> node2 = new TreeNode<String>();
node2.setValue("3");
root.setRight(node2);
TreeNode<String> node2_1 = new TreeNode<String>();
node2_1.setValue("6");
node2.setLeft(node2_1);
TreeNode<String> node2_2 = new TreeNode<String>();
node2_2.setValue("7");
node2.setRight(node2_2);
return root;
}
}
/**
*输出结果
先序遍历 非递归 1, 2, 4, 8, 9, 5, 3, 6, 7
先序遍历 递归 1, 2, 4, 8, 9, 5, 3, 6, 7
中序遍历 非递归 8, 4, 9, 2, 5, 1, 6, 3, 7
中序遍历 递归 8, 4, 9, 2, 5, 1, 6, 3, 7
后序遍历 非递归 8, 9, 4, 5, 2, 6, 7, 3, 1
后序遍历 递归 8, 9, 4, 5, 2, 6, 7, 3, 1
*/