0

2-3-4 ツリーで明確化していただければ幸いです...次のように定義されたツリーがあるとします。 


class N234{  //node class
    public:
        int firstData, secondData, thirdData;
        N234 *firstChild,*secondChild,*thirdChild,*fourthChild,*parent;
};



class T234{  //tree with root node
    public:
        T234(){
            this->root->parent=NULL;
            this->root->firstChild=NULL;
            this->root->secondChild=NULL;
            this->root->thirdChild=NULL;
            this->root->fourthChild=NULL;
        }
    private:
        N234* root;
};
私の質問は、実際には、ノードの変数 (firstData、secondData、 thirdData) にすでに何らかの値がある場合に、ノードがいっぱいである (3 つの値がすべて含まれている) かどうかをどのように知ることができるかということです。

例:
ルート: |4| ルートの左の子:|1,2|
ルート |7,9| の右の子

ここで root には 1 つの値 (4) があります。私の質問は、彼の他のすべての変数 (secondData、 thirdData) には何らかの値があるため (たとえそれがゴミであっても)、実際に 1 つの値を持っていることをどのように知ることができるかということです.. よろしくお願いします!

4

2 に答える 2

0

「キーの総数」メンバー変数をノード クラスに追加する必要がある

class N234{  //node class
 public:

   N234(int x) : totalItems(1) { keys[0] = x; children[0] = 0; } 

   N234(int x, int y) : totalItems(2) {keys[0] = x; keys[1] = y; children[0] = 0;}

   N234(int x, int y, int z) : totalItems(3) { keys[0] = x; keys[1] = y; 
                      keys[2] = z; children[0] = 0; }

   bool isLeaf() { return child[0] == 0 ? true : false }
   bool isFourNode() { return totalItems == 4 : true : false}
  private:
   totalItems;
   int keys[3];
   N234 *children[4];
};

次に、4 ノードかどうかを確認します。

于 2014-09-02T17:26:50.480 に答える
0

心配する内部ノードしかない場合、最も簡単な方法は、子ポインターを確認することです。

が null の場合thirdChild、ノードは 2 ノードであるため、意味のある値 ( firstData) は 1 つだけで、残り ( secondData、thirdData) にはジャンクが含まれます。

thirdChildnull ではないが nullの場合fourthChild、3 ノードです。最初の 2 つのデータ変数には意味のある値が含まれています。

すべての子ポインターが null でない場合、それは 4 ノードです。

このアプローチの唯一の問題は、ポインターが実際に無効であり(たとえば、thirdChild2 ノードの場合)、単に使用されていない場合は、ポインターを null にする必要があることです。ただし、すべての有効な子ポインターが使用されるわけではありません (たとえば、firstChildリーフである 2 ノードのポインター)。

したがって、1 つの解決策は、すべての無効なポインターが指すノードを作成し、それ以外の方法では使用しないことです。ある意味では、通常の NULL とは異なる、2 番目の NULL として機能します。

どの種類のポインタ (無効、または有効だが未使用) が NULL を指し、どのポインタが偽のノードを指しているかは問題ではないことに注意してください。(また、「2 番目の NULL」に NULL 以外の値を使用できることにも注意してください。実際のノードのアドレスである必要はありませんが、ノードのアドレスにはならないことを確認する必要があります。とにかく、そのようなアプローチを使用するのは緊張します。)

于 2014-06-15T23:48:46.130 に答える