0

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

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

public BinaryTreeNode(Object theElement, BinaryTreeNode theleftChild, BinaryTreeNode therightChild)
{
    element = theElement;
    leftChild = theleftChild;
    rightChild = therightChild;
}

public BinaryTreeNode(Object theElement)
{
    element = theElement;
}

public BinaryTreeNode() {}

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

// tree for ( A - B ) / C
BinaryTreeNode b1 = new BinaryTreeNode("A");
BinaryTreeNode b2 = new BinaryTreeNode("-");
BinaryTreeNode b3 = new BinaryTreeNode("B");
BinaryTreeNode b4 = new BinaryTreeNode("/");
BinaryTreeNode b5 = new BinaryTreeNode("C");
BinaryTreeNode bAB = new BinaryTreeNode(b2, b1, b3);
BinaryTreeNode bRoot = new BinaryTreeNode(b4, bAB, b5);
q.put(bRoot);

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

// tree for ( A - B ) / C
BinaryTreeNode b1 = new BinaryTreeNode("A");
BinaryTreeNode b2 = new BinaryTreeNode("B");
BinaryTreeNode b3 = new BinaryTreeNode("C");
BinaryTreeNode bRoot= new BinaryTreeNode("/", new BinaryTreeNode("-", b1, b2), b3);
q.put(bRoot);

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

4

6 に答える 6

3

2 つ目は「要素」の値として文字列を使用し、最初のものは BinaryTreeNode を使用します。「要素」の値が何であるかはわかりませんが、私の直感では、それは文字列である必要があります。これらのスニペットの唯一の違いです。

于 2009-11-19T23:31:47.733 に答える
2

それは混合バッグです;-)

2 番目のアプローチは、その出力に関して優れているように見えます。BinaryTreeNode の要素メンバーに
一貫して文字列を配置します。最初のアプローチでは、文字列と BinaryTreeNode インスタンスを組み合わせて使用​​します。

少なくとも、最初のスニペットを次のように書き直すことをお勧めします。

BinaryTreeNode b1 = new BinaryTreeNode("A");
BinaryTreeNode b3 = new BinaryTreeNode("B");
BinaryTreeNode b5 = new BinaryTreeNode("C");
BinaryTreeNode bAB = new BinaryTreeNode("-", b1, b3);
BinaryTreeNode bRoot = new BinaryTreeNode("/", bAB, b5);

2 番目の方法のもう 1 つの利点は、中間ノード(上記の bAB など) 用に追加のストレージを必要としないことです。これらの変数は参照型であるため、これは大きな問題ではありません。したがって、ストレージはほとんど必要なく、非常に効率的にコピーできます。2 番目の方法は、基本的にこれらのノードを in-situで構築するものであり、これはより効率的であると考えられます。（これは、この方法ですべての中間ノードを作成しようとすると、ツリーの深さが大きくなるにつれてすぐに機能しなくなるということです...）

興味深い一時停止、教育の瞬間があります;-)、時期尚早の最適化の誘惑について熟考します...

一方...最初の方法の1つの利点（セマンティックの変更が示されている）は、コードのより定期的な支出が増えることであり、ツリー構造の問題をより簡単に見つけるのに役立つ場合があります。
[編集：]考えられるハイブリッド ソリューションは、ソリューション #2 を使用して、ツリーの下部の 2 つのレイヤー (リーフ ノードとその上のレイヤー) を定義することです。つまり、行ごとに [最大] 3 つのノードを定義します。これの利点は、ツリーを定義するために必要な行数をほぼ半分にすることです (ツリーが成長するにつれて要因になる可能性があります)。また、最も多くのノード (リーフ -ノード）。さて...そのような構造/構文は、ツリーが追加された場合/場合に柔軟性が大幅に低下し、バランスを再調整する必要があります(おそらくこれが、インストラクターがツリーをハードコーディングして、生徒は、ツリーのバランスを再調整するために必要な操作の種類を「感じる」ことができます。)

これは言った、

どちらのアプローチも、スーパーカリフラジリスティックなエクスピアリドーシャスではありません。

少しクールなアプローチは、テキスト ファイルからツリーを読み取ることです。そのテキストの構文は、アプローチ＃1のレイアウトで明らかな行ごとに1つの名前付きノードをかなり厳密に反映している可能性があるため、それ自体は大きな利益にはならないと主張するかもしれません...いくつかのキーストローク。ただし、このようなソリューションの利点は、これが「データ」を「コード」から切り離すことを考えると、より明らかになります。 異なるツリーで作業するためにプログラムを再コンパイルする (またはこのバイナリの多数の異なるバージョンを用意する) 必要はありません。プログラムに別のテキスト ファイルを指定するだけです。また、このデカップリングは、ノード クラスの名前が変更されたなど、コードがリファクタリングされた場合に興味深いものになります。極端な場合、このコードとデータの独立性により、完全に異なるツリー ライブラリの使用が可能になります。必要な唯一の変更は、ノードの論理構造がファイルから解析された後に、ノードの構築とアセンブリをマップするロジックを少し生成することです。

于 2009-11-20T00:15:55.043 に答える
1

左側は最初のコードが生成する構造で、2 番目のコードは右側にあります。

          * -- "/"            "/"
         / \                  / \
        /   \                /   \
"-" -- *    "C"            "-"   "C"
      / \                  / \
     /   \                /   \
   "A"   "B"            "A"   "B"

プリンの証は食べてみて：こんな木をどう加工したいか？2 番目のケースでは、ルート ノードから開始し、その要素を読み取り、それが演算子の場合は、必要に応じて子を再帰的に読み取り、それらの値に対して演算子の関数を実行します。ただし、最初のケースでは、要素を読み取らず、最初にその型を確認します。別のツリー ノードへの参照である場合、それは演算子であることを意味するため、そのノードの値を演算子として取得します。「これはツリー ノードなので、演算子です」というこの結論は、怪しげに聞こえるはずです。タイプでディパッチを行いたい場合は、タイプに意味がある必要があるため、演算子は「operator」タイプにする必要があります。ただし、この演習では、文字列値のディスパッチで十分だと思います。結論は：

于 2009-11-20T14:25:57.623 に答える
0

各ノードの要素は BinaryTreeNode 自体である必要はありません。任意のオブジェクトで十分です。

于 2009-11-19T23:32:12.040 に答える
0

2番目のものは、1つのことについてよりよく読みます。逆ポーランド記法に精通している場合、2 番目の表記は RPN 計算機に入力するように読みます。これはクラスの機能を検証するための単なるテストであることを考えると、ここでは効率が実際に問題になるべきではないと思います。

于 2009-11-19T23:36:10.460 に答える
0

私は友人であり、この状況では数式を表すために要素を使用していたため、要素をノードとして使用するのは不適切であるというのが私の推論でした。ノードの要素として参照される別のツリーのルート ノードを使用できることは理解していますが、この例ではまったく不適切です。

最初の方法で見たエラーは、変数 bAB (つまり、bAB 内のノード b1、b2、および b3) を使用したときにサブツリー全体を保存しようとしたことでした。数式を表す。

于 2009-11-20T11:22:21.567 に答える