問題タブ [tree-traversal]

データ構造で与えられた課題では、与えられたコードがテスト クラスのバイナリ ツリーを正しく横断したかどうかを判断するために、テスト クラスを作成する必要がありました。

これらは、私たちに与えられた BinaryTreeNode クラスの 3 つのコンストラクターです。

指定されたツリーの 1 つを作成するために、テスト クラスで次のコードをすばやく作成しました。

しかし、私の友人は私がこのようにすることを提案しました：

しかし、彼はなぜこの方法が優れているのかを説明するのに苦労しました。これがより効率的である理由を誰か説明できますか? 例からさらにコードが必要な場合は、お問い合わせください。

まず、この質問はこれの複製ではなく、それに基づいています。

その質問の木を例にとると、

そのように印刷するには、プログラムをどのように変更しますか。

一般というより

私は基本的にそれを行うための最も効率的な方法についての直感を探しています.結果をリストに追加してからループする方法があります. より効率的な方法は、ポップされたときに各レベルの最後の要素を格納し、後で新しい行を出力することです。

アイデア？

ディレクトリ構造を再帰的にトラバースするとき、ディレクトリよりも多くのファイルがある場合に使用する最も効率的なアルゴリズムは何ですか? 深さ優先トラバーサルを使用すると、特定のディレクトリに多くのファイルがあると時間がかかるように見えることに気付きました。この場合、幅優先トラバーサルはより効率的に機能しますか? 現時点では 2 つのアルゴリズムの概要を説明する方法がないため、ご意見をお待ちしております。

編集: alphazero のコメントに応えて、私は Linux マシンで PHP を使用しています。

C でバイナリ ツリーをトラバースしようとしています。ツリーには AST ノード (コンパイラの抽象構文ツリー ノード) が含まれています。ASTnode は、指定されたノードのタイプを指定する nodetype を予約します (つまり、INT OP または CHAR と TYPE は他のタイプに関係する必要はありません)。他のメンバーは左右のポインターであり、最後に保存します。

トラバースのコードは次のとおりです。

また、AST では定数値に余分な値が含まれないため、CONSTANT ノードに左または右の値を割り当てることはできません。

更新しました：

問題は私のメインコールにあります:

ノード 5 (!! でマークされている) を削除すると、コードは非常にうまく機能します。そうしないと、セグメンテーション エラーが発生します。

で動作する関数makenode:

階層/ツリー構造でインタラクション デザインを行うためのインスピレーションを探しています。(多数のサブプロダクトを含むプロダクト、サブプロダクトの選択に適用されるルール)。

サブノードとその親ノードの間に目に見える接続があるツリーが必要です。また、それらを選択するためにどのルールが適用されるかを視覚化したいと考えています。

典型的なルール:

• 必須: 1 つのサブ製品から 1 つだけ選択してください
• オプション: 複数のサブプロダクトから 0 個以上を選択します
• 相互排他的: 複数のサブプロダクトから 1 つだけを選択します

理解していただければ幸いです。

この分野のインスピレーションを探しています。提案、例、ヒントは大歓迎です

私はこれに似た配列を持っています：

ただし、各アイテムを関連する親配列内の「子」配列に再帰的に配置する関数が必要です。したがって、次のようになります。

それが理にかなっていることを願っています！

再帰を使用せずにプレオーダートラバーサルを理解することはできますが、インオーダートラバーサルに苦労しています。おそらく、再帰の内部動作を理解していないために、私はそれを理解していないようです。

これは私がこれまでに試したことです：

内側のwhileループは正しく感じられません。また、一部の要素は2回印刷されています。そのノードが以前に出力されたかどうかを確認することでこれを解決できるかもしれませんが、これには別の変数が必要です。どこが間違っているのですか？

注文後のトラバーサルは試していませんが、似ていると思います。そこでも同じ概念上の障害に直面します。

御時間ありがとうございます！

LifoPS：との定義Node：

