1

私のクラスは現在、データ構造ユニットの一部としてバイナリツリーを実行しています。Nodeクラスのコンストラクターには3つのパラメーター（値、左ノード、右ノード）が必要であることを理解しています。要件の一部として、Treeクラスが必要です。ツリークラスの目的は何ですか？ノードのセット全体を管理するためですか？特定のノードを挿入、削除、検索するために必要な機能が含まれているだけですか？

前もって感謝します。

私のノードクラス：

class Node {
protected int data;
protected leftNode;
protected rightNode;

Node (int data, Node leftNode, Node rightNode){
this.data = data;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
}
4

5 に答える 5

2

はい、内部構造に関連するすべての動作とアルゴリズムをカプセル化することにより、ツリーの機能インターフェイスを提供することになっています。

なぜこれが良いのですか？ いくつかの機能を提供するだけで、スタンドアロンの方法で機能するものを定義するため、ノードやアルゴリズムなどを気にせずに、誰もがツリークラスを使用できるようになります。

理想的には、クラスはパラメトリックである必要がTree<T>あります。そうすれば、たとえば、一般的なメソッドを使用できるようになります。

T getRoot()

基本的には、それを投影して、次のことができるようにする必要があります

  • 値を挿入
  • 値を削除する
  • 検索値
  • ツリー全体をご覧ください
  • なんでもいい
于 2012-04-09T22:11:00.640 に答える
1

データ構造の目的は、関連する値のコレクションを保持し、それらを意味のある方法で操作する方法を提供することです。

ツリーは特別な種類のデータ構造です。これは、階層的なデータ、つまり自然な親子関係を持つデータに適しています。二分木には、親ノードごとに最大2つの子があります。

特筆に値するツリーのもう1つの機能は、自己相似であるという事実です。ツリー内のすべてのノードは、それ自体がサブツリーのルートです。再帰はこの事実を利用します。

はい、それらは最初から良い方法です。java.util.Map役に立つかもしれない他の人のためにインターフェースを見たいと思うかもしれません。

于 2012-04-09T22:10:50.843 に答える
1

私が見ているように、クラスTreeは、ツリーのルートノードへの参照、および各ノードに属するメソッドではなく、ツリー全体で動作するメソッドと属性への参照を保持する必要があります。getLeft()getValue()

たとえばsize、クラスで属性を定義するTreeと、ツリーにノードを追加または削除するメソッド（これもこのクラスに含まれます）が、サイズを最新の状態に保つ役割を果たします。

于 2012-04-09T22:12:48.550 に答える
0

ご想像のとおり、この仮定には少し欠陥があります。定義したNodeタイプは、バイナリツリーの完全に細かいインスタンスです。

ジャックは、、挿入、削除などのTree操作を提供するために、ノードのセット全体の周りにタイプを設定したいと述べています。getRootもちろんこれは悪い考えではありませんが、決して必須ではありません。これらの操作の多くはNodeそれ自体で実行される可能性があり、必ずしもこれらの操作のすべてを実行する必要はありません。たとえば、getRoot操作を行うことには賛成と反対の両方の引数があります。これに対する反論は、ある時点でサブツリーのみが必要なアルゴリズムがある場合Tree、ルートを保持するオブジェクトが、アルゴリズムで不要になったsのNodeガベージコレクションを防ぐというものです。Node

しかし、より一般的には、ここで尋ねる必要がある本当の質問はこれです：あなたが扱っているもののどれがインターフェースであり、どれが実装ですか？これは、バイナリツリーを呼び出し元へのインターフェイスとして公開する場合と、ある種の有限マップをインターフェイスとして提供する場合の1つであり、バイナリツリーは単なる実装の詳細であるためです。null前者の場合、クライアントは、ツリーが値とブランチのいずれかであるか、またはであるかを「認識」し、Nodeたとえば、ツリーの構造を再帰することができます。後者の場合、クライアントが「知っている」のは、クラスが何らかの形式のput、getおよびをサポートしていることだけです。delete操作が、これが検索ツリーとして保存されているという事実に依存することは許可されていません。後者の場合の多くの変形では、実際にTree、クライアントからノードを隠すためのフロントエンドとしてタイプを使用します。（たとえば、Javaの組み込みjava.util.TreeMapクラスがこれを行います。）

したがって、最短の答えは、実際には、状況によって異なります。少し長い答えは、バイナリツリーの実装とそのユーザーの間の契約が何であるかに依存するということです。呼び出し元がツリーについてどのようなことを想定できるか、バイナリツリーの詳細は、作成者が将来変更できると期待することなどです。

于 2012-04-09T22:27:00.010 に答える
0

「ノードのセット全体を管理するためですか？」

はい。

「特定のノードを挿入、削除、検索するために必要な機能が含まれているだけですか？」

基本的にはそうです。そのため、少なくともルートノードへの参照が含まれている必要があります。

于 2012-04-09T22:10:29.557 に答える