アルゴリズム 木構造のパス表示

質問

下記のような入力データを出力データのように出力させたいのですが。
アルゴリズムを教えて頂けませんでしょうか？

言語は特定の言語でなくても構いません。
日本語で雰囲気が解ればそれに越したことはありません。

もし、特定の言語で記述頂ける場合、
(言語依存の特殊な表記方法を避けて頂けるとたすかります(知識が浅いため)。

但し言語依存の関数等は引数と戻り値の説明を入れていただけたら可です。
(勘違いしそうなので)

トリッキーな書き方を避けべたな平書きでお決まりの処理部分は関数
で省略みたいな感じだとありがたいです(見やすいため)。

※元データ生成データ共に、見た目のままのテキストデータです。
//入力データ例(階層等やパターンは決まって無いことが前提)
親
├子1
├子2
│├孫1
│└孫2
├子3
│　└孫3
│　　 ├ひ孫1
│　 └ひ孫2
└子4
//ここまで

//出力データ
親\子1
親\子2
親\子2\孫1
親\子2\孫2
親\子3
親\子3\孫3
親\子3\孫3ひ孫1
親\子3\孫3ひ孫2
親\子4

回答No.4

mtaka2 · ベストアンサー

同じようなプログラムを組んだことがあります。
一見複雑そうに見えますが、分かってしまえば非常に簡単です。

階層構造を保持する配列を用意しておきます。(以下、path[x]とします。)
各行を読み込んだ時の、行頭の階層を表す「├、│、└、スペース」の数をn、階層名をsとすると
　　　　・path[n] にsを代入
　　　　・path[0]～path[n]を、間に\を挟んで出力
　します。

以上です。

例えば、質問者さんの例だと、
n=0 s="親"　　　→path[0]に"親"を代入、path[0]を出力→"親"
n=1 s="子1" 　　→path[1]に"子1"を代入、path[0]～path[1]を出力→"親\子1"
n=1 s="子2" 　　→path[1]に"子2"を代入、path[0]～path[1]を出力→"親\子2"
n=2 s="孫1" 　　→path[2]に"孫1"を代入、path[0]～path[2]を出力→"親\子2\孫1"
n=2 s="孫2" 　　→path[2]に"孫2"を代入、path[0]～path[2]を出力→"親\子2\孫2"
n=1 s="子3" 　　→path[1]に"子3"を代入、path[0]～path[1]を出力→"親\子3"
n=2 s="孫3" 　　→path[2]に"孫3"を代入、path[0]～path[2]を出力→"親\子3\孫3"
n=3 s="ひ孫1" 　→path[3]に"ひ孫1"を代入、path[0]～path[3]を出力→"親\子3\孫3\ひ孫1"
n=3 s="ひ孫2" 　→path[3]に"ひ孫2"を代入、path[0]～path[3]を出力→"親\子3\孫3\ひ孫2"
n=1 s="子4" 　　→path[1]に"子4"を代入、path[0]～path[1]を出力→"親\子4"

となります。

ただし、以上の記述は行頭の「├、│、└、スペースの数」に間違いがない、というのが前提です。

実際には、質問者さんの例では、孫3・ひ孫1のスペースの数がおかしいので、そのままでは使えません。
これが「質問するときの記入ミス」なら、上述のアルゴリズムで問題ありませんが、
元のデータもその通りだったのだとすると、かなり難しくなります。

お礼

教えていただいた方法をヒントに
日本語プログラミングで作成してみました。
出力にあたり不要文字列の削除やデータの若干の整形が必要ですが、
解りやすくするために問題の主要部分だけ抽出してます。

//ここから

//反復はforeachのこと
データを反復
　N=対象の階層数　//対象とは繰り返しのイテレータのこと
　S=対象
　P[N]=対象
Pを反復
　　結果に(対象&"\")を配列追加
結果を表示。
//ここまで

こんな単純なアルゴリズムで書けるなんて目からうろこです。
ありがとうございました。

補足

書き忘れました。
対象の階層数は
該当記号の個数をカウントする関数です。

回答No.5

kmee

すみません。良く読んだら、入力ファイルだったんですね。
「内部で木構造になっているデータ」の出力と勘違いしてました。

単に変換するなら、#4さんの方法がよいと思います。

注意点は、「階層が不明」「文字列の保存」の2点です。
言語によっては、伸び縮みする配列を扱いずらいものがあります(C言語とか)

あとは
> パターンは決まって無い
というのが不明です。一定の約束事がなければ、入力データの解析が困難です。
すでに指摘があるように「ひ孫2」が他の規則から逸脱していますが、これも「孫3」の子である、と判断させようとすれば、例外的に判定する必要があります。

お礼

色々と説明不足ですみません。
参考になりました。
結果的にはNo.4さんの回答を採用させていただきました。
解決ありがとうございました。

補足

一部、誤りがありがみつかりましたので修正です。
//ここから
データを反復
　N=対象の階層数
　S=対象
　P[N]=対象
　(N+1)回　//修正箇所
　　結果に(P[回数-1]&"\")を配列追加//修正箇所
//ここまで
以上解決とさせていただきます。

回答No.3

dscripty

[ANo.2] さんの回答を具体的にかくと、こんなかんじ。

人のデータ構造 [
- 名前
- 子供たち(人のリスト)
- 親(人へのリンク)
- 先祖の名前リストの最後に本人の名前を加えて返す関数() {
　親がいないとき
　→ 「本人の名前」をかえす。
　親がいるとき
　→ 「[親(人へのリンク)].先祖の名前リストの最後に本人の名前を加えて返す関数() + "\" + 名前」をかえす。
}
]

(1) 処理対象を「親」に設定。

(2) 処理対象に対して以下を実行。
「先祖の名前リストの最後に本人の名前を加えて返す関数()」を出力。
「処理対象の子供たち(人のリスト)」の中の人を順番に処理対象にして (2) を実行。子供たちいないときはなにもしない。

おわり。

お礼

教えていただいた方法をヒントに
日本語プログラミングで作成してみました。
出力にあたり不要文字列の削除やデータの若干の整形が必要ですが、
解りやすくするために問題の主要部分だけ抽出してます。

//ここから

//反復はforeachのこと
データを反復
　N=対象の階層数　//対象とは繰り返しのイテレータのこと
　S=対象
　P[N]=対象
Pを反復
　　結果に(対象&"\")を配列追加
結果を表示。
//ここまで

こんな単純なアルゴリズムで書けるなんて目からうろこです。
ありがとうございました。

補足

インデントの記述ミスがあり修正です。
//ここから
//反復はforeachのこと
データを反復
　N=対象の階層数　//対象とは繰り返しのイテレータのこと
　S=対象
　P[N]=対象
　Pを反復　//インデントが崩れてました
　　結果に(対象&"\")を配列追加
結果を表示。
//ここまで

回答No.2

kmee

再帰呼び出しが可能な言語なら、再帰呼び出しを使うのが常套手段でしょう。
自分から下の木の表示すべてに
「ルート\1階層目\2階層目...\自分の上」
を追加すればいいわけです。

あとは、言語や目的に合せて
・「自分の上」までの情報を下に伝えて、「自分」で出力
にするか
・「一覧表」を返して、出力は呼び出し側にまかせる
にするか

お礼

回答ありがとうございます。
以前、自身でも再帰処理で同じような処理を書いたのですが・・・。
思い出せませんでした。

今回は、時間が無かったので
No4さんの方法を採用させていただくことにしました。

再帰処理は慣れておくと便利なので、また時間があるときにでも
勉強のために再帰処理で書いてみたいと思います。

回答No.1

hitomura

以下の2点の補足お願いします。

> │　└孫3
> │　　 ├ひ孫1
> │　 └ひ孫2
の部分ですが、
(1) 半角空白が消えてしまうため全角空白への置き換えを行っているのか、それとも最初から全角空白なのかお教えください。
(2) ひ孫1とひ孫2とで空白の個数が違いますが、それで間違いありませんか。

お礼

編集の際に使ったスペースのミス問題です。
スペースはこの際問題でないので外してみました。
親
├子1
├子2
│├孫1
│└孫2
├子3
│├孫3
│└孫4
└子4