二分木の単一レベルでノードを印刷（訪問）する必要があります。
これがどのように行われるかはわかりませんが、一般的なアルゴリズムについてはあまり熟練していません。
幅優先探索では、キューを使用し、ルートノードをキューに入れることから始めて、ルートノードをデキューして子をエンキューし、最初にエンキューされた子をキューから外して、子をエンキューすることを知っています。 on ...
そして私の理解では、バイナリツリーが作成されたときに各ノードにレベルを割り当ててから、幅優先探索を実行しているときにレベルを確認しない限り、あるレベルがいつ終了し、別のレベルがいつ開始するかを正確に知ることは不可能です。 。

このようなもの（コードはPHPですが、これはPHP関連の質問ではありません。これは一般的なアルゴリズム関連の質問です。これは、各ノードが追加されたときにノードのレベルを格納するバイナリツリーにノードを追加する関数の一部です。 ）：：

だから私の質問は：

これは、バイナリツリーの単一レベルでノードを印刷する唯一の方法ですか？
別の方法はありますか？
ツリーを作成するときにレベルを保存せずに別の方法はありますか？

私は反復アルゴリズムを実装しました。このアルゴリズムでは、各反復で順序ツリーのトラバーサル (下向きの累積と呼ばれることもあります) が行われ、その後に順序ツリーのトラバーサル (上向きの累積) が続きます。各ノードへの訪問ごとに、次の訪問に使用するための情報を計算して保存する必要があります (後続のポストオーダー トラバーサルまたは後続の反復のいずれかで)。

事前注文トラバーサル中、各ノードは、それとルートの間のすべてのノードがすでに処理されている限り、個別に処理できます。処理後、各ノードはタプル (具体的には 2 つの float) をそれぞれの子に渡す必要があります。ポストオーダー トラバーサルでは、すべてのサブツリー (存在する場合) が既に処理されている限り、各ノードを個別に処理できます。処理後、各ノードは単一のフロートをその親に渡す必要があります。

ツリーの構造は静的で、アルゴリズム中は変更されません。ただし、下向きのトラバーサルの過程で、渡される 2 つの float が両方とも 0 になった場合、このノードの下のサブツリー全体を処理する必要はなく、このノードの上向きのトラバーサルを開始できます。(後続の反復で渡された float がこのノードで非ゼロになる可能性があり、トラバーサルが再開されるため、サブツリーを保持する必要があります)。

各ノードでの計算の強度は、ツリー全体で同じです。各ノードでの計算は簡単です。ノードでの子の数と同じ長さの数値のリストで、いくつかの合計と乗算/除算を行うだけです。

処理中のツリーはバランスが取れていません。通常のノードには 2 つのリーフと 0 ～ 6 個の追加の子ノードがあります。したがって、単純にツリーを比較的バランスの取れたサブツリーのセットに分割することは (私には) 自明ではありません。さらに、ツリーは使用可能なすべての RAM を消費するように設計されています。処理できるツリーが大きいほど、優れています。

私のシリアル実装は、私の小さなテスト ツリーだけで毎秒 1000 回の反復を達成しています。「本物の」木では、1桁（またはそれ以上？）遅くなる可能性があると思います。アルゴリズムが許容できる結果に到達するには、少なくとも 1 億回 (場合によっては最大 10 億回) の反復が必要であることを考えると、アルゴリズムを並列化して、複数のコアを活用したいと考えています。並列プログラミングの経験はありません。

アルゴリズムの性質を考慮した並列化の推奨パターンは何ですか?

このライブラリを使用して、ツリー構造に関する情報を保持しています。

http://www.datasoftsolutions.net/tree_container_library/overview.php

これが私のC++コードの簡略化されたバージョンです:

ツリーはこんな感じ

Node(6) がルートにつながるすべてのノード、つまり6,5,3,0をトラバースする関数を作成しようとしています。これは C++ での私の最初のプロジェクトであり、ポインターを理解するのに苦労しています。おそらくC++の数行ですが、これを数時間実行しようとしましたが、成功しませんでした。どんな助けでも大歓迎です。

このようなものは機能しますが、4 だけでなく多くのレベルで機能する必要があります。