本篇內容主要講解“Java二叉樹的遍歷方式有哪些”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學習“Java二叉樹的遍歷方式有哪些”吧!
二叉樹的四種遍歷方式:
二叉樹的遍歷(traversing binary tree)是指從根結點出發,按照某種次序依次訪問二叉樹中所有的結點,使得每個結點被訪問依次且僅被訪問一次。
四種遍歷方式分別為:先序遍歷、中序遍歷、后序遍歷、層序遍歷。
遍歷之前,我們首先介紹一下,如何創建一個二叉樹,在這里用的是先建左樹在建右樹的方法,
首先要聲明結點TreeNode類,代碼如下:
public class TreeNode { public int data; public TreeNode leftChild; public TreeNode rightChild; public TreeNode(int data){ this.data = data; } }
再來創建一顆二叉樹:
/** * 構建二叉樹 * @param list 輸入序列 * @return */ public static TreeNode createBinaryTree(LinkedList<Integer> list){ TreeNode node = null; if(list == null || list.isEmpty()){ return null; } Integer data = list.removeFirst(); if(data!=null){ node = new TreeNode(data); node.leftChild = createBinaryTree(list); node.rightChild = createBinaryTree(list); } return node; }
接下來按照上面列的順序一一講解,
首先來看前序遍歷,所謂的前序遍歷就是先訪問根節點,再訪問左節點,最后訪問右節點,
如上圖所示,前序遍歷結果為:
ABDFECGHI
實現代碼如下:
/** * 二叉樹前序遍歷 根-> 左-> 右 * @param node 二叉樹節點 */ public static void preOrderTraveral(TreeNode node){ if(node == null){ return; } System.out.print(node.data+" "); preOrderTraveral(node.leftChild); preOrderTraveral(node.rightChild); }
再者就是中序遍歷,所謂的中序遍歷就是先訪問左節點,再訪問根節點,最后訪問右節點,
如上圖所示,中序遍歷結果為:
DBEFAGHCI
實現代碼如下:
/** * 二叉樹中序遍歷 左-> 根-> 右 * @param node 二叉樹節點 */ public static void inOrderTraveral(TreeNode node){ if(node == null){ return; } inOrderTraveral(node.leftChild); System.out.print(node.data+" "); inOrderTraveral(node.rightChild); }
最后就是后序遍歷,所謂的后序遍歷就是先訪問左節點,再訪問右節點,最后訪問根節點。
如上圖所示,后序遍歷結果為:
DEFBHGICA
實現代碼如下:
/** * 二叉樹后序遍歷 左-> 右-> 根 * @param node 二叉樹節點 */ public static void postOrderTraveral(TreeNode node){ if(node == null){ return; } postOrderTraveral(node.leftChild); postOrderTraveral(node.rightChild); System.out.print(node.data+" "); }
講完上面三種遞歸的方法,下面再給大家講講非遞歸是如何實現前中后序遍歷的
還是一樣,先看非遞歸前序遍歷
1.首先申請一個新的棧,記為stack;
2.聲明一個結點treeNode,讓其指向node結點;
3.如果treeNode的不為空,將treeNode的值打印,并將treeNode入棧,然后讓treeNode指向treeNode的右結點,
4.重復步驟3,直到treenode為空;
5.然后出棧,讓treeNode指向treeNode的右孩子
6.重復步驟3,直到stack為空.
實現代碼如下:
public static void preOrderTraveralWithStack(TreeNode node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode treeNode = node; while(treeNode!=null || !stack.isEmpty()){ //迭代訪問節點的左孩子,并入棧 while(treeNode != null){ System.out.print(treeNode.data+" "); stack.push(treeNode); treeNode = treeNode.leftChild; } //如果節點沒有左孩子,則彈出棧頂節點,訪問節點右孩子 if(!stack.isEmpty()){ treeNode = stack.pop(); treeNode = treeNode.rightChild; } } }
中序遍歷非遞歸,在此不過多敘述具體步驟了,
具體過程:
1.申請一個新棧,記為stack,申請一個變量cur,初始時令treeNode為頭節點;
2.先把treeNode節點壓入棧中,對以treeNode節點為頭的整棵子樹來說,依次把整棵樹的左子樹壓入棧中,即不斷令treeNode=treeNode.leftChild,然后重復步驟2;
3.不斷重復步驟2,直到發現cur為空,此時從stack中彈出一個節點記為treeNode,打印node的值,并讓treeNode= treeNode.right,然后繼續重復步驟2;
4.當stack為空并且cur為空時結束。
public static void inOrderTraveralWithStack(TreeNode node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode treeNode = node; while(treeNode!=null || !stack.isEmpty()){ while(treeNode != null){ stack.push(treeNode); treeNode = treeNode.leftChild; } if(!stack.isEmpty()){ treeNode = stack.pop(); System.out.print(treeNode.data+" "); treeNode = treeNode.rightChild; } } }
后序遍歷非遞歸實現,后序遍歷這里較前兩者實現復雜一點,我們需要一個標記位來記憶我們此時節點上一個節點,具體看代碼注釋
public static void postOrderTraveralWithStack(TreeNode node){ Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode treeNode = node; TreeNode lastVisit = null; //標記每次遍歷最后一次訪問的節點 while(treeNode!=null || !stack.isEmpty()){//節點不為空,結點入棧,并且指向下一個左孩子 while(treeNode!=null){ stack.push(treeNode); treeNode = treeNode.leftChild; } //棧不為空 if(!stack.isEmpty()){ //出棧 treeNode = stack.pop(); /** * 這塊就是判斷treeNode是否有右孩子, * 如果沒有輸出treeNode.data,讓lastVisit指向treeNode,并讓treeNode為空 * 如果有右孩子,將當前節點繼續入棧,treeNode指向它的右孩子,繼續重復循環 */ if(treeNode.rightChild == null || treeNode.rightChild == lastVisit) { System.out.print(treeNode.data + " "); lastVisit = treeNode; treeNode = null; }else{ stack.push(treeNode); treeNode = treeNode.rightChild; } } } }
最后再給大家介紹一下層序遍歷
具體步驟如下:
1.首先申請一個新的隊列,記為queue;
2.將頭結點head壓入queue中;
3.每次從queue中出隊,記為node,然后打印node值,如果node左孩子不為空,則將左孩子入隊;如果node的右孩子不為空,則將右孩子入隊;
4.重復步驟3,直到queue為空。
實現代碼如下:
public static void levelOrder(TreeNode root){ LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ root = queue.pop(); System.out.print(root.data+" "); if(root.leftChild!=null) queue.add(root.leftChild); if(root.rightChild!=null) queue.add(root.rightChild); } }
到此,相信大家對“Java二叉樹的遍歷方式有哪些”有了更深的了解,不妨來實際操作一番吧!這里是億速云網站,更多相關內容可以進入相關頻道進行查詢,關注我們,繼續學習!
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。