Java、二分木のリスト化（再帰）

Javaでのプログラミング課題です。
二分木のrootを除いた左側のSub-Tree（または右側のSub-tree）を因数として関数に渡し、再帰法を使って、そのSub-Treeの要素を階層ごとにリスト化したものを戻り値として返したいです。
（一つの大きなリストの要素として、同じ階層の要素がまとめられているリスト）

例として、

このような二分木の場合、
function(root.left) => [2, [4, 5]] 　　左のSub-Treeを因数
function(root.right) => [3, [6, 7], [8]]　　　右のSub-Treeを因数
というような戻り値が帰ってくる関数を作りたいです。

＊ただし制限として、
１）因数はroot.leftのようにNodeしか渡すことができません。初期化した空のリストを因数として渡すやり方は思いついたのですが、先生にそれではだめだと言われました。
関数の中でリストを作らなければならないみたいです？
２）再帰を使うこと
と決められています。

しばらく考え、いろいろ調べてみたのですが思いつきません。
ご教示いただけますと幸いです。よろしくお願いします。

jimbe

2021/10/17 04:20

> しばらく考え、いろいろ調べてみたその「考え、調べてみた」結果をご提示ください。(良くあるアルゴリズムと思いますからネットにも色々情報はあるはずです。) 「初期化した空のリストを因数(引数?)として渡すやり方は思いついた」(因数→引数?)のでしたら、少なくともそのコードはご提示頂いたほうが良いかと思います。 > 関数の中でリストを作らなければならないみたいです？未確認ならば先生に問い合わせて確認しては如何でしょう。なお、課題はご自身でが大前提です。「聞くは一時の恥、聞かぬは一生の恥」教わる為にお金を払っているはずですから、分かるまで先生に聞くべきと思います。

kazuma-s

2021/10/24 19:16

> function(root.right) => [3, [6, 7], [8]]　　　右のSub-Treeを因数というような戻り値が帰ってくる関数を作りたいです。 8 が 7 の左の子の場合、どんなリストが返ってくるのですか？ 8 が 6 の左の子の場合、どんなリストが返ってくるのですか？ 8 が 6 の右の子の場合、どんなリストが返ってくるのですか？

行動規範の内容に同意します

回答1件

再帰で空のリストを返す

初期化した空のリストを因数として渡すやり方は思いついたのですが、先生にそれではだめだと言われました。

再帰処理はできていると思います。次のように、Nodeがnullだったら空リストを返すようにしてみたら。

Java
1static リスト 展開(Node source) {
2
3  if (source == null) return 空リスト
4
5  リスト result = 併合処理( 展開(左Node),  展開(右Node))
6
7  resultの先頭にsourceを追加
8  return result;
9
10}

併合処理も再帰で行うなら

併合処理が難しいと思うなら再帰を使ってみます。アキュムレータリストを引数に追加します。アキュムレータリスト引数は空リストを渡します。

Java
1static リスト 併合処理( 左リスト,  右リスト, アキュムレータリスト) {
2
3  if ( 左リストが空 && 右リストが空) return アキュムレータリスト;
4
5   作業リスト = new 空リスト;
6   if ( ! 左リストが空) 左リストの先頭要素を削除; 内容を作業リストに追加;
7   if ( ! 右リストが空) 右リストの先頭要素を削除; 内容を作業リストに追加;
8
9  アキュムレータリスト.add(作業リスト);
10
11  return  併合処理( 左リスト,  右リスト, アキュムレータリスト) ;
12
13}

アキュムレータリストとは結果を格納する入れ物です。空リストは初期値を与えていることになります。引数に空リストを与えるのはNGでした。その場合は、最初の「展開」メソッドのように再帰の終了時に空リストを返します。両者の違いは次のようになります。

再帰メソッドの引数に空リスト（初期値）を与えると、リストの末尾にむかって要素を追加する
再帰メソッドの終了時に空リスト（初期値）を返すと、リストの先頭に向かって要素を追加する

つまり、初期値を最初に与えるか最後に与えるかによって、リストを左から作るか、右から作るかの違いが生じます。どちらの方法でも再帰処理できるようにしてください。

補足事項

最後にソースコードを追記します。Java 17(recordを使用)で動作します。併合処理を2種類の再帰で記述しました。

Java
1import java.util.ArrayList;
2import java.util.List;
3import java.util.stream.Stream;
4
5record Node(String name, Node left, Node right) {}
6
7@FunctionalInterface
8interface NodeUtils<U> {
9  List<List<U>> explode(Node source);
10}
11
12class NodeUtilsImpl1 implements NodeUtils<String> {
13  
14  @Override
15  public List<List<String>> explode(Node source) {
16    if (source == null) return new ArrayList<>();
17    List<List<String>> result = merge(explode(source.left()),explode(source.right()));
18    result.add(0,List.of(source.name())); // 先頭に追加
19    return result;
20  }
21  
22  private List<List<String>> merge(List<List<String>> left, List<List<String>> right) {
23    if (left.isEmpty() && right.isEmpty()) return new ArrayList<>();
24    List<String> temp = new ArrayList<>();
25    if (!left.isEmpty()) temp.addAll(left.remove(0));
26    if (!right.isEmpty()) temp.addAll(right.remove(0));
27    List<List<String>> result = merge(left,right);
28    result.add(0,temp); // 先頭に追加
29    return result;
30  }
31
32}
33
34class NodeUtilsImpl2 implements NodeUtils<String> {
35  
36  @Override
37  public List<List<String>> explode(Node source) {
38    if (source == null) return new ArrayList<>();
39    List<List<String>> result = merge(explode(source.left()), explode(source.right()), new ArrayList<>());
40    result.add(0,List.of(source.name())); // 先頭に追加
41    return result;
42  }
43  
44  private List<List<String>> merge(List<List<String>> left, List<List<String>> right, List<List<String>> acc) {
45    if (left.isEmpty() && right.isEmpty()) return acc;
46    List<String> temp = new ArrayList<>();
47    if (!left.isEmpty()) temp.addAll(left.remove(0));
48    if (!right.isEmpty()) temp.addAll(right.remove(0));
49    acc.add(temp); // 末尾に追加
50    return merge(left,right,acc);
51  }
52
53}
54
55public class q364810 {
56  
57  public static void main(String[] args) {
58    Stream.of(new NodeUtilsImpl1(), new NodeUtilsImpl2()).forEach(q364810::test);
59  }
60  
61  static void test(NodeUtils<String> utils) {
62    
63    System.out.println();
64  
65    Node n7 = new Node("7",null,new Node("8",null,null));
66    Node n2 = new Node("2",new Node("4",null,null),new Node("5",null,null));
67    Node n3 = new Node("3",new Node("6",null,null),n7);
68    Node n1 = new Node("1",n2,n3);
69
70    Stream.of(n1,n2,n3,n7).map(n -> utils.explode(n)).forEach(System.out::println);
71
72  }
73
74}