質問です。
完全2分木Tで、Tの行きがけ順のリストを帰りがけ順のリストに変えるプログラムを作ろうと思うのですが。
この問題で、与えられるのは、行きがけ順のリストですよね?それから、帰りがけ順のリストを作るときには、やはり、一度行きがけ順から木を作り直してそれから帰りがけ順のプログラミングをするべきなのでしょうか?しかし、例えば、いきなり、nodeを整数型として、1,2,4,5,6,7,8,9,10などと与えられても、どのような木かというのもわかりません。わかることといえば、最初の2を最後にまわすこと。
考え方を教えてください。お願いします。
No.5ベストアンサー
- 回答日時:
#1です。
「葉以外のどの節点も2つの子を持つ木を考える」だけでは行きがけ順のリストなんてありえない。
時間があるなら問題の意図を出題者に問う。時間がなければ、問題の抱える矛盾の考察も回答の一部とし、なんらかの前提を自分で設定して進めるしかないでしょう。
No.6
- 回答日時:
No.4です。
>よって、完全2分木で考えていいのですか??
と僕に聞かれても困るので出題者に確認してください。。完全2分木を前提とするって解答に書けば問題ない気はしますが。
ちょっと気になっていたのが、「リスト」という言葉です。質問文からノードを単純に並べた1次元配列を想像していたのですが、もともとの問題文にリストという言葉が使われているのであれば、そうでない可能性があります。
プログラムで木を実装するときに、単方向リストとか双方向リストとか呼ばれるものをよく使うからです。大抵は構造体と構造体へのポインタで実現します。出題者の意図として木の設計まで含んでいるのかもしれませんね。
No.4
- 回答日時:
No.2です。
僕が知っている完全2分木は、
完全2分木(complete binary tree):
どのレベルにおいても非終端ノードが完全に詰まっている2分木
です。これと違う完全2分木の定義を使われているのであれば、1次元配列のノードを復元するのは無理だと思います。ノードの接続情報も一緒にもらう必要がありますね。
ありがとうございます。
そうなんです。問題文には、葉以外のどの節点も2つの子をもつ木を考えていました。よって、おそらく完全2分木だけをさしているのではないと思うのですが。
ただ、おっしゃられたように、この場合、行きがけ順のリストだけを与えられても、帰りがけ順のリストを求めるのは不可能ですよね??よって、完全2分木で考えていいのですか??
No.3
- 回答日時:
#1です。
>とは考えられないでしょうか?この木での帰りがけ順と上の木の帰りがけ順のリストは明らかに異なります。
Tが完全2分木である以上、いびつな形になってはいけないので、要素数にしたがって、ただ1つの形になる事が前提となります。
そして与えられるのは、Tの行きがけ順リストなので、そのリストにも矛盾が無い事が前提となります。
ありがとうございます。
実は、問題文には、葉以外のどの節点も2つの子を持つ木を考えると書いてありました。そこで、始めは勝手に完全2分木だと解釈したのですが。どうもそうではなさそうなのです。
この場合、ただ行きがけ順のリストを与えられても、そこから帰りがけ順のリストを求めるのは不可能ですよね?やはり、完全2分木で考えるのが妥当なのでしょうか?
No.2
- 回答日時:
質問の通り、行きがけ順リスト→完全2分木リスト→帰りがけ順リストに変換していくのが分かりやすいかと。
ノード数が固定ならあらかじめ変換テーブルを作る手もありますね。完全2分木を1次元配列(node[1],node[2]...)にする場合、
1
2 3
4 56 7
の順番で並べます。あるn番目のノードに対して左のノードは2n、右のノードは2n+1、親はn/2になります。
ありがとうございます。
質問です。考えていたのですが、木を与えられた行きがけ順のリストから復元するときに、いろいろな木ができてしまうことに気づきました。たとえば、上の木では他に
1
2 3
4 5
6 7
というように。この場合はどう対処したらよいのでしょうか?
また、最初のリストが与えられるのですが、それは、どのようにして与えられるのでしょうか?いきなり、行きがけ順のリスト 1,2,3,4,5,6,7のように与えられるのでしょうか?この場合、1は根ですが、それ以降は根からどのように枝分かれしているのかわからないと思うのですが。
よろしくお願いします。
No.1
- 回答日時:
例えばABCDEFGの7文字を完全2分木にする。
D
B F
A C E G
この場合、通りがけ順にA~Gが並ぶことになる。
与えられるリストは木を作るのに最適な行きがけ順になっている。
1
2 5
3 4 6 7
この順番から行きがけ順のリストはDBACFEGと与えられる事になる。
このリストを帰りがけ順に並び替えれば良い。
7
3 6
1 2 4 5
つまり、DBACFEGと与えられたリストをACBEGFDというリストに並び替える。
ありがとうございます。ただ、おっしゃっていることがさっぱり理解できていません。
やはり与えられたリストから木を作り直し、それから帰りがけ順でリストをするということなのでしょうか?
また、もし上の木が
1
2 7
3 4
5 6
とは考えられないでしょうか?この木での帰りがけ順と上の木の帰りがけ順のリストは明らかに異なります。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- その他(プログラミング・Web制作) pythonにおける単方向リストの実装について 4 2022/07/13 12:34
- C言語・C++・C# C言語 3 2022/10/04 15:07
- その他(プログラミング・Web制作) どういうプログラムで組みますか?google colabでやってるんですけど、出来る方お願いします。 1 2022/07/17 18:41
- その他(趣味・アウトドア・車) アマチュア無線の「村」まで入った「市郡区番号リスト」を探しています 4 2022/08/27 07:07
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# pythonのファイルの並びでの読み込みとリストについて 4 2022/04/13 03:52
- その他(プログラミング・Web制作) どういうプログラムで組みますか?google colabでやってるんですけど、出来る方お願いします。 1 2022/07/06 09:28
- Excel(エクセル) エクセルについて教えてください。 2 2023/06/14 11:11
- 会社・職場 ADHDなどをお持ちの方に答えていただけたら参考になります。 職場の後輩であまりにも仕事ができない、 4 2023/07/20 19:52
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
昔Winnyってありましたけど、あ...
-
4色定理はなぜグラフ理論で証...
-
線形リストに挿入するプログラム
-
c言語 ノードの連結
-
C言語 TreeViewのノードをプロ...
-
2分探索木の高さを求めるプロ...
-
複数のマックPCによる数値計算...
-
東芝のDynabookなのですがアン...
-
Dreamweaver CS3 : シングルク...
-
XSLT 文字列を指定した回数分...
-
終了タグが認識されない?
-
エラーがでます。
-
ビデオハードウェアエラー Live...
-
DTDファイルをクラスパスから読...
-
スタイルシートについて
-
VBでXMLファイルを作ると xmlns...
-
XSLTでの正規表現判定
-
リンクを使って複数ページへCSS...
-
Dropboxの更新がiPhoneで通知さ...
-
XMLで要素が記述された順番に意...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
CPUの考え方を教えてください ...
-
昔Winnyってありましたけど、あ...
-
SNMP リンクダウンとノードダ...
-
ルート要素ノードが2個ある場合?
-
同じタグ名の項目取得
-
ノードとは
-
あるノードリストに、特定の名...
-
TreeView の初期表示について
-
ツリービューのノードをダブル...
-
コンテキストメニュークリック...
-
ノード数とは?
-
XML文書の指定した属性値を持つ...
-
複数のマックPCによる数値計算...
-
C#でtreeviewの指定ノードを選...
-
VB6.0ツリービューについて
-
TreeViewの再表示のちらつきを...
-
VB6.0でDOMを使用して...
-
vbsのDOMDocumentで要素のText...
-
TreeViewで複数ノードの選択は...
-
C# TreeView 効率良いノード追...
おすすめ情報