- ベストアンサー
木のなぞり順をかえるプログラムについて
質問です。 完全２分木Ｔで、Ｔの行きがけ順のリストを帰りがけ順のリストに変えるプログラムを作ろうと思うのですが。 この問題で、与えられるのは、行きがけ順のリストですよね？それから、帰りがけ順のリストを作るときには、やはり、一度行きがけ順から木を作り直してそれから帰りがけ順のプログラミングをするべきなのでしょうか？しかし、例えば、いきなり、nodeを整数型として、1,２，４，５，６，７，８，９，１０などと与えられても、どのような木かというのもわかりません。わかることといえば、最初の２を最後にまわすこと。 考え方を教えてください。お願いします。
- みんなの回答 （6）
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
#1です。 「葉以外のどの節点も２つの子を持つ木を考える」だけでは行きがけ順のリストなんてありえない。 時間があるなら問題の意図を出題者に問う。時間がなければ、問題の抱える矛盾の考察も回答の一部とし、なんらかの前提を自分で設定して進めるしかないでしょう。
その他の回答 (5)
- JaritenCat
- ベストアンサー率37% (122/322)
No.4です。 ＞よって、完全２分木で考えていいのですか？？ と僕に聞かれても困るので出題者に確認してください。。完全２分木を前提とするって解答に書けば問題ない気はしますが。 ちょっと気になっていたのが、「リスト」という言葉です。質問文からノードを単純に並べた１次元配列を想像していたのですが、もともとの問題文にリストという言葉が使われているのであれば、そうでない可能性があります。 プログラムで木を実装するときに、単方向リストとか双方向リストとか呼ばれるものをよく使うからです。大抵は構造体と構造体へのポインタで実現します。出題者の意図として木の設計まで含んでいるのかもしれませんね。
- JaritenCat
- ベストアンサー率37% (122/322)
No.2です。 僕が知っている完全２分木は、 完全２分木(complete binary tree)： どのレベルにおいても非終端ノードが完全に詰まっている２分木 です。これと違う完全２分木の定義を使われているのであれば、１次元配列のノードを復元するのは無理だと思います。ノードの接続情報も一緒にもらう必要がありますね。
#1です。 >とは考えられないでしょうか？この木での帰りがけ順と上の木の帰りがけ順のリストは明らかに異なります。 Tが完全２分木である以上、いびつな形になってはいけないので、要素数にしたがって、ただ１つの形になる事が前提となります。 そして与えられるのは、Tの行きがけ順リストなので、そのリストにも矛盾が無い事が前提となります。
お礼
ありがとうございます。 実は、問題文には、葉以外のどの節点も２つの子を持つ木を考えると書いてありました。そこで、始めは勝手に完全２分木だと解釈したのですが。どうもそうではなさそうなのです。 この場合、ただ行きがけ順のリストを与えられても、そこから帰りがけ順のリストを求めるのは不可能ですよね？やはり、完全２分木で考えるのが妥当なのでしょうか？
- JaritenCat
- ベストアンサー率37% (122/322)
質問の通り、行きがけ順リスト→完全２分木リスト→帰りがけ順リストに変換していくのが分かりやすいかと。ノード数が固定ならあらかじめ変換テーブルを作る手もありますね。 完全２分木を１次元配列(node[1],node[2]...)にする場合、 １ ２ ３ ４ ５６ ７ の順番で並べます。あるn番目のノードに対して左のノードは2n、右のノードは2n+1、親はn/2になります。
お礼
ありがとうございます。 質問です。考えていたのですが、木を与えられた行きがけ順のリストから復元するときに、いろいろな木ができてしまうことに気づきました。たとえば、上の木では他に １ ２ ３ ４ ５ ６ ７ というように。この場合はどう対処したらよいのでしょうか？ また、最初のリストが与えられるのですが、それは、どのようにして与えられるのでしょうか？いきなり、行きがけ順のリスト １，２，３，４，５，６，７のように与えられるのでしょうか？この場合、１は根ですが、それ以降は根からどのように枝分かれしているのかわからないと思うのですが。 よろしくお願いします。
例えばＡＢＣＤＥＦＧの７文字を完全２分木にする。 Ｄ Ｂ Ｆ Ａ Ｃ Ｅ Ｇ この場合、通りがけ順にＡ～Ｇが並ぶことになる。 与えられるリストは木を作るのに最適な行きがけ順になっている。 １ ２ ５ ３ ４ ６ ７ この順番から行きがけ順のリストはＤＢＡＣＦＥＧと与えられる事になる。 このリストを帰りがけ順に並び替えれば良い。 ７ ３ ６ １ ２ ４ ５ つまり、ＤＢＡＣＦＥＧと与えられたリストをＡＣＢＥＧＦＤというリストに並び替える。
お礼
ありがとうございます。ただ、おっしゃっていることがさっぱり理解できていません。 やはり与えられたリストから木を作り直し、それから帰りがけ順でリストをするということなのでしょうか？ また、もし上の木が １ ２ ７ ３ ４ ５ ６ とは考えられないでしょうか？この木での帰りがけ順と上の木の帰りがけ順のリストは明らかに異なります。
お礼
ありがとうございます。 そうなんです。問題文には、葉以外のどの節点も２つの子をもつ木を考えていました。よって、おそらく完全２分木だけをさしているのではないと思うのですが。 ただ、おっしゃられたように、この場合、行きがけ順のリストだけを与えられても、帰りがけ順のリストを求めるのは不可能ですよね？？よって、完全２分木で考えていいのですか？？