你的位置:123新聞網 > 科技 > Java生成樹中的從根到葉子節點的所有路徑 10

Java生成樹中的從根到葉子節點的所有路徑 10

時間:2022-06-01 22:26瀏覽次數:60

1 楼: HDD001


方法是在dfs的過程中維護dfs的路徑,到達葉子結點時將路徑加入到答案中,具體見代碼的註釋。
輸入格式爲:
7 A
A B
C A
D B
E B
C F
C G
其中,第一行表示結點數量n和根結點編號,第[2..n + 1]行每行兩個字符u和v,表示樹邊。


import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
static final int maxn = 1000;

int n;                // 樹的結點個數
char root;            // 樹的根
List> ans = new ArrayList>();    // 結果,存放所有路徑
boolean[][] G = new boolean[maxn][maxn];                        // 鄰接矩陣

/**
* dfs
* @param u        當前到達的結點
* @param fa    當前結點的父節點
* @param path    根到fa的路徑
*/
void dfs(char u, char fa, List path) {
path.add(u);
boolean leaf = true;            // u爲葉子結點
for(char v = 'A'; v <= 'Z'; ++v) {
if(G[u][v] && v != fa) {    // 鄰接矩陣中有別的邊
leaf = false;            // u不是葉子結點
dfs(v, u, path);
}
}
if(leaf) {                        // u爲葉子結點,將路徑加入到答案
List pt = new ArrayList();
for(Character c : path) pt.add(c);
ans.add(pt);
}

path.remove(path.size() - 1);
}

public void go() throws FileNotFoundException
{
Scanner in = new Scanner(new File("data.in"));

String s;                        // 進行輸入的處理時的臨時變量
n = in.nextInt();                // 獲取結點個數
s = in.next(); root = s.charAt(0);    // 獲取根
for(int i = 0; i < n - 1; ++i) {
char u, v;
s = in.next(); u = s.charAt(0);    // 獲取邊,並在鄰接矩陣中做標記
s = in.next(); v = s.charAt(0);
G[u][v] = G[v][u] = true;
}
List path = new ArrayList();
dfs(root, '0', path);
for(int i = 0; i < ans.size(); ++i) {    // 輸出答案
for(Character c: ans.get(i))
System.out.print(c);
System.out.println();
}

in.close();
}

public static void main(String[] args) throws FileNotFoundException{
new Main().go();
}
}

友情链接: 91賽普網城固網易財網邁特網匯川網1127網科斯網234網牛牛網

123新聞網娛樂生活科技教育

Copyright © 2013-2022 123新聞網 版權所有