c# - ツリーをゼロから実装する

Question

木をゼロから実装して、木について学ぼうとしています。この場合、C# Java または C++ で実行したいと思います。(組み込みメソッドを使用しない場合)

したがって、各ノードにはキャラクターが格納され、ノードごとに最大 26 個のノードが存在します。

各ノードへのポインターを格納するには、どのデータ構造を使用しますか?

基本的に、基数ツリーをゼロから実装しようとしています。

ありがとう、

score 3 · Accepted Answer

各ノードへのポインターを格納するには、どのデータ構造を使用しますか?

ノード。各ノードには、ツリー内の (最大で) 26 個の他のノードへの参照が必要です。ノード内では、それらを配列、LinkedList、ArrayList、または考えられるその他のほぼすべてのコレクションに格納できます。

score 1 · Accepted Answer

実際にスペースよりも速度に関心があり、各ノードが正確に 1 つの文字を表す場合 (最大 26 であることを意味します)、26 スロットの単純な配列を使用し、それぞれが「ノード」を参照します (ノードは配列を含むオブジェクト)。

固定サイズの配列の良いところは、検索がはるかに高速になることです。すでに小文字であることが保証されている char "c" を検索する場合、検索は次のように簡単です。

nextNode=nodes[c-'a'];

文字列の再帰的なルックアップは簡単です。

score 1 · Accepted Answer

素早い返信ありがとうございます。

はい、snogfish は正しいと言っていました。基本的に、26 個のノード (AZ) を持つツリー + bool isTerminator です。

各ノードにはこれらの値があり、それらは相互にリンクされています。

私はまだポインターを深く学んでいないので、今日は C# で安全でないコードを使用してこれをゼロから実装しようとしていますが、無駄です。

したがって、誰かが内部ツリークラスを使用して C# で始めるためのコードを提供してくれるとありがたいです。開始できたら、アルゴリズムを他の言語に移植し、ポインターを使用するように変更するだけです。

どうもありがとう、マイケル

score 1 · Accepted Answer

これは私が最近見つけたもので、ツリーの悪い API ではありません - グラフが必要でしたが、保持しているデータのデータ構造を分離するためにどのように設定されているかを確認するのに便利でした。ツリー内を移動するなど。

https://jsfcompounds.dev.java.net/treeutils/site/apidocs/com/truchsess/util/package-summary.html

score 1 · Accepted Answer

あなたが説明しているのは基数ツリーではありません...基数ツリーでは、ノードに複数の文字を含めることができ、子ノードの数に上限はありません。

あなたが説明していることは、アルファベットによってより制限されているように聞こえます...各ノードはazにすることができ、その後に別の文字、azなどを続けることができます.次のノードポインタを保持するために選択したデータ構造にとって、区別は重要です.

あなたが説明するツリーでは、使用する最も簡単な構造はポインターの単純な配列かもしれません...あなたがする必要があるのは、文字（「A」など）をそのASCII値（「65」）に変換し、開始を減算することだけですオフセット (65) を使用して、必要な「次のノード」を決定します。より多くのスペースを占有しますが、挿入とトラバーサルは非常に高速です。

真の基数ツリーでは、3、4、78、または 0 個の子ノードを持つことができ、「次のノード」リストには並べ替え、挿入、および削除のオーバーヘッドがあります。はるかに遅い。

Java について話すことはできませんが、C# でカスタム基数ツリーを実装する場合は、組み込みの .NET コレクションの 1 つを使用します。独自のソート済みリストを作成しても、ツリーの概念を理解するのにはあまり役に立ちません。また、.NET コレクションの組み込みの最適化に勝るものはありません。次に、コードは単純です。次のノードを検索します。存在する場合は、それをつかんで行ってください。そうでない場合は、次のノードコレクションに追加します。

使用するコレクションは、ツリーを介して正確に何を実装しているかによって異なります...すべてのタイプのツリーには、挿入時間、ルックアップ時間などのトレードオフが含まれます。選択は、ツリーではなく、アプリケーションにとって最も重要なものに依存します.

わかる？

score 0 · Accepted Answer

この Simeon Pilgrim ブログ、「Code Camp Puzzle Reviewed」をチェックしてください。ソリューションの 1 つは C# で Radix を使用しており、ソリューションをダウンロードできます。

score 0 · Accepted Answer

それは本当に問題ではありません。リンクされたリスト、配列 (ただし、これは固定サイズになります)、または言語の標準ライブラリの List 型を使用できます。

リスト/配列を使用することは、ツリーをトラバースするためにインデックスの簿記を行うことを意味するため、親の子への参照を保持するだけで使用するのが最も簡単な場合があります。

c# - ツリーをゼロから実装する

7 に答える 7

Related

Reference