0

Representing Rooted Treesから引用した次の段落を理解するのに苦労しています。基本的に、ツリーを表す 2 つの方法を示します。G & T は私にはある程度明確ですが、もう 1 つはあまり明確ではなく、クラスの定義を示しています。

  • G&T オプション: 各ノードには、アイテム、親、子の 3 つの参照があります。子の単一参照は、リストを参照する必要があります (そのため、ノードは必要な数の子を持つことができます)。

  • 別のオプションは、兄弟を直接リンクさせることです。例えば

    class SibTreeNode {
 Object item;
 SibTreeNode parent;
 SibTreeNode firstChild; // Left-most child.
 SibTreeNode nextSibling;
}

public class SibTree {
  SibTreeNode root;
  int size; // Number of nodes in the tree.
}

ビデオの著者は、(約 18 分で) 2 番目の方法の方が必要なメモリが少ないと主張しています。誰かがクラス定義を理解するのを手伝ってくれますか?最初の方法と比較して、これがどのように少ないメモリを必要としますか?

4

1 に答える 1

1

2番目のオプションは、単純に煩わしい単一リンクリストです。リストノードからノードのコンテンツへのポインタが必要ないため、煩わしい単一リンクリストはメモリをあまり消費しません。

外部リストを使用してG＆Tオプションのレイアウトを確認します。

class ListNode {
    SibTreeNode* object;
    ListNode* nextElement;
};

class SibTreeNode {
    Object* item;
    SibTreeNode* parent;
    ListNode* childList;
};

SibTreeNode要素ごとに4つではなく5つのポインターを使用します。

于 2013-02-21T12:33:25.147 に答える