快捷導(dǎo)航

java棧實現(xiàn)二叉樹的非遞歸遍歷的示例代碼

更新時間：2021年03月21日 15:17:08 作者：LuckyCCat

這篇文章主要介紹了java棧實現(xiàn)二叉樹的非遞歸遍歷,本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下

一般來說遍歷二叉樹用到遞歸，但是用Stack進行遍歷也是一個不錯的方法。

二叉樹設(shè)置

class Node{
	public int val;
	public Node left;
	public Node right;
	
	public Node(int v) {
		val=v;
		left=null;
		right=null;
	}
}

public class Main {
	public static void main(String[] args) {
		Node head =new Node(0);
		Node node1=new Node(1);
		Node node2=new Node(2);
		Node node3=new Node(3);
		Node node4=new Node(4);
		Node node5=new Node(5);
		Node node6=new Node(6);
		head.left=node1;
		head.right=node2;
		node1.left=node3;
		node1.right=node4;
		node2.left=node5;
		node2.right=node6;
		pos2(head);
		pos1(head);
		in(head);
	}

在這里插入圖片描述

前序遍歷

思想和流程

彈出就打印
如果有右子樹，就壓入
如果有左子樹，就壓入

public static void pos1(Node h) {
	System.out.print("先序遍歷 ");
	if(h!=null) {
		Stack<Node>stack =new Stack<Node>();
		stack.push(h);
		while(!stack.isEmpty()) {
			h=stack.pop();
			System.out.print(h.val+" ");
			if(h.right!=null) {
				stack.push(h.right);
			}
			if(h.left!=null) {
				stack.push(h.left);
			}
		}
	}
	System.out.println();
}

后序遍歷

前序遍歷的順序是父節(jié)點，左，右，而后序遍歷的順序是左，右，父節(jié)點，也就是說前序遍歷左右替換之后就是后序遍歷的倒過來。所以只要把前序遍歷時候左右子節(jié)點壓棧的順序調(diào)換一下，再用另一個棧儲存，然后再彈出就是后序遍歷了。在此代碼就不多寫了。

中序遍歷

思路和流程

彈出就打印
整條左邊界依次入棧
上一條件無法繼續(xù)，彈出打印，開始右子樹

public static void in(Node h) {
	System.out.print("中序遍歷 ");
	if(h!=null) {
		Stack<Node>stack =new Stack<Node>();
		while(!stack.isEmpty()||h!=null) {
			if(h!=null) {
				stack.push(h);
				h=h.left;
			}else {
				h=stack.pop();
				System.out.print(h.val+" ");
				h=h.right;
			}
		}
	}
	System.out.println();
}

后序遍歷變體

用一個Stack實現(xiàn)
思路是左節(jié)點沒處理就處理左節(jié)點，左節(jié)點處理過了就處理右節(jié)點，右節(jié)點處理完了就返回。

public static void pos2(Node h) {
	if(h!=null) {
		Stack<Node>stack =new Stack<Node>();
		stack.push(h);
		Node c=null;//用c記錄上一次被打印的節(jié)點
		while(!stack.isEmpty()) {
			c=stack.peek();
			if(c.left!=null&&h!=c.left&&h!=c.right) {
				stack.push(c.left);
			}else if(c.right!=null&&h!=c.right) {
				stack.push(c.right);
			}else {
				System.out.print(stack.pop().val+" ");
				h=c;//記錄本次被打印的節(jié)點
			}
		}
	}
}

打印結(jié)果

在這里插入圖片描述