在【Java】 大话数据结构(9) 树(二叉树、线索二叉树)一文中，已经实现了采用递归方法的前、中、后序遍历，本文补充了采用循环的实现方法、以及层序遍历并进行了一个总结。
递归实现
/*
* 前序遍历
*/
void () {
(root);
.out.();
}
void ( node) {
if(node==null)
;
.out.print(node.data);
(node.);
(node.);
}
/*
* 中序遍历
*/
void () {
(root);
.out.();
}
void ( node) {
if(node==null)
;
(node.);
.out.print(node.data);
(node.);
}
/*
* 后序遍历
*/
void () {
(root);
.out.();
}
void ( node) {
if(node==null)
;
(node.);
(node.);
.out.print(node.data);
}
非递归实现(迭代)
非递归实现，需要先创建一个栈，利用其特性来进行储存和输出。
前序遍历，先输出当前点的值遍历二叉树java算法，一直沿着左子树进行读取，没左子树就在右子树重复上述过程。
中序遍历与前序遍历基本一致，只是输出值的代码位置不同。
后序遍历由于要左右子树输出完后才能输出根结点，所以增加一个栈进行标记是否完成左右子树的输出，其余思想基本类似。
下面代码中，要注意node的结点位置和stack.peek()的位置关系。
此外，在后序非递归遍历的过程中遍历二叉树java算法 java循环树_【Java】 二叉树的遍历（递归与循环+层序遍历），栈中保留的是当前结点的所有祖先。这是和先序及中序遍历不同的。在某些和祖先有关的算法中，此算法很有价值。
/**
* 前序遍历(非递归)
*/
void () {
(root);
.out.();
}
void ( node) {
Stack stack = new Stack();
while(node!=null||!stack.()) {
while(node!=null) {
.out.print(node.data);
stack.push(node);
node=node.;
}
node=stack.pop().;
}
}
/**
* 中序遍历
*/
void () {
(root);
.out.();
}
void ( node) {
Stack stack = new Stack();
while(node!=null||!stack.()) {
while(node!=null) {
stack.push(node);
node=node.;
}
node=stack.pop();
.out.print(node.data);
node=node.;
}
}
/**
* 后序遍历
*/
void () {
(root);
.out.();
}
void ( node) {
Stack stack = new Stack();
Stack tag = new Stack();
//下面这段注释也能实现，与后面未注释部分基本一致。代表了自己的思考过程，就不删除了
//while(node!=null||!stack.()) {
//while(node!=null){
//stack.push(node);
//tag.push(0);
//node=node.;
//}
//注释中的tag用于标记当前结点是否完成左右子结点遍历(所以用0，1表示)
//while(!tag.()&&tag.peek()==1) { //栈顶节点的左右子结点已完成遍历
//.out.print(stack.pop().data);
//tag.pop();
//}
//if(!tag.()) { //上面和这里的 !flag.() 不可省略，不然会出错。
//tag.pop();
//tag.push(1);
//node=stack.peek().;
//}
//}
/*后序遍历时，分别从左子树和右子树共两次返回根结点(用tag表示次数)，
* 只有从右子树返回时才访问根结点，所以增加一个栈标记到达结点的次序。
*/
while(node!=null||!stack.()) {
if(node!=null){
stack.push(node);
tag.push(1); //第一次访问
node=node.;
}else {
if(tag.peek()==2) {
.out.print(stack.pop().data);
tag.pop();
}else {
tag.pop();
tag.push(2); //第二次访问
node=stack.peek().;
}
}
}
}
：前序和后序的非递归遍历还可以合理利用栈的性质来实现，与上面的稍有不同。
前序：
List ( root) {
list = new ();
Stack stk = new Stack();
stk.push(root);
while(!stk.()){
node = stk.pop();
if(node==null)
;
list.add(node.val);
stk.push(node.right);
stk.push(node.left);
}
list;
}
后序：
List ( root) {
list = new ();
Stack stk = new Stack();
stk.push(root);
while(!stk.()){
node = stk.pop();
if(node==null)
;
list.(node.val); //'s . If using here,then using '.(list)'' in the end;
stk.push(node.left);
stk.push(node.right);
}
list;
}
层序遍历
合理利用队列的性质即可。
void () {
node =root;
> list = new ();
list.add(node);
while(!list.()) {
node=list.poll();
.out.print(node.data);
if(node.!=null)
list.offer(node.);
if(node.!=null)
list.offer(node.);
}
}
完整代码(含测试代码)
;
java.util.;
java.util.Stack;
class {
E data;
,;
(E data) {
this.data=data;
this.=null;
this.=null;
}
}
class {
root;
() {
//root=new (null, null, null);
root=null;
}
/*
* 前序遍历
*/
void () {
(root);
.out.();
}
void ( node) {
if(node==null)
;
.out.print(node.data);
(node.);
(node.);
}
/*
* 中序遍历
*/
void () {
(root);
.out.();
}
void ( node) {
if(node==null)
;
(node.);
.out.print(node.data);
(node.);
}
/*
* 后序遍历
*/
void () {
(root);
.out.();
}
void ( node) {
if(node==null)
;
(node.);
(node.);
.out.print(node.data);
}
//===============循环遍历===============
/**
* 前序遍历(非递归)
*/
void () {
(root);
.out.();
}
void ( node) {
Stack stack = new Stack();
while(node!=null||!stack.()) {
while(node!=null) {
.out.print(node.data);
stack.push(node);
node=node.;
}
node=stack.pop().;
}
}
/**
* 中序遍历
*/
void () {
(root);
.out.();
}
void ( node) {
Stack stack = new Stack();
while(node!=null||!stack.()) {
while(node!=null) {
stack.push(node);
node=node.;
}
node=stack.pop();
.out.print(node.data);
node=node.;
}
}
/**
* 后序遍历
*/
void () {
(root);
.out.();
}
void ( node) {
Stack stack = new Stack();
Stack tag = new Stack();
//while(node!=null||!stack.()) {
//while(node!=null){
//stack.push(node);
//tag.push(0);
//node=node.;
//}
//这里的tag用于标记当前结点是否完成左右子结点遍历(所以用0，1表示)
//while(!tag.()&&tag.peek()==1) { //栈顶节点的左右子结点已完成遍历
//.out.print(stack.pop().data);
//tag.pop();
//}
//if(!tag.()) { //上面和这里的 !flag.() 不可省略，不然会出错。
//tag.pop();
//tag.push(1);
//node=stack.peek().;
//}
//}
/*后序遍历时遍历二叉树java算法，分别从左子树和右子树共两次返回根结点(用tag表示次数)，
* 只有从右子树返回时才访问根结点，所以增加一个栈标记到达结点的次序。
*/
while(node!=null||!stack.()) {
if(node!=null){
stack.push(node);
tag.push(1); //第一次访问
node=node.;
}else {
if(tag.peek()==2) {
.out.print(stack.pop().data);
tag.pop();
}else {
tag.pop();
tag.push(2); //第二次访问
node=stack.peek().;
}
}
}
}
//=========层序遍历============
void () {
node =root;
> list = new ();
list.add(node);
while(!list.()) {
node=list.poll();
.out.print(node.data);
if(node.!=null)
list.offer(node.);
if(node.!=null)
list.offer(node.);
}
}
void main([] args) {
= new ();
.root=new ("A");
.root.=new ("B");
.root.=new ("C");
.root..=new ("D");
// = new ();
//.root=new ("A");
//.root.=new ("B");
//.root..=new ("C");
//.root...=new ("D");
//.root..=new ("E");
//.root...=new ("F");
//.root....=new ("G");
//.root.....=new ("H");
.out.("————前序————");
.();
.();
.out.("————中序————");
.();
.();
.out.("————后序————");
.();
.();
.out.("————层序遍历————");
.();
}
}
————前序————
ABDC
ABDC
————中序————
BDAC
BDAC
————后序————
DBCA
DBCA
————层序遍历————
ABCD
遍历结果
文章来源:https://blog.csdn.net/weixin_29444613/article/details/114086135