快捷導(dǎo)航

java二叉樹的非遞歸遍歷

更新時(shí)間：2020年12月04日 18:25:01 作者：隨新飛翔

二叉樹的遞歸遍歷比較簡(jiǎn)單，這里就不聊了,今天主要聊聊二叉樹的非遞歸遍歷，主要借助于“棧”后進(jìn)先出的特性來(lái)保存節(jié)點(diǎn)的順序，先序遍歷和中序遍歷相對(duì)來(lái)說(shuō)比較簡(jiǎn)單，重點(diǎn)理解后序遍歷

二叉樹的遞歸遍歷比較簡(jiǎn)單，這里就不聊了。今天主要聊聊二叉樹的非遞歸遍歷，主要借助于“?！焙筮M(jìn)先出的特性來(lái)保存節(jié)點(diǎn)的順序，先序遍歷和中序遍歷相對(duì)來(lái)說(shuō)比較簡(jiǎn)單，重點(diǎn)理解后序遍歷。

1. 先看看節(jié)點(diǎn)類型：

//二叉樹的節(jié)點(diǎn)類型
private class Node{
	int data; //節(jié)點(diǎn)值
	Node leftChild; //左孩子
	Node rightChild; //右孩子
	public Node(int data) {
		this.data=data;
	}
}

2.先序遍歷。

非遞歸先序遍歷的思路如下：

1.先將根節(jié)點(diǎn)入棧
2.訪問(wèn)根節(jié)點(diǎn)
3.如果根節(jié)點(diǎn)存在右孩子，則將右孩子入棧
4.如果根節(jié)點(diǎn)存在左孩子，則將左孩子入棧（注意：一定是右孩子先入棧，然后左孩子入棧）
5.重復(fù)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); //根節(jié)點(diǎn)入棧
	while(!s.empty()) {
		//1.訪問(wèn)根節(jié)點(diǎn)
		Node p=s.pop();
		System.out.print(p.data+" ");
		//2.如果根節(jié)點(diǎn)存在右孩子，則將右孩子入棧
		if(p.rightChild!=null) {
			s.push(p.rightChild);
		}
		//3.如果根節(jié)點(diǎn)存在左孩子，則將左孩子入棧
		if(p.leftChild!=null) {
			s.push(p.leftChild);
		}
	}
	System.out.println();
}

3.中序遍歷。

非遞歸中序遍歷的思路如下：
1.先將根節(jié)點(diǎn)入棧
2.將當(dāng)前節(jié)點(diǎn)的所有左孩子入棧，直到左孩子為空
3.訪問(wèn)棧頂元素，如果棧頂元素存在右孩子，則繼續(xù)第2步
4.重復(fù)第2、3步，直到棧為空并且所有的節(jié)點(diǎn)都被訪問(wèn)

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.將根節(jié)點(diǎn)入棧
		//2.將所有左孩子入棧
		while(tmp!=null) {
			s.push(tmp);
			tmp=tmp.leftChild;
		}
		//3.訪問(wèn)棧頂元素
		tmp=s.pop();
		System.out.print(tmp.data+" ");
		//4.如果棧頂元素存在右孩子，則將右孩子賦值給tmp，也就是將右孩子入棧
		if(tmp.rightChild!=null) {
			tmp=tmp.rightChild;
		}
		//否則，將tmp置為null，表示下次要訪問(wèn)的是棧頂元素
		else {
			tmp=null;
		}
	}
	System.out.println();
}

4.后序遍歷。

后續(xù)遍歷的非遞歸實(shí)現(xiàn)思路：
1.根節(jié)點(diǎn)入棧
2.將根節(jié)點(diǎn)的左子樹入棧，直到最左，沒(méi)有左孩子為止
3.得到棧頂元素的值，先不訪問(wèn)，判斷棧頂元素是否存在右孩子，如果存在并且沒(méi)有被訪問(wèn)，則將右孩子入棧，否則，就訪問(wèn)棧頂元素

	public void postOrder(Node Root) {
		if(Root==null) {
			System.out.println("空樹");
			return;
		}
		Node tmp=Root; //當(dāng)前節(jié)點(diǎn)
		Node prev=null; //上一次訪問(wèn)的節(jié)點(diǎn)
		Stack<Node> s=new Stack<Node>();
		while(tmp!=null || !s.empty()) {
			//1.將根節(jié)點(diǎn)及其左孩子入棧
			while(tmp!=null) {
				s.push(tmp);
				tmp=tmp.leftChild;
			}
			
			if(!s.empty()) {
				//2.獲取棧頂元素值
				tmp=s.peek();
				//3.沒(méi)有右孩子，或者右孩子已經(jīng)被訪問(wèn)過(guò)
				if(tmp.rightChild==null || tmp.rightChild==prev) {
					//則可以訪問(wèn)棧頂元素
					tmp=s.pop();
					System.out.print(tmp.data+" ");
					//標(biāo)記上一次訪問(wèn)的節(jié)點(diǎn)
					prev=tmp;
					tmp=null;
				}
				//4.存在沒(méi)有被訪問(wèn)的右孩子
				else {
					tmp=tmp.rightChild;
				}
			}
		}
		System.out.println();
	}

利用非遞歸算法來(lái)搜索二叉樹中的某個(gè)元素java

層序遍歷
可以利用層序遍歷來(lái)解決這個(gè)問(wèn)題

代碼

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遞歸、非遞歸實(shí)現(xiàn)二叉樹遍歷

最近找工作做筆試題發(fā)現(xiàn)很重要，就自己寫了一點(diǎn)，和大家分享

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

到此這篇關(guān)于java二叉樹的非遞歸遍歷的文章就介紹到這了,更多相關(guān)java二叉樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: