# java-二叉树的遍历-先序、中序、后序（递归和非递归）、层次遍历

```import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class BinTreeTraverse {
//private int[] array={ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
private int[] array={ 10,6,14,4,8,12,16};//BinarySearchTree
private static List<Node> nodeList=null;

public static void main(String[] args) {
BinTreeTraverse tree=new BinTreeTraverse();
tree.createBinTree();

preOrder(nodeList.get(0));
System.out.println();
preOrderStack(nodeList.get(0));
System.out.println();

inOrder(nodeList.get(0));
System.out.println();
inOrderStack(nodeList.get(0));
System.out.println();

postOrder(nodeList.get(0));
System.out.println();
postOrderStack(nodeList.get(0));
System.out.println();

levelOrderStack(nodeList.get(0));
}

public static void visit(Node node){
System.out.print(node.getData()+" ");
}

//create binary tree from array.the data stored in level-order
public void createBinTree(){

for(int i=0,len=array.length;i<len;i++){
}

int len=array.length;
int lastRootIndex=(len>>1)-1;
for(int i=lastRootIndex;i>=0;i--){
Node root=nodeList.get(i);
int leftIndex=i*2+1;
Node leftNode=nodeList.get(leftIndex);
//Node leftNode=new Node(array[leftIndex]);//this is wrong
root.setLeft(leftNode);
//最后的那个根节点一定是有左孩子的。右孩子则不一定
int rightIndex=leftIndex+1;
if(rightIndex<=len-1){
Node rightNode=nodeList.get(rightIndex);
root.setRight(rightNode);
}

}
}

//nonRecursion perOrder Traverse
public static void preOrderStack(Node root){

Stack<Node> stack=new Stack<Node>();
Node p=root;
if(p!=null){
stack.push(p);
while(!stack.isEmpty()){
p=stack.pop();
visit(p);
if(p.getRight()!=null)stack.push(p.getRight());
if(p.getLeft()!=null)stack.push(p.getLeft());
}
}
}
//nonRecursion inOrder Traverse
public static void inOrderStack(Node p){
Stack<Node> stack=new Stack<Node>();
while(p!=null||!stack.isEmpty()){
//push all LeftChild,when p has no LeftChild,that means it's root,it should be visited
while(p!=null){
stack.push(p);
p=p.getLeft();
}
if(!stack.isEmpty()){
p=stack.pop();
visit(p);
p=p.getRight();
}
}
}

//nonRecursion postOrder Traverse
public static void postOrderStack(Node p){
Stack<Node> stack=new Stack<Node>();
Node q=p;//q,is the latest Node that has been visited
while(p!=null){
while(p.getLeft()!=null){
stack.push(p);
p=p.getLeft();
}
/*
while(p!=null){//wrong.when 'while' ends,p=null
stack.push(p);
p=p.getLeft();
}
*/
/*left-right-root
*when a node:
*1.has no right-child -->p.getRight()==null
*2.right-child has been visited -->p.getRight()==q
*it's time to visit this node.
*/
while(p!=null&&(p.getRight()==null||p.getRight()==q)){
visit(p);
q=p;
if(stack.isEmpty())return;
p=stack.pop();
}
stack.push(p);
p=p.getRight();
}
}
//level order
public static void levelOrderStack(Node p){
if(p==null)return;
while(!queue.isEmpty()){
Node temp=queue.remove(0);
System.out.print(temp.data+" ");
if(temp.left!=null){
}
if(temp.right!=null){
}
}
System.out.println();
}

public static void preOrder(Node root){
if(root==null){return;}
System.out.print(root.getData()+" ");
preOrder(root.getLeft());
preOrder(root.getRight());
}
public static void inOrder(Node root){
if(root==null){return;}
inOrder(root.getLeft());
System.out.print(root.getData()+" ");
inOrder(root.getRight());
}
public static void postOrder(Node root){
if(root==null){return;}
postOrder(root.getLeft());
postOrder(root.getRight());
System.out.print(root.getData()+" ");
}

private static class Node{
private Node left;
private Node right;
private int data;
Node(int iData){
data=iData;
left=null;
right=null;
}
public void setLeft(Node leftNode){
this.left=leftNode;
}
public void setRight(Node rightNode){
this.right=rightNode;
}
public Node getLeft(){
return left;
}
public Node getRight(){
return right;
}
public int getData(){
return data;
}

}

}

```

java-二叉树的遍历-先序、中序、后序（递归和非递归）、层次遍历

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊

1、先、中、后递归遍历 其中（1）（2）（3）位置上分别表示先、中、后。 2、先、中、后非递归遍历

#include "stdafx.h" #include <iostream> using namespace std; const int MAXSIZE = 20; //
// 二叉树的遍历.cpp : Defines the entry point for the console application. // #include <ST

PS：输入测试数据时候采用先序遍历的方式用#作为分隔符来输入，例如：此二叉树 用这种方式输入ABC##

#include <iostream> #include <stack> using namespace std; struct Node{ char data;