通過棧(Stack)實現對樹的遍歷

說到數的遍歷樹,長期以來的第一印象都是通過遞歸去實現。然而今天看了某位前輩的代碼,才發現使用棧去實現遍歷是那么簡單。理論上通過數組也是可以實現同等功能的,畢竟Stack也是通過數據去實現的。

package com.sysway.ui.widget;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;public class Traversal {/*** 通過棧實現對根節點下所有葉節點的遍歷* @param root 根節點* @return 葉節點集合*/private static List<TreeNode> traversalByStack(TreeNode root) {List<TreeNode> results = new ArrayList<TreeNode>();Stack<TreeNode> stack = new Stack<TreeNode>();stack.push(root); // 將元素推入棧中while (!stack.isEmpty()) {TreeNode node = stack.pop(); // 取出棧頂元素,并將該元素從棧中刪除if (node.isLeaf()) { // 如果是葉節點results.add(node);}else {List<TreeNode> childrens = node.getChildrens(); // 取非葉節點的所有子節點stack.addAll(childrens); // 將所有子節點加入棧}}return results;}/*** 通過遞歸實現對根節點下所有葉節點的遍歷* @param root 根節點* @return 葉節點集合*/private static List<TreeNode> traversalByRecursion(TreeNode node) {List<TreeNode> results = new ArrayList<TreeNode>();if (node.isLeaf()) {results.add(node);}else {for (TreeNode children : node.getChildrens()) {results.addAll(traversalByRecursion(children));}}return results;}public static void main(String[] args) {TreeNode node1 = new TreeNode("1");TreeNode node2 = new TreeNode("2");TreeNode node3 = new TreeNode("3");TreeNode node4 = new TreeNode("4");TreeNode node5 = new TreeNode("5");TreeNode node6 = new TreeNode("6");node1.addChildren(node2, node3);node2.addChildren(node4, node5);node5.addChildren(node6);List<TreeNode> leafs = traversalByStack(node1);System.out.println("---------Stack");for (TreeNode leaf : leafs) {System.out.println(leaf.getData());}List<TreeNode> leafs2 = traversalByRecursion(node1);System.out.println("---------Recursion");for (TreeNode leaf : leafs2) {System.out.println(leaf.getData());}}}class TreeNode {private List<TreeNode> childrens;private String data;public TreeNode(String data) {this.data = data;}public void addChildren(TreeNode... children) {if (children == null || children.length < 1) {return;}if (childrens == null) {childrens = new ArrayList<TreeNode>();}childrens.addAll(Arrays.asList(children));}public List<TreeNode> getChildrens() {return childrens;}public String getData() {return data;}public boolean isLeaf() {return childrens == null || childrens.isEmpty();}
}

樹的結構如圖:

輸出結果如下:

---------Stack
3
6
4
---------Recursion
4
6
3

特別鳴謝yanan!

?

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/273297.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/273297.shtml
英文地址,請注明出處:http://en.pswp.cn/news/273297.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

設計模式_01_單一原則

設計模式_01_單一原則 package designPatternOf_01; /*** 單一原則示例&#xff1a;動物呼吸* 引入的問題&#xff1a;魚不吸空氣&#xff0c;吸水*/ public class SinglePrinciple_01 {public static void main(String[] args) {Animal animalnew Animal();animal.breath(&quo…

StroyBoard中UICollectionView中添加Header和footer

到Storyboard中&#xff0c;選擇collection view controller中的"Collection View"。在Attributes inspector中&#xff0c;選擇"Section Header"和"Section Footer",一旦選中你就會在屏幕中看到下面的的顯示&#xff1a; 最重要的是&#xff0c…

樹形結構數據匯總查詢解決方案+優化求助

最近遇到一個地區數據匯總的問題&#xff0c;地區下的地址呈樹形結構&#xff0c;&#xff08;簡化結構&#xff09;如A市下有B、C區&#xff0c;B區下有D、E街道。先要查詢所有地區的人數&#xff08;包括子區域&#xff09;&#xff0c;如A的人數直屬A的人數B的人數C的人數D的…

find 是區分大小寫的。對于不區分大小寫的寫法(轉載)

轉自&#xff1a;http://justwinit.cn/post/3633/ 默認情況下&#xff0c;find 是區分大小寫的。對于不區分大小寫的 find&#xff0c;將 -iname 測試替換為 -name 測試。find downloads -iname "*.gif"downloads/.xvpics/Calendar05_enlarged.gifdownloads/lcmgcfe…

ORACLE會話以及SQL執行信息查詢

select t.BLOCKING_SESSION,t.SQL_ID,t.SID,t.SERIAL#,t.MACHINE,t.PROGRAM,t.ACTION,t.LOGON_TIME "登錄時間",trunc((sysdate - t.LOGON_TIME) * 24 * 60 * 60) || s "登錄時長",trunc(nvl(s.ELAPSED_TIME / decode(s.EXECUTIONS, 0, 1, s.EXECUTIONS) /…

Dom4j 學習筆記

dom4j 是一種解析 XML 文檔的開放源代碼 XML 框架。dom4j下載地址 本文主要記載了一些簡單的使用方法。 一、xml文件的解析 dom4j既可以解析普通的xml文件&#xff0c;也可以解析一個InputStream&#xff0c;先看看xml文件長什么樣子&#xff1a; <books><book>&l…

交叉連接(CROSS JOIN)的實際應用

一次偶然的機會&#xff0c;使用到了萬年不用的交叉連接&#xff08;CROSS JOIN&#xff09; 業務場景如下&#xff1a; 1、存在多個運營商&#xff0c;每個運營商下面都有各種類型的設備&#xff0c;不同運營商的設備不完全相同&#xff1b; 2、任何設備有且僅有兩種用途‘…

Atitit.操作注冊表 樹形數據庫 注冊表的歷史 java版本類庫總結

Atitit.操作注冊表 樹形數據庫 注冊表的歷史 java版本類庫總結 1. 注冊表是樹形數據庫 1 2. 注冊表的由來 1 3. Java 操作注冊表 2 3.1. 使用Preferences API &#xff08;限定訪問路徑了&#xff09; 2 3.2. 使用JNI 3 3.3. Jregistrykey 推薦 4 3.4. Jregistry 4 4. org.ope…

C# xml文件讀取與修改

c#讀寫xml文件已知有一個XML文件&#xff08;bookstore.xml&#xff09;如下&#xff1a; Code<?xml version"1.0" encoding"gb2312"?><bookstore> <book genre"fantasy" ISBN"2-3631-4"> <title>Obero…

外連接從表過濾

1、使用left join時從表的過濾 WITH a AS( SELECT A aid FROM dual UNION ALL SELECT B FROM dual UNION ALL SELECT C FROM dual UNION ALL SELECT D FROM dual UNION ALL SELECT E FROM dual ), b AS( SELECT A aid,10 num,1 type FROM dual UNION ALL SELECT B,20,2 FROM d…

php pcntl 多進程學習

1、捕獲子進程退出&#xff08;監聽SIGCHLD信號&#xff0c;然后調用 pcntl_wait 函數&#xff09; declare(ticks1);pcntl_signal(SIGCHLD, "sig_handler"); function sig_handler($signo) {switch ($signo) {case SIGCHLD:$status 0;$child_id pcntl_wait($statu…

Oracle取最大/最小值函數

SELECT greatest(DATE2020-01-01,DATE2020-01-03,DATE2020-01-05,DATE2020-01-07,DATE2020-01-09) 最大值, least(1,3,5,7,9) 最小值 FROM dual; SELECT 1 FROM dual WHERE greatest(1,3,5,7,9) > 8;

ORACLE將查詢字段指定為某種類型

SELECT CAST(張三 AS VARCHAR2(20)) name FROM dual; 一般來說在查詢時很少有用到這種語句&#xff0c;但是使用CREATE TABLE ... AS SELECT ...語句的時候這個就很好用了 --建表 CREATE TABLE test01 AS SELECT 張三 name FROM dual; --正常插入數據 INSERT INTO test01 SEL…

Less Css 教程

http://www.w3cplus.com/css/less&#xff0c;這個東西太吊了&#xff01;轉載于:https://www.cnblogs.com/wln3344/p/4479014.html

分組查詢最晚一條數據(ORACLE)

現有客戶表&#xff0c;交費表&#xff0c;需查詢每個存在交費記錄客戶的最后一筆交費信息 這里提供兩種方式 注&#xff1a;客戶不會在同一時間有兩條交費&#xff0c;SQL可直接執行 --查詢客戶名稱&#xff0c;最后一筆交費時間&#xff0c;以及最后一筆交費金額 WITH --客…

ORACLE循環中使用序列

在批量生成數據時&#xff0c;經常會用到序列的Nextval&#xff0c;今天碰到了這樣的情況&#xff0c;日常記錄&#xff0c;下附解決方案。先看這段腳本 DECLARE i INTEGER; BEGINFOR cur IN 1..5 LOOPi : DomainObjectId.Nextval;dbms_output.put_line(i);END LOOP; END; 編…

常用的機器學習數據挖掘知識點【轉】

轉自&#xff1a; 【基礎】常用的機器學習&數據挖掘知識點 Basis(基礎)&#xff1a; MSE(Mean Square Error 均方誤差)&#xff0c;LMS(LeastMean Square 最小均方)&#xff0c;LSM(Least Square Methods 最小二乘法)&#xff0c;MLE(MaximumLikelihood Estimation最大似然…

tomcat運行問題解決方法

早上過來遇到一個非常奇怪的問題&#xff0c;運行一個新的項目&#xff0c;運行環境都沒問題&#xff0c;可是在調試的時候&#xff0c;總是出錯。 錯誤代碼&#xff1a; log4j:WARN No appenders could be found for logger log4j:WARN Please initialize the log4j system p…

團隊開發——沖刺1.d

沖刺階段一&#xff08;第四天&#xff09; 1、昨天做了什么&#xff1f; 完成部分界面設置&#xff0c;補充三層難度界面、游戲結束界面。 2、今天準備做什么&#xff1f; 優化界面細節。查看C#資料&#xff0c;再解決自己電腦的問題。 3、遇到什么困難&#xff1f; 已經固定好…

10. javacript高級程序設計-DOM

1. DOM DOM(文檔對象模型)是針對HTML和XML文檔的一個API&#xff08;應用程序接口&#xff09; 1.1 節點層次 DOM可以將任何HTML和XML文檔描繪成一個由多層節點構成的結構。節點分為幾種不同的類型&#xff0c;每種類型分別表示文檔中不同的信息及標記。 1.1.1 Node類型 DOM1中…