二叉树的遍历方式有多种，前序遍历，中序遍历，后序遍历，层序遍历，在这里来介绍一下前、中、后序遍历。
- 前序遍历：根左右
- 中序遍历：左根右
- 后序遍历：左右根
二叉树
前序遍历：ABDECF
中序遍历：DBEACF
后序遍历：DEBFCA
介绍一种常见题型：已知任意两种遍历，求出另一种遍历，前提是必须得知道中序遍历。
方法就是通过前序或后序得到根节点，在中序遍历中根据根节点找出左右子树（如上，根据中序遍历，A两侧便是左右子树DBE，CF），之后运用递归的思想，便可以画出一整棵二叉树，再来求第三种遍历就很轻松了。
接下来我们用Java来简单实现一下二叉树的三种遍历方式：
有两种实现方式，分别是：
- 递归实现
- 利用栈的进出实现
public class BinaryTree {
private TreeNode root = null;
public BinaryTree(){
root = new TreeNode(1,"A");
}
/*
* 二叉树
* A
* B C
* D E F
*
* */
// 创建如上所示二叉树
public void createBinaryTree(){
TreeNode nodeB = new TreeNode(2, "B");
TreeNode nodeC = new TreeNode(3, "C");
TreeNode nodeD = new TreeNode(4, "D");
TreeNode nodeE = new TreeNode(5, "E");
TreeNode nodeF = new TreeNode(6, "F");
root.leftnode = nodeB;
root.rightnode = nodeC;
nodeB.leftnode = nodeD;
nodeB.rightnode = nodeE;
nodeC.rightnode = nodeF;
}
// 获取二叉树高度,返回私有的getHeight
public int getHeight(){
return getHeight(root);
}
// 获取二叉树节点数,返回私有的getSize
public int getSize(){
return getSize(root);
}
private int getSize(TreeNode node) {
if(node == null){
return 0;
}else{
return getSize(node.leftnode) + getSize(node.rightnode) + 1;
}
}
private int getHeight(TreeNode node) {
if(node == null){
return 0;
}else{
int j = getHeight(node.leftnode);
int k = getHeight(node.rightnode);
return (j<k)?k+1:j+1;
}
}
// 前序遍历--迭代
public void prevOrder(TreeNode node) {
if(node == null){
return;
}else {
System.out.println(node.getData());
if(node.leftnode != null) prevOrder(node.leftnode);
if(node.rightnode != null) prevOrder(node.rightnode);
}
}
// 中序遍历--迭代
public void midOrder(TreeNode node) {
if(node == null){
return;
}else {
if(node.leftnode != null) midOrder(node.leftnode);
System.out.println(node.getData());
if(node.rightnode != null) midOrder(node.rightnode);
}
}
// 后序遍历--迭代
public void postOrder(TreeNode node) {
if(node == null){
return;
}else {
if(node.leftnode != null) postOrder(node.leftnode);
if(node.rightnode != null) postOrder(node.rightnode);
System.out.println(node.getData());
}
}
// 前序遍历--栈
public void nonprevOrder(TreeNode node){
if(node == null){
return;
}
Stack<TreeNode> st = new Stack<>();
st.push(node);
while(!st.isEmpty()){
TreeNode p = st.pop();
System.out.println(p.getData());
if(p.rightnode != null) st.push(p.rightnode);
if(p.leftnode != null) st.push(p.leftnode);
}
}
// 中序遍历--栈
public void nonmidOrder(TreeNode node){
if(node == null){
return;
}
Stack<TreeNode> st = new Stack<>();
TreeNode n = node;
while(!st.isEmpty() || n != null){
if(n != null){
st.push(n);
n = n.leftnode;
}else{
n = st.pop();
System.out.println(n.getData());
n = n.rightnode;
}
}
}
// 后序遍历--栈
public void nonpostOrder(TreeNode node){
if (node == null){
return;
}
Stack<TreeNode> st = new Stack<>();
// 创建另一个栈，来存储从st栈中抛出的元素
Stack<TreeNode> output = new Stack<>();
TreeNode n = node;
while (!st.isEmpty() || n != null){
if (n != null){
output.push(n);
st.push(n);
n = n.rightnode;
}else {
n = st.pop();
n = n.leftnode;
}
}
while (output.size() >0){
System.out.println(output.pop().getData());
}
}
// 内部类，二叉树的节点
public class TreeNode<T>{
private int index;
private T data;
private TreeNode<T> leftnode;
private TreeNode<T> rightnode;
// 构造函数，一个节点出生不知道其儿子节点，所以为null
public TreeNode(int index, T data){
this.index = index;
this.data = data;
this.leftnode = null;
this.rightnode = null;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
}
public static void main (String[] args){
BinaryTree bt = new BinaryTree();
bt.createBinaryTree();
System.out.println("高度：" + bt.getHeight());
System.out.println("节点个数：" + bt.getSize());
System.out.println("--前序--");
bt.prevOrder(bt.root);
System.out.println("--中序--");
bt.midOrder(bt.root);
System.out.println("--后序--");
bt.postOrder(bt.root);
System.out.println("--前序--");
bt.nonprevOrder(bt.root);
System.out.println("--中序--");
bt.nonmidOrder(bt.root);
System.out.println("--后序--");
bt.nonpostOrder(bt.root);
}
}
