java二叉树的非递归遍历
二叉树的递归遍历比较简单，这里就不聊了。今天主要聊聊二叉树的非递归遍历，主要借助于“栈”后进先出的特性来保存节点的顺序，先序遍历和中序遍历相对来说比较简单，重点理解后序遍历。
1.先看看节点类型：
//二叉树的节点类型
privateclassNode{
intdata;//节点值
NodeleftChild;//左孩子
NoderightChild;//右孩子
publicNode(intdata){
this.data=data;
}
}
2.先序遍历。
非递归先序遍历的思路如下：
1.先将根节点入栈
2.访问根节点
3.如果根节点存在右孩子，则将右孩子入栈
4.如果根节点存在左孩子，则将左孩子入栈（注意：一定是右孩子先入栈，然后左孩子入栈）
5.重复2-4
publicvoidpreOrder(NodeRoot){
if(Root==null){
System.out.println("空树");
return;
}
Nodetmp=Root;
Stacks=newStack();
s.push(tmp);//根节点入栈
while(!s.empty()){
//1.访问根节点
Nodep=s.pop();
System.out.print(p.data+"");
//2.如果根节点存在右孩子，则将右孩子入栈
if(p.rightChild!=null){
s.push(p.rightChild);
}
//3.如果根节点存在左孩子，则将左孩子入栈
if(p.leftChild!=null){
s.push(p.leftChild);
}
}
System.out.println();
}
3.中序遍历。
非递归中序遍历的思路如下：
1.先将根节点入栈
2.将当前节点的所有左孩子入栈，直到左孩子为空
3.访问栈顶元素，如果栈顶元素存在右孩子，则继续第2步
4.重复第2、3步，直到栈为空并且所有的节点都被访问
publicvoidinOrder(NodeRoot){
if(Root==null){
System.out.println("空树");
return;
}
Nodetmp=Root;
Stacks=newStack();
while(tmp!=null||!s.empty()){
//1.将根节点入栈
//2.将所有左孩子入栈
while(tmp!=null){
s.push(tmp);
tmp=tmp.leftChild;
}
//3.访问栈顶元素
tmp=s.pop();
System.out.print(tmp.data+"");
//4.如果栈顶元素存在右孩子，则将右孩子赋值给tmp，也就是将右孩子入栈
if(tmp.rightChild!=null){
tmp=tmp.rightChild;
}
//否则，将tmp置为null，表示下次要访问的是栈顶元素
else{
tmp=null;
}
}
System.out.println();
}
4.后序遍历。
后续遍历的非递归实现思路：
1.根节点入栈
2.将根节点的左子树入栈，直到最左，没有左孩子为止
3.得到栈顶元素的值，先不访问，判断栈顶元素是否存在右孩子，如果存在并且没有被访问，则将右孩子入栈，否则，就访问栈顶元素
publicvoidpostOrder(NodeRoot){
if(Root==null){
System.out.println("空树");
return;
}
Nodetmp=Root;//当前节点
Nodeprev=null;//上一次访问的节点
Stacks=newStack();
while(tmp!=null||!s.empty()){
//1.将根节点及其左孩子入栈
while(tmp!=null){
s.push(tmp);
tmp=tmp.leftChild;
}
if(!s.empty()){
//2.获取栈顶元素值
tmp=s.peek();
//3.没有右孩子，或者右孩子已经被访问过
if(tmp.rightChild==null||tmp.rightChild==prev){
//则可以访问栈顶元素
tmp=s.pop();
System.out.print(tmp.data+"");
//标记上一次访问的节点
prev=tmp;
tmp=null;
}
//4.存在没有被访问的右孩子
else{
tmp=tmp.rightChild;
}
}
}
System.out.println();
}
利用非递归算法来搜索二叉树中的某个元素java
层序遍历
可以利用层序遍历来解决这个问题
代码
booleansearchUsingLevelOrder(BinaryTreeNoderoot,intdata){
BinaryTreeNodetemp;
LLQueueq=newLLQueue();
if(root==null)
returnfalse;
q.enqueue(root);
while(q.isNotEmpty()){
temp=q.deQueue();
if(data==root.getData())
returntrue;
if(temp.getLeft()!=null)
q.enqueue(temp.getLeft());
if(temp.getRight()!=null)
q.enqueue(temp.getRight());
}
q.deleteQueue();
returnfalse;
}
Java递归、非递归实现二叉树遍历
最近找工作做笔试题发现很重要，就自己写了一点，和大家分享
importjava.util.Stack;
importjava.util.HashMap;
publicclassBinTree{
privatechardate;
privateBinTreelchild;
privateBinTreerchild;
publicBinTree(charc){
date=c;
}
//先序遍历递归
publicstaticvoidpreOrder(BinTreet){
if(t==null){
return;
}
System.out.print(t.date);
preOrder(t.lchild);
preOrder(t.rchild);
}
//中序遍历递归
publicstaticvoidInOrder(BinTreet){
if(t==null){
return;
}
InOrder(t.lchild);
System.out.print(t.date);
InOrder(t.rchild);
}
//后序遍历递归
publicstaticvoidPostOrder(BinTreet){
if(t==null){
return;
}
PostOrder(t.lchild);
PostOrder(t.rchild);
System.out.print(t.date);
}
//先序遍历非递归
publicstaticvoidpreOrder2(BinTreet){
Stacks=newStack();
while(t!=null||!s.empty()){
while(t!=null){
System.out.print(t.date);
s.push(t);
t=t.lchild;
}
if(!s.empty()){
t=s.pop();
t=t.rchild;
}
}
}
//中序遍历非递归
publicstaticvoidInOrder2(BinTreet){
Stacks=newStack();
while(t!=null||!s.empty()){
while(t!=null){
s.push(t);
t=t.lchild;
}
if(!s.empty()){
t=s.pop();
System.out.print(t.date);
t=t.rchild;
}
}
}
//后序遍历非递归
publicstaticvoidPostOrder2(BinTreet){
Stacks=newStack();
Stacks2=newStack();
Integeri=newInteger(1);
while(t!=null||!s.empty()){
while(t!=null){
s.push(t);
s2.push(newInteger(0));
t=t.lchild;
}
while(!s.empty()&&s2.peek().equals(i)){
s2.pop();
System.out.print(s.pop().date);
}
if(!s.empty()){
s2.pop();
s2.push(newInteger(1));
t=s.peek();
t=t.rchild;
}
}
}
publicstaticvoidmain(String[]args){
BinTreeb1=newBinTree('a');
BinTreeb2=newBinTree('b');
BinTreeb3=newBinTree('c');
BinTreeb4=newBinTree('d');
BinTreeb5=newBinTree('e');
/**
*a
*//
*bc
*//
*de
*/
b1.lchild=b2;
b1.rchild=b3;
b2.lchild=b4;
b2.rchild=b5;
BinTree.preOrder(b1);
System.out.println();
BinTree.preOrder2(b1);
System.out.println();
BinTree.InOrder(b1);
System.out.println();
BinTree.InOrder2(b1);
System.out.println();
BinTree.PostOrder(b1);
System.out.println();
BinTree.PostOrder2(b1);
}
}
到此这篇关于java二叉树的非递归遍历的文章就介绍到这了,更多相关java二叉树内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！