二叉树的递归遍历比较简单，这里就不聊了。今天主要聊聊二叉树的非递归遍历，主要借助于“栈”后进先出的特性来保存节点的顺序，先序遍历和中序遍历相对来说比较简单，重点理解后序遍历。
1. 先看看节点类型：
//二叉树的节点类型
private class Node{
int data; //节点值
Node leftChild; //左孩子
Node rightChild; //右孩子
public Node(int data) {
this.data=data;
}
}
2.先序遍历。
非递归先序遍历的思路如下：
1.先将根节点入栈
2.访问根节点
3.如果根节点存在右孩子，则将右孩子入栈
4.如果根节点存在左孩子，则将左孩子入栈（注意：一定是右孩子先入栈，然后左孩子入栈）
5.重复2-4
public void preOrder(Node Root) {
if(Root==null) {
System.out.println("空树");
return;
}
Node tmp=Root;
Stack<Node> s=new Stack<Node>();
s.push(tmp); //根节点入栈
while(!s.empty()) {
//1.访问根节点
Node p=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步，直到栈为空并且所有的节点都被访问
public void inOrder(Node Root) {
if(Root==null) {
System.out.println("空树");
return;
}
Node tmp=Root;
Stack<Node> s=new Stack<Node>();
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.得到栈顶元素的值，先不访问，判断栈顶元素是否存在右孩子，如果存在并且没有被访问，则将右孩子入栈，否则，就访问栈顶元素
public void postOrder(Node Root) {
if(Root==null) {
System.out.println("空树");
return;
}
Node tmp=Root; //当前节点
Node prev=null; //上一次访问的节点
Stack<Node> s=new Stack<Node>();
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
层序遍历
可以利用层序遍历来解决这个问题
代码
boolean searchUsingLevelOrder(BinaryTreeNode root,int data){
BinaryTreeNode temp;
LLQueue q = new LLQueue();
if(root == null)
return false;
q.enqueue(root);
while(q.isNotEmpty()){
temp = q.deQueue();
if(data == root.getData())
return true;
if(temp.getLeft() != null)
q.enqueue(temp.getLeft());
if(temp.getRight() != null)
q.enqueue(temp.getRight());
}
q.deleteQueue();
return false;
}
Java递归、非递归实现二叉树遍历
最近找工作做笔试题发现很重要，就自己写了一点，和大家分享
import java.util.Stack;
import java.util.HashMap;
public class BinTree {
private char date;
private BinTree lchild;
private BinTree rchild;
public BinTree(char c) {
date = c;
}
// 先序遍历递归
public static void preOrder(BinTree t) {
if (t == null) {
return;
}
System.out.print(t.date);
preOrder(t.lchild);
preOrder(t.rchild);
}
// 中序遍历递归
public static void InOrder(BinTree t) {
if (t == null) {
return;
}
InOrder(t.lchild);
System.out.print(t.date);
InOrder(t.rchild);
}
// 后序遍历递归
public static void PostOrder(BinTree t) {
if (t == null) {
return;
}
PostOrder(t.lchild);
PostOrder(t.rchild);
System.out.print(t.date);
}
// 先序遍历非递归
public static void preOrder2(BinTree t) {
Stack<BinTree> s = new Stack<BinTree>();
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;
}
}
}
// 中序遍历非递归
public static void InOrder2(BinTree t) {
Stack<BinTree> s = new Stack<BinTree>();
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;
}
}
}
// 后序遍历非递归
public static void PostOrder2(BinTree t) {
Stack<BinTree> s = new Stack<BinTree>();
Stack<Integer> s2 = new Stack<Integer>();
Integer i = new Integer(1);
while (t != null || !s.empty()) {
while (t != null) {
s.push(t);
s2.push(new Integer(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(new Integer(1));
t = s.peek();
t = t.rchild;
}
}
}
public static void main(String[] args) {
BinTree b1 = new BinTree('a');
BinTree b2 = new BinTree('b');
BinTree b3 = new BinTree('c');
BinTree b4 = new BinTree('d');
BinTree b5 = new BinTree('e');
/**
* a
* / /
* b c
* / /
* d e
*/
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);
}
}
