您好,登錄后才能下訂單哦!
本篇文章給大家分享的是有關(guān)Java中的遍歷怎么利用二叉樹實現(xiàn),小編覺得挺實用的,因此分享給大家學(xué)習(xí),希望大家閱讀完這篇文章后可以有所收獲,話不多說,跟著小編一起來看看吧。
遞歸實現(xiàn)
public void preorder_Traversal(TreeNode root) { if(root==null)return; //訪問節(jié)點的邏輯代碼塊 System.out.print(root.val+" "); preorder_Traversal(root.left); preorder_Traversal(root.right); }
非遞歸過程如下:
1.每遍歷一個節(jié)點的時候,先節(jié)點入棧,然后尋找當(dāng)前節(jié)點的左子節(jié)點。(因為是前序遍歷,所以在節(jié)點入棧之前就可以對節(jié)點進(jìn)行訪問)
2.當(dāng)某個節(jié)點的左子節(jié)點,當(dāng)左子節(jié)點不為空的時候,重復(fù)過程1.
3.當(dāng)左子節(jié)點為空的時候?qū)?dāng)前節(jié)點出棧,并且通過其尋找右子節(jié)點,右子節(jié)點不為空的時候,重復(fù)過程1-2
4.當(dāng)右子節(jié)點也為空的時候,則跳回上一個該節(jié)點的父節(jié)點(即因為當(dāng)前節(jié)點已經(jīng)出棧,所以現(xiàn)在在棧中最上層的節(jié)點是當(dāng)前節(jié)點的父節(jié)點)
非遞歸實現(xiàn)
public void preorder(TreeNode root) { Stack<TreeNode> stack=new Stack<>(); while(root!=null||!stack.isEmpty()) { //當(dāng)前節(jié)點不為空,則入棧,確保最后遍歷到的節(jié)點沒有左子節(jié)點 //因為是前序遍歷,所以再遍歷到每個節(jié)點的時候,都可以先訪問,再尋找其左右子節(jié)點。 while(root!=null) { System.out.print(root.val+" "); stack.push(root); root=root.left; } if(!stack.empty()) { //把這兩步看成是一步,找到右節(jié)點,并把已處理的中節(jié)點從stack當(dāng)中去除 root=stack.pop(); root=root.right; } } }
遞歸實現(xiàn)
public void inorder_Traversal(TreeNode root) { if(root==null)return; inorder_Traversal(root.left); //訪問節(jié)點的邏輯代碼塊 System.out.print(root.val+" "); inorder_Traversal(root.right); }
非遞歸
對比前序、中序,發(fā)現(xiàn)代碼幾乎一模一樣,但唯一的不同的是,訪問節(jié)點的位置不一樣,中序遍歷是當(dāng)左子節(jié)點被訪問過,或者不存在的時候,才可以訪問中間節(jié)點,所以再該處,訪問節(jié)點的位置放在了當(dāng)左子節(jié)點不存在的時候,即節(jié)點出棧的時候,即是左子節(jié)點不存在的時候進(jìn)行訪問。
非遞歸實現(xiàn)
public void Inorder(TreeNode root) { Stack<TreeNode> stack=new Stack<>(); while(root!=null||!stack.isEmpty()) { //當(dāng)前節(jié)點不為空,則入棧,確保最后遍歷到的節(jié)點沒有左子節(jié)點 while(root!=null) { stack.push(root); root=root.left; } //通過當(dāng)前節(jié)點,跳到當(dāng)前節(jié)點的右節(jié)點,因為是中序遍歷,所以當(dāng)前節(jié)點沒有左節(jié)點的時候,就 可以訪問當(dāng)前節(jié)點 if(!stack.empty()) { root=stack.pop(); System.out.print(root.val+" "); root=root.right; } } }
遞歸實現(xiàn)
public void postorder_Traversal(TreeNode root) { if(root==null)return; postorder_Traversal(root.left); postorder_Traversal(root.right); //訪問節(jié)點的邏輯代碼塊 System.out.print(root.val+" "); }
非遞歸版本一
借助兩個棧來存儲我們的節(jié)點以及標(biāo)示位,過程如下:
1.每遍歷一個節(jié)點的時候,先節(jié)點入棧s,并且s2入棧一個標(biāo)識位0,然后尋找當(dāng)前節(jié)點的左子節(jié)點。
2.當(dāng)某個節(jié)點的左子節(jié)點,當(dāng)左子節(jié)點不為空的時候,重復(fù)過程1.
3.當(dāng)左子節(jié)點為空的時候?qū)?dāng)前節(jié)點peek出(即將節(jié)點拿出,但棧中還是有該節(jié)點),并且此時將s2對應(yīng)棧頂?shù)臉?biāo)識位改為1,通過其尋找右子節(jié)點,右子節(jié)點不為空的時候,重復(fù)過程1-2
4.當(dāng)右子節(jié)點也為空的時候,并且s2對應(yīng)的標(biāo)識符為1的時候,則彈出s1棧頂?shù)漠?dāng)前節(jié)點,并且將s2的標(biāo)識符彈出(即因為當(dāng)前節(jié)點還沒有出棧,所以現(xiàn)在在棧中最上層的節(jié)點是當(dāng)前節(jié)),注意s1彈出當(dāng)前節(jié)點并訪問,但是不賦值給root,在這個root此時還是null
5.進(jìn)入過程3,此時root被peek賦值到當(dāng)前節(jié)點的父節(jié)點(因為在過程4當(dāng)中,已經(jīng)pop出了當(dāng)前節(jié)點,所以s1棧頂是當(dāng)前節(jié)點的父節(jié)點)的右子節(jié)點。
6.重復(fù)過程1-5
public void Postorder(TreeNode root) { Stack<TreeNode> s =new Stack<>(); Stack<Integer> s2 =new Stack<>(); Integer i=new Integer(1); while(root!=null||!s.isEmpty()) { //只要當(dāng)前節(jié)點非空,就入棧 while(root!=null) { s.push(root); s2.push(new Integer(0)); root=root.left; } //s2當(dāng)中如果存1,則意味著當(dāng)前s1對應(yīng)的節(jié)點的左右子節(jié)點都已經(jīng)遍歷過了。 while(!s.empty()&&s2.peek().equals(i)) { s2.pop(); System.out.print(s.pop().val+" "); } if(!s.isEmpty()) { s2.pop(); s2.push(new Integer(1)); root=s.peek(); root=root.right; } } }
非遞歸版本二
實現(xiàn)思路:
在進(jìn)行后序遍歷的時候是先要遍歷左子樹,然后在遍歷右子樹,最后才遍歷根節(jié)點。所以在非遞歸的實現(xiàn)中要先把根節(jié)點入棧,然后再把左子樹入棧直到左子樹為空,此時停止入棧。此時棧頂就是需要訪問的元素,所以直接取出訪問p。在訪問結(jié)束后,還要判斷被訪問的節(jié)點p是否為棧頂節(jié)點的左子樹,如果是的話那么還需要訪問棧頂節(jié)點的右子樹,所以將棧頂節(jié)點的右子樹取出賦值給p。如果不是的 話則說明棧頂節(jié)點的右子樹已經(jīng)訪問完了,那么現(xiàn)在可以訪問棧頂節(jié)點了,所以此時將p賦值為null。判斷結(jié)束的條件是p不為空或者棧不為空,若果兩個條件都不滿足的話,說明所有節(jié)點都已經(jīng)訪問完成。
非遞歸實現(xiàn)
public void postOrder(Node root) { Stack<Node> s = new Stack<Node>(); Node p = root; while (p != null || !s.empty()) { while(p != null) { s.push(p); p = p.left; } p = s.pop(); System.out.print(p.val+" "); //這里需要判斷一下,當(dāng)前p是否為棧頂?shù)淖笞訕?,如果是的話那么還需要先訪問右子樹才能訪問根節(jié)點 //如果已經(jīng)是不是左子樹的話,那么說明左右子書都已經(jīng)訪問完畢,可以訪問根節(jié)點了,所以講p復(fù)制為NULL //取根節(jié)點 if (!s.empty() && p == s.peek().left) { p = s.peek().right; } else p = null; } }
用隊列實現(xiàn),步驟是:
1.對于不為空的結(jié)點,先把該結(jié)點加入到隊列中;
2.從隊中拿出結(jié)點,如果該結(jié)點的左右結(jié)點不為空,就分別把左右結(jié)點加入到隊列中;
3.重復(fù)以上操作直到隊列為空;
public void LaywerTraversal(TreeNode root){ if(root==null) return; LinkedList<TreeNode> list = new LinkedList<TreeNode>(); list.add(root); TreeNode currentNode; while(!list.isEmpty()){ currentNode=list.poll(); System.out.println(currentNode.val); if(currentNode.left!=null){ list.add(currentNode.left); } if(currentNode.right!=null){ list.add(currentNode.right); } } }
以上就是Java中的遍歷怎么利用二叉樹實現(xiàn),小編相信有部分知識點可能是我們?nèi)粘9ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學(xué)到更多知識。更多詳情敬請關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。