java二叉树的非递归遍历

Z时代
2024-01-10
分类：综合

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

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