java二叉树的非递归遍历

二叉树的递归遍历比较简单，这里就不聊了。今天主要聊聊二叉树的非递归遍历，主要借助于“栈”后进先出的特性来保存节点的顺序，先序遍历和中序遍历相对来说比较简单，重点理解后序遍历。

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);
	}
}

到此这篇关于java二叉树的非递归遍历的文章就介绍到这了,更多相关java二叉树内容请搜索自学编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持自学编程网！

编程技巧