Java二叉樹的四種遍歷(遞歸與非遞歸)
一、先序遍歷與后序遍歷
先序遍歷根節(jié)點,再遍歷左子樹,再遍歷右子樹。
后序遍歷先遍歷左子樹,再遍歷右子樹,再遍歷根節(jié)點。
先序遍歷遞歸實現(xiàn):
public static void preOrderByRecursion(TreeNode root) { // 打印節(jié)點值 System.out.println(root.value); preOrder(root.left); preOrder(root.right); }
先序遍歷的非遞歸實現(xiàn):
非遞歸實現(xiàn)需要借助棧這樣一個數(shù)據(jù)結(jié)構(gòu),實際上遞歸實現(xiàn)也是依靠棧,只不過是隱式的。
- 先將根節(jié)點壓入棧中。
- 彈出棧中的節(jié)點,將彈出節(jié)點的右子節(jié)點壓入棧中,再將彈出節(jié)點的左子樹壓入棧中。
- 重復步驟2,直到棧為空。
public static void preOrder(TreeNode root) { if (root == null) { return; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.empty()) { TreeNode node = stack.pop(); // 打印節(jié)點值 System.out.print(node.value + " "); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } }
后序遍歷遞歸實現(xiàn):先序遍歷反過來,就不贅述了。
public static void postOrderByRecursion(TreeNode root) { postOrderByRecursion(root.left); postOrderByRecursion(root.right); System.out.println(root.value); }
后序遍歷非遞歸實現(xiàn):后序遍歷就是先序遍歷反過來,所以需要兩個棧,多出來的棧用來反向輸出。
public static void postOrder(TreeNode root) { if (root == null) { return; } Stack<TreeNode> s1 = new Stack<>(); Stack<TreeNode> s2 = new Stack<>(); s1.push(root); while (!s1.empty()) { TreeNode node = s1.pop(); s2.push(node); if (node.left != null) { s1.push(node.left); } if (node.right != null) { s1.push(node.right); } } while (!s2.empty()) { System.out.println(s2.pop().value); } }
二、中序遍歷
中序遍歷先遍歷左子樹,再遍歷根節(jié)點,再遍歷右子樹。
遞歸遍歷:
public static void inOrderByRecursion(TreeNode root) { if (root == null) { return; } inOrderByRecursion(root.left); // 打印節(jié)點值 System.out.println(root.value); inOrderByRecursion(root.right); }
非遞歸遍歷:
- 將二叉樹的左側(cè)“邊”從上到下依次壓入棧中。
- 從棧中彈出節(jié)點
- 對以彈出節(jié)點的右子節(jié)點為根節(jié)點的子樹,重復步驟1。
- 重復2、3步驟,直到棧為空。
public static void inOrder(TreeNode root) { if (root == null) { return; } Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null) { stack.push(cur); cur = cur.left; } while (!stack.empty()) { TreeNode node = stack.pop(); System.out.println(node.value); cur = node.right; while (cur != null) { stack.push(cur); cur = cur.left; } } }
三、層序遍歷
層序遍歷顧名思義就是一層一層,從左到右的遍歷二叉樹。需要用到隊列這一數(shù)據(jù)結(jié)構(gòu)。
- 將根節(jié)點推入隊列。
- 從隊列中取出一個節(jié)點。
- 先將取出節(jié)點的左子節(jié)點推入隊列,再將取出節(jié)點的右子節(jié)點推入隊列。
- 重復2、3步驟直到隊列中無節(jié)點可取。
public static void floorOrder(TreeNode root) { if (root == null) { return; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); System.out.println(node.value); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } }
到此這篇關(guān)于Java二叉樹的四種遍歷(遞歸與非遞歸)的文章就介紹到這了,更多相關(guān)Java二叉樹的四種遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Spring?Boot?整合?FreeMarker?實例分享
這篇文章主要分享了Spring?Boot整合FreeMarker?實例FreeMarker是一款模板引擎,即一種基于模板和要改變的數(shù)據(jù),并用來生成輸出文本,更多相關(guān)介紹需要的小伙伴可以參考下面文章內(nèi)容2022-05-05MyBatis-Plus邏輯刪除和字段自動填充的實現(xiàn)
本文主要介紹了MyBatis-Plus邏輯刪除和字段自動填充的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2022-08-08Bean?Searcher配合SpringBoot的使用詳解
這篇文章主要介紹了Bean?Searcher配合SpringBoot的使用,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-06-06mybatis-plus enum實現(xiàn)枚舉類型自動轉(zhuǎn)換
本文主要介紹了mybatis-plus enum實現(xiàn)枚舉類型自動轉(zhuǎn)換,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-07-07Apache?log4j2-RCE?漏洞復現(xiàn)及修復建議(CVE-2021-44228)
Apache?Log4j2是一款Java日志框架,大量應用于業(yè)務(wù)系統(tǒng)開發(fā)。2021年11月24日,阿里云安全團隊向Apache官方報告了Apache?Log4j2遠程代碼執(zhí)行漏洞(CVE-2021-44228),本文給大家介紹Apache?log4j2-RCE?漏洞復現(xiàn)(CVE-2021-44228)的相關(guān)知識,感興趣的朋友一起看看吧2021-12-12Java編程Post數(shù)據(jù)請求和接收代碼詳解
這篇文章主要介紹了Java編程Post數(shù)據(jù)請求和接收代碼詳解,涉及enctype的三種編碼,post與get等相關(guān)內(nèi)容,具有一定參考價值,需要的朋友可以了解下。2017-11-